c21coterie @ ウィキ

c21coterie @ ウィキ内検索 / 「AOJ Problem Set from ALDS1 問20～24」で検索した結果

• 会津大学オンラインジャッジ復習
  ...ジです。 AOJitp1 AOJ Problem Set from ALDS1問　0～19 AOJ Problem Set from ALDS1 問20～24 AOJ Problem Set from ALDS1 問25～29 AOJ Problem Set from ALDS1 問30～34 AOJ Problem Set from ALDS1 問35～39 AOJ Problem Set from DSL 問0～問4 AOJProblem Set from CGL 問0～4 AOJProblem Set from CGL 問5～9 AOJ Problem Set from DPL 問0～4 AOJProblem Set from NTL 問0～4 AOJ再挑戦問0～4 AOJ再挑戦問...
• AOJ Problem Set from ALDS1問　0～19
  ...どんなんだろう？ AOJやっててよかったことは今のところ何もないので、評価値が下がろうが気にしない。 #include stdio.h #include string.h #include list const int LIMIT =((1 16)+33); std list int hashTable[LIMIT]; int h1(char *str){ int p,p1,num,result=0; char c; for(p=0;p strlen(str);p++){ c=str[p]; num=0; if(c== A )num=0; if(c== C )num=1; if(c== G )num=2; if(c== T )num=3; ...
• AOJ Problem Set from ALDS1 問20～24
  Tree - Tree Walk http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C lang=jp 2分木をデータから組み立て順番に訪問した結果を出力する問題。 #include stdio.h const int LIMIT=26; const int NIL=-1; struct node{ int p,right,left; }; node Tree[LIMIT]; void Preorder(int p){ if(p==-1)return; printf(" %d",p); Preorder(Tree[p].left); Preorder(Tree[p].right); } void Inorder(int p){ if(p==-1)return; Inord...
• AOJ Problem Set from ALDS1 問25～29
  Heaps - Maximum Heap http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B きちんとしたヒープを組み立てる問題。 #include stdio.h const int SIZE=500005; int heap_size; int A[SIZE]; void maxHeapify(int *A,int i){ int l=2*i; int r=2*i+1; int largest; if(l =heap_size A[l] A[i]){ largest=l; }else{ largest=i; } if(r =heap_size A[r] A[largest]){ largest=r; } if(largest!=i){ int t=A[i]; A[i]=A[la...
• AOJ Problem Set from ALDS1 問30～34
  Graph I - Graph http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A グラフのつながりを表示する問題。 #include stdio.h #include string.h const int LIMIT=101; int g[LIMIT][LIMIT]; int main(){ int n,u,k,v; scanf("%d", n); memset(g,0,sizeof(g)); for(int i=0;i n;i++){ scanf("%d %d", u, k); while(k--){ scanf("%d", v); g[u][v]=1; } } for(int i=1;i =n;i++){ for(int ...
• AOJ Problem Set from DSL 問0～問4
  Set - Disjoint Set Union Find Tree http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A 集合をユニオン木で管理せよという問題。 コード実行速度6/26位　タイム　0.03秒。 一位が0.02秒で２位が0.03秒５人、まあ平凡タイム。 #include stdio.h #include map int parents[10001]; int parentSearch(int p){ return (parents[p]=(p==parents[p]?p parentSearch(parents[p]))); } void parentUpdate(int p,int top){ if(p!=parents[p]){ parentUpdate(parents...
• prolog勉強プロジェクトオイラー121～130
  ...ひとつで一位が狙えるAOJと違ってプロジェクトオイラーは整数論の知識が要求される。 整数論の知識がない私にはこの問題は今のところお手上げだったのだが。 海外のコードも結構いじましい努力してるな。 深さを制限して1～200まで探索して制限内である数Nを作れたら確定で探索をまとめている。 もっと賢い方法を期待してたけど、こういう小手先のテクニックでも結構速くなるらしい。 プロジェクトオイラーのほうはどうせ整数論の知識もない私のことだし、一位を目指すとか上位を目指すとかそういうことはしない、まあできないけど。 深さ制限探索してある数Nが作れたときそのNをそれまでにもっと低い回数で作れていたら探索しない。 ということでまあ何とか見れる速度になった。 海外のコードを参考にしたし、なぜそれでうまくいくかの原理もよくわかってない。 参考サイトでも探そう。 search(_,...
• prolog勉強プロジェクトオイラー31～40
  プロジェクトオイラーの問題をＰｒｏlogで解くページ。 作者　堀江 伸一 近況　問い３６のコードの無駄を修正。 こんなネットの裏の裏の一番端っこの誰からも注目されないＷｉｋｉに何を書いたって世の中に何の影響も与えないので結構好きかって書いてます。 Problem 31 「硬貨の和」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2031 イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). 以下の方法で£2を作ることが可能である． 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p これらの硬貨を使...
• 会津大学オンラインジャッジ英語問題日本語訳
  会津大学オンラインジャッジの英語問題。 問題を意訳したものを掲載。 個人的な意訳なので正確性については保証しませんが、私が解けた問題だけ掲載しておきます。 Problem F Computation of Minimum Length of Pipeline http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1014 グラフの問題。 ｎ個の源泉、ｍ個の都市、源泉と都市の間の距離、都市と都市の間の距離が与えらえる。 源泉から都市へ熱水を供給したい。 源泉から都市へ、都市から都市へとパイプラインを引き全ての都市に熱水を供給し最短距離でつなげよ。 サンプルとして提示されているinputデータの解説は以下の通り。 3 5(源泉の数、都市の数) 12 8 25 19 23(源泉1からi番目の都市ま...
• prolog勉強プロジェクトオイラー141～150
  プロジェクトオイラーの問題を堀江伸一さんがProlog言語でとくページ。 整数論の知識はないので早いコードはあまりかけない。 Problem 142 「完全平方数コレクション」 † x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x y z 0で, 最小の x + y + z を求めよ. http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20142 解法 最新のパソコンで1秒くらいで答えが出る方法。 x+y=s1 x-y=s2 y+z=s3 y-z=s4 x+z=s5 x-z=s6 として x-s1=-y x-s2=y y-s3=-z y-s4=z として s1+s2の半分を...
• prolog勉強プロジェクトオイラー111～120
  ...オンラインジャッジ（AOJ）という競技プログラムの過去問を扱ったサイトでは私。 たまにですがコード実行速度１位を取ったり取った後で一月後位に１位を抜かれたりしています。 Problem 111 「重複桁を持つ素数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20111 この問題例えばMの値が正しいかは置いといて M(n,1)=2,M(n,2)=5でXは１を２個、２を５個持ち他に何個かの桁がそれ以外の数字で構成された素数があったとして、これが素数なら 1と２両方で足すのかという疑問があったが、計算してみると M(10,d)はｄが６以下になることがないみたいなのでこの疑問は解消されないままアセプト。 解けたものの分かりにくい問題だ。 test述語で駆動。 出てきた...
• prolog勉強プロジェクトオイラー1～10
  プロジェクトオイラーの問題を堀江伸一こと私がＰｒｏｌｏｇで解くページ。 プロジェクトオイラーの問題は問題番号が小さいものほど簡単で問題番号が大きいものは非常に難しくなります。 この辺は最初なので中学生プログラマでも挑戦できるレベルの問題が並ぶ。 Problem 1 「3と5の倍数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%201 1000未満の３か５の倍数になっている自然数の合計を答えよ 解法 数式で解くのが正しいけれどサイトの趣旨、数学の問題をプログラムで特に合わせて末尾再帰で記述。 mod_n(N,N) - member(R,[3,5]), N mod R= =0, !. mod_n(_,0) -!. search(1000,Ans) -!,write...
• prolog勉強プロジェクトオイラー171～180
  プロジェクトオイラーという数学の問題が掲載されているサイトの問題を堀江伸一さんがProlog言語で解くページ。 Problem 171 「各桁の平方の和が平方数となる数を求めよ」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20171 正の整数nについて, f(n)を各桁の数字(10進数)の平方の和と定義する. 例えば, f(3) = 3^2 = 9, f(25) = 2^2 + 5^2 = 4 + 25 = 29, f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4 = 36 0 n 10^20について, f(n)が平方数となるようなnの和の末尾9桁を求めよ. 解法 何も考えずまとめて計算すれば即座に答えが出ます。 P...
• prolog勉強プロジェクトオイラー161～170
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 Problem 161 「トリオミノ」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20161 トリオミノで9*12の長方形を埋め尽くすとき何通りの埋め方があるか答える問題。 解法 左下から右上へ敷き詰めていく。 ビット演算に翻訳して敷き詰め、あとは敷き詰め終わった部分は敷き詰め終わった部分の形（どのようなピースでどのように埋めたかは無視して全体の形だけ）を主キーにして動的計画法でアセプト。 計算に必要なのは３行だけなので9列*3行の２７ビットで管理ができこれはＰｒｏｌｏｇの一番短い整数型28bitより短い。 これで少し高速化を達成できているかもしれない。 Prologコード計算時間　2.112se...
• プロジェクトオイラー問２９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2029 Problem 29 「個別のべき乗」 † a^bで 2 =a,b =100を考えるとき重複を排除すると何通りの数が作れるか？ 解法 とりあえずプルートゥーズな方法で実装してみました。 全部求めて重複削除、それだけです。 calc(C) - between(2,100,A), between(2,100,B), C is A^B. main29 - findall(PowAB,calc(PowAB),PowABs), list_to_set(PowABs,PowABs1), length(PowABs1,Ans), write(Ans).
• プロジェクトオイラー問い111～120
  Problem 112 「はずみ数の濃度について調べ上げよ」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20112 左から右までどの桁もその左の桁を上回らない数を増加数と呼ぶ. 例えば, 134468. 同様に, どの桁もその右の桁を上回らない数を減少数と呼ぶ. 例えば, 66420. 増加数でも減少数でもない正の整数を「活発な」数と呼ぶことにする. 例えば, 155349. 100以下の数に活発な数が無いのは明らかだが, 1000より下の数では半数を少し上回る数(525)が活発である. 実際, 活発な数の割合が50%に達する最少の数は538である. 驚くべきことに, 活発な数はますます一般的になり, 21780では活発な数の割合は90%に達する. 活発な数が数の割合が99%...
• プロジェクトオイラー問い61～70
  問い61 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2061 三角数, 四角数, 五角数, 六角数, 七角数, 八角数に関する問題。 解法 問題をグラフに翻訳して深さ優先探索で解決です。 少し手の込んだ処理を書いてますがもしかしたらもっとシンプルになるかもしれません。 #include stdio.h #include vector #include map std map int,std vector int memo[9]; bool spents[9]={false,false,false,true,false,false,false,false,false}; void saiki(int start,int num,int deep,int...
• prolog勉強プロジェクトオイラー61～70
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ Problem 61 「巡回図形数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2061 三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される. 三角数P3,n=n(n+1)/2 1, 3, 6, 10, 15, ... 四角数P4,n=n^2 1, 4, 9, 16, 25, ... 五角数P5,n=n(3n-1)/2 1, 5, 12, 22, 35, ... 六角数P6,n=n(2n-1) 1, 6, 15, 28, 45, ... 七角数P7,n=n(5n-3)/2 1, 7, 18, 34, 55, ... 八角数P8,n=n(3n-2) 1, ...
• プロジェクトオイラー問４６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2046 Problem 46 「もうひとつのゴールドバッハの予想」 † Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した. 9 = 7 + 2×12 15 = 7 + 2×22 21 = 3 + 2×32 25 = 7 + 2×32 27 = 19 + 2×22 33 = 31 + 2×12 後に, この予想は誤りであることが分かった. 平方数の2倍と素数の和で表せない最小の奇合成数はいくつか? 解法 小さい数から試していきます。 i=2から初めてiを1ずつ増加させます。 iが平方数ならiとi以下の素数個々との和全部をstd setに入れます。 ...
• prolog勉強プロジェクトオイラー101～110
  プロジェクトオイラーの問題をPrologで解く堀江伸一さんのページ。 学がないのでリンク先みたいなサイトを見るたびうらやましくなるような人間です。 http //d.hatena.ne.jp/Lost_dog/touch/searchdiary?word=*%5BHaskell%5D 問い101「最適多項式」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20101 ニュートン補間を題材にした練習問題。 計算法や原理は分かったものの、Prologでどう実装したらよいかわからなかったのでとりあえずわかりやすさ重視でコードを実装。 f(N,Re) -Re is 1-N+N^2-N^3+N^4-N^5+N^6-N^7+N^8-N^9+N^10. f2(N,Re) -...
• prolog勉強プロジェクトオイラー21～30
  プロジェクトオイラーの問題をPrologで解くページ。 創価学会の皆さまから小学校の算数までしかできないと言われている堀江伸一さんがこのページのコードを書いているようです。 Problem 21 「階乗の数字和」 † http //projecteuler.net/problem=21 10000以下の友愛数の和を求めよという問題。 そのまま定義通り計算するだけです。 複数の関数で一つの関数を表現するＰｒｏlogて独特。 yakusuu_sum(1,_,1,Sum,Sum) -!. yakusuu_sum(N,M,1,Sum,Sum1) -N M*M,!,Sum1 is Sum*(N+1). yakusuu_sum(N,M,Multi,Sum,Result) - 0= =N mod M,!, N1 is N//M, Multi1 is Multi*M+1, ya...
• プロジェクトオイラー問５４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2054 Problem 54 「ポーカーハンド」 † ポーカーの勝敗を判定する問題。 詳細はリンク先を参照のこと。 解法 世界中で何回ポーカーの役判定のコードが書かれたのだろうかと思いをはせる問題です。 両者ともに素朴に役を判定して役に対応したスコアと役で使ったカードの数字を返し、 Aのほうがスコアが大きいなら勝利、同じならカードを比べてAの勝利か判定するだけ。 １を14として取り扱うと話が綺麗になります。 判定には巧みな手法があるそうなのでそれを調べるのもいいかもしれませんね。 ファイルは一行ごと１０枚のカードを現すリストと変換しています。 max(A,B,A) -A B,!. max(_,B,B) -!. ...
• プロジェクトオイラー問３１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2031 Problem 31 「硬貨の和」 † イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). 以下の方法で£2を作ることが可能である． 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p これらの硬貨を使って£2を作る方法は何通りあるか? 解法 初めてこの問題にPrologで挑戦した時は破壊的代入も配列もstd mapもないPrologでどうやって動的計画法をするか悩みました。 基本がわかれば考え方は簡単。...
• プロジェクトオイラー問８１
  http //projecteuler.net/problem=81 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2081 Problem 81 「経路の和 2方向」 † コストが最小になる経路移動の問題その１ 詳細はリンク先参照のこと。 解法 上の段からの動的計画法で間に合います。 テキストファイルは一段をリストとしてそのリストのリストに手作業で変換してから読み込んでいる。 sumA([],_,[]) -!. sumA([X|Xs],Sum,[Sum1|Result]) - !, Sum1 is Sum+X, sumA(Xs,Sum1,Result). min(A,B,A) -A B,!. min(_,B,B) -!. dp_one_row([],[],_...
• prolog勉強プロジェクトオイラー201～210
  プロジェクトオイラーの問題を堀江伸一子と私がProlog言語で解くページ。 最近スランプ気味。 Problem 201 「唯一の和を持つ部分集合」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20201 数の集合Aについて, sum(A)でAの要素の和を表す. 集合B = {1,3,6,8,10,11}を考えよう. Bの3要素の部分集合は20個あり, それぞれ和は以下になる. sum({1,3,6}) = 10, sum({1,3,8}) = 12, sum({1,3,10}) = 14, sum({1,3,11}) = 15, sum({1,6,8}) = 15, sum({1,6,10}) = 17, sum({1,6,11}) = 18, sum({...
• プロジェクトオイラー問い71～80
  問い71 分母が１００万以下で１より小さい既約分数を小さい順に並べた時3/7の左にある分数の分子を答えよ。 解法 ファレイ数列で一発です。 ファレイ数列が何故既約な分数を生成するかは理屈より図解で勉強したほうが分かりやすいか。 あれ？ファレイ数列の概念を使えばファイ関数を導き出せる？ #include stdio.h struct S{ int n,m; S operator+(const S s){ S re; re.n=n+s.n; re.m=m+s.m; return re; } }; int main(){ S s1,s2,s3; s1.n=2; s1.m=5; s2.n=3; s2.m=7; while(1){ s3=s1+s2; if(s3.m =1000*1000)break; s1=s3; } printf("%d",s...
• プロジェクトオイラー問い51～60
  問い51 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2051 　*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる. 　56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である 　56003は, このような性質を持つ最小の素数である.　 　桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注 連続した桁でなくても良い) 解法 100万までの素数をvectorに格納し、各素数それぞれについて*文字にチェンジした全パタ...
• prolog勉強プロジェクトオイラー11～20
  小学校の算数までしかできないと巷で評判の堀江伸一さんが、プロジェクトオイラーの問題にprolog言語で挑戦してみました。 ローカルな言語が集まるプロジェクトオイラーですが流石にprologで解いてるのは私だけかな、チェックはしてないけど。 Problem 11 「格子内の最大の積」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2011 20*20の格子に数字が入ってるものが与えられる。 上下左右斜めの連続する4つの数字の積の最大値を求めよ。 解法 こういう問題はＰｒｏlogのありがたさが少しだけわかる。 失敗したらとりあえずエラー処理もいらずにバックトラックしてくれるというのはとても便利。 dyxs(1,0). dyxs(0,1). dyxs(1,1). ...
• プロジェクトオイラー問い91～100
  問い91 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2091 0 =x,y =50の格子点で直角三角形を作るとき点の一つを原点に固定した時何通りの三角形を作れるか？ 解法 直角になる地点が決まれば後はベクトルの直角の概念から条件を満たす残りの点は決まります。 それを素直に計算するだけです。 #include stdio.h #include algorithm int gcd ( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } int main(){ int ans=0; for(int ax=0;ax =50;ax++){ for(int ...
• プロジェクトオイラー問１２４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20124 http //projecteuler.net/problem=124 Problem 124 「順序付き根基」 † n の"根基"(radical)は, rad(n) に関する問題。 詳細はリンク先参照のこと。 解法 エラトステネスの篩もどきでテーブル化して計算しソートし１万個めを求めるだけです。 計算量ＢｉｇＯ（366401）+１０万個の要素のソート。 まあ普通です。 世の中Ｊ言語使いこなしてる人多いなと思います。 Ｊ言語だとこの問題１行、究極のショートコードですね。 #include stdio.h #include algorithm struct E{ int n,r...
• prolog勉強プロジェクトオイラー91～100
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 問い91 原点が特殊処理が必要なくらいで後は点OAのベクトルを90度回してOA (a,b)としgcd(a,b)でOA 割ったベクトルを求め、そのベクトルの定数倍地点になる点の数を数えればOK。 gcd(0, B, B). gcd(A, B, G) - A 0, R is B mod A, gcd(R, A, G). min(X,Y,X) -X Y,!. min(_,Y,Y) -!. point_count(_,0,1000) -!. point_count(L,D,Result) - Result is L//D. r90(0,_,1,0) -!. r90(_,0,0,1) -!. r90(DY,DX,DY1,DX1) - gcd(DY,DX,G), DY1 is DX//G, DX1 is D...
• プロジェクトオイラー問５６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2056 Problem 56 「もっとべき乗の数字和」 † Googol (10＾100)は非常に大きな数である 1の後に0が100個続く. 100＾100は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも桁の和は1である. a, b 100 について自然数 ab を考える. 桁の和の最大値を答えよ. 解法 書くだけ問題でなんか面白くないです。 賢い方法あるのでしょうか？ keta_sum(0,0) -!. keta_sum(N,Result) - N1 is N//10, X is N mod 10, keta_sum(N1,Re), Result is Re+X. sear...
• prolog勉強プロジェクトオイラー191～200
  プロジェクトオイラーの問題を堀江伸一こと私がProlog言語で解くページ。 兵庫県加古川市加古川町南備後79-16 名前　堀江伸一 Problem 191 「賞を貰える文字列」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20191 ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している. 3日連続で休む, または, 2回以上遅刻した生徒は褒賞金を得る権利を失う. n日間の各生徒の出席状況を3進の文字列で表す. 文字はL (late, 遅刻), O (on time, 出席), A (absent, 欠席) である. 4日間の場合, 81通りの3進の文字列が考えられる. そのうち賞を貰えるのは以下の43個の文字列である. 30日間の場合, 賞を貰える文字列は何通り...
• プロジェクトオイラー問い101～110
  問い102　内部に原点を含む三角形はファイル内にいくつあるでしょう? http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20102 3つの異なる点が -1000 ≤ x, y ≤ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる. 以下の2つの三角形を考える. A(-340,495), B(-153,-910), C(835,-947) X(-175,41), Y(-421,-714), Z(574,-645) 三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる. 27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点...
• プロジェクトオイラー問７７
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2077 Problem 77 「素数の和」 † 10は素数の和として5通りに表すことができる 7 + 3 5 + 5 5 + 3 + 2 3 + 3 + 2 + 2 2 + 2 + 2 + 2 + 2 素数の和としての表し方が5000通り以上になる最初の数を求めよ. 解法 5000通りと少ないので全探索しても十分間に合います。 not_prime(N) -N 2,!. not_prime(N) - between(2,N,R), (R*R N - !,fail;true), N mod R= =0, !. is_prime(N) -not(not_prime(N)). search2(0,_,1...
• アルゴリズム勉強日記
  http //rose.u-aizu.ac.jp/onlinejudge/index.jsp?lang=ja リンク先は会津大学オンラインジャッジというプログラマ向け問題集を扱ったサイトです。 私はこのサイトでsinapusu2002という名前で登録しプログラムの問題集を解いてます。 私の成績 http //judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=sinapusu2002 極力自力で解こうとしていますが、どうしても解けない問題は検索して答えを見たり、掲示板で質問して解いてます。 その際のカンニング履歴を記録することにしました。 個人的なもので、自分一人が分かれば十分な記録です。 カンニング履歴 1 http //rose.u-aizu.ac.jp/onlinejudge/ProblemSet/d...
• プロジェクトオイラー問い81～90
  問い81 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2081 80*80サイズの表の左上から出発して表の右下まで進む時、経路上の数字の和が最小になるルートを求めよ。 下か右にしか移動できないものとする。 解法 一段ずつの動的計画法で一発です。 #include stdio.h #include string.h int main(){ int ans[81][81],num; char c; memset(ans,0,sizeof(ans)); for(int i=1;i =80;i++){ for(int j=1;j =80;j++){ scanf("%d%c", num, c); if(i==1){ ans[i][j]=num+ans[i][j-...
• プロジェクトオイラー問い41～50
  問い41 n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする. #下のリンク先にあるような数学的定義とは異なる 例えば2143は4桁Pandigital数であり, かつ素数である. n桁（この問題の定義では9桁以下）Pandigitalな素数の中で最大の数を答えよ. 解法 ９桁や８桁のパンデジタル数の各桁の和は45と36で9の倍数となっておりこれは８桁と９ケタのパンデジタル数は全て素数でないということを示しています、組み合わせ数を考えると驚く話です。 よって7桁までのパンデジタル数を全て全探索して検討すれば良いと分かります。 末尾の数字が２の倍数であってはいけないや大きな数字から試すなど各種ルールを適用すればもっと計算量が下がるかもしれません。 #include stdio.h #include stdlib.h bool...
• prolog勉強プロジェクトオイラー71～80
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 と書きましたが、下記リンク先サイトの方が私のコードよりずっと賢いのでそちらを参考にした方がよいです。 http //d.hatena.ne.jp/nineties/20110119 プロジェクトオイラーについては私のサイトよりこの人のサイトの方がずっと賢いです。 問い75はブロコット木を使えば早くなるとか、76や77は分割数と見るより、1～99までのコインを組み合わせたり素数を組み合わせる動的計画法とみるなど。 読めば目からうろこな発想でかかれています。 物事や問題をシンプルな話に変換できる能力、リンク先の人は私から見れば尊敬に値します。 プロジェクトオイラーの問題は問題番号が大きいほど難しくなるのですが、頭の悪い私でも問題番号100以下の簡単な問題なら解けます。 しかし同じ簡単な問題を解く...
• 会津大学オンラインジャッジカンニング履歴一覧
  http //rose.u-aizu.ac.jp/onlinejudge/index.jsp?lang=ja リンク先は会津大学オンラインジャッジというプログラマ向け問題集を扱ったサイトです。 私はこのサイトでsinapusu2002という名前で登録しプログラムの問題集を解いてます。 私の成績 http //judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=sinapusu2002 極力自力で解こうとしていますが、どうしても解けない問題は検索して答えを見たり、掲示板で質問して解いてます。 その際のカンニング履歴を記録することにしました。 個人的なもので、自分一人が分かれば十分な記録です。 カンニング履歴 1 http //rose.u-aizu.ac.jp/onlinejudge/ProblemS...
• prolog勉強プロジェクトオイラー151～160
  プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ。 Problem 151 「規格寸法用紙 期待値問題」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20151 とある印刷屋では毎週16回の定期的な仕事がある. 毎回 A5 サイズの特殊な色校正用紙 (special colour-proofing paper) を1枚使う. 月曜日の朝になると, 主任はA1サイズの特殊紙が入った新しい封筒を開ける. 彼はA1の紙を半分に切る. するとA2の紙が2枚出来上がる. 片方を半分に切りA3の紙が2枚出来上がる. 以下繰り返し, A5の紙を得るまで繰り返し, 1枚をその週の最初の仕事に使う. 使われなかった紙は全て元の封筒に収める. さて, 各仕事の際に, 主...
• プロジェクトオイラー問４９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2049 Problem 49 「素数数列」 † 項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ. (i)3つの項はそれぞれ素数である. (ii)各項は他の項の置換で表される. 1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する. それではこの数列の3つの項を連結した12桁の数を求めよ. 解法 まずa1 =a2 =a3 =a4でa1～a4は0～9の数という条件を満たす [a1,a2,a3,a4]というリストを全探索する。 ある[a1,a2,a3,a4]を並べ替えたものを４桁の整数とみて、これが素数であるか判定し ...
• プロジェクトオイラー問８９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2089 Problem 89 「ローマ数字」 † ローマ数字は同じ数をあらわすのに色々な表記ができる。 ファイルに必ずしも最短の長さでない方法で書かれたローマ数字が１０００個書かれている。 これを最短の長さに置き換えた場合何文字節約できるか答えよ。 ファイルや詳細はリンク先参照のこと。 解法 データファイルを文字列を集めたリストに手作業で変換し。 それを読み込み、文字コードリストを文字のリストに変換。 文字のリスト各文字を１０進数字に変換して、１０進数字からそのローマ数字の表す１０進数時に 変換し、１０進数時を最短のローマ数字で表記した時の長さを計算してとコードを書いた。 一つ一つの手順はおかしくないし丁寧に掛け...
• プロジェクトオイラー問８２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2082 Problem 82 「経路の和 3方向」 † 数字の書かれたマス目を移動して左端から右端へ到達する。 経路上の数字の和が最小になる経路を通った時のその和を答えよ。 詳細はリンク先参照のこと。 解法 一列ごとの動的計画法で片が付きます。 一列ごとの処理が少しわかりづらいので機能ごとに分割してもよかったかもしれません。 データファイルは一段を一つのリストとしてそのリストの集まりという形に手作業で変換してから読み込んでいる。 seed(0) - between(0,79,_). min(a,B,B) -!. min(A,a,A) -!. min(A,B,A) -A B,!. min(_,B,B) -!. dp_o...
• プロジェクトオイラー問４８
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2048 Problem 48 「自身のべき乗(self powers)」 † 次の式は, 1＾1 + 2^2 + 33 + ... + 10^10 = 10405071317 である. では, 1^1 + 2^2 + 3^3 + ... + 1000^1000 の最後の10桁を求めよ. 解法 mod演算の中で計算すれば結構速いですね。 modPow(_,0,1) -!. modPow(Pow,R,Result) - R mod 2= =1, !, R1 is R//2, Pow1 is (Pow^2) mod 10^10, modPow(Pow1,R1,Re), Result is (Re*Pow) mod 10^...
• プロジェクトオイラー問５０
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2050 Problem 50 「連続する素数の和」 † 素数41は6つの連続する素数の和として表せる 41 = 2 + 3 + 5 + 7 + 11 + 13. 100未満の素数を連続する素数の和で表したときにこれが最長になる. 同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ. 100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か? 解法 B Aとして A番目の素数までの集計値-B番目の素数までの集計値の差分が AからBまでの連続した素数の和です。 それだけの問題です。 素数は篩で選り分けて集計して。 後は差分のなかで素...
• プロジェクトオイラー問９５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2095 Problem 95 「友愛鎖」 † ある数の真の約数とは, それ自身を除く約数すべてである. 例えば, 28 の真の約数は 1, 2, 4, 7, 14 である. これらの約数の和は 28 に等しいため, これを完全数と呼ぶ. 面白いことに, 220 の真の約数の和は 284 で, 284 の真の約数の和は 220 となっており, 二つの数が鎖をなしている. このため, 220 と 284 は友愛数と呼ばれる. さらに長い鎖はあまり知られていないだろう. 例えば, 12496 から始めると, 5 つの数の鎖をなす. 12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 ...
• プロジェクトオイラー問６７
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2067 Problem 67 「最大経路の和 その2」 † 三角数もどきの頂から右下左下への移動を選びながら経路上の数字を合計する。 計が最大になる経路があるが、その経路の計を答えよ。 詳細はリンク先参照のこと。 解法 一段ごとの動的計画法で十分です。 一段をリストとし、そのリストを集めたリスト。 問題で与えられたテキストデータがそうなるように手作業で変換してから解いてます。 big(X,Y,X) -X Y,!. big(_,Y,Y) -!. next_row([X],[Z],[Z1]) -!,Z1 is Z+X. next_row([X],[_,Z],[Z1]) - !, Z1 is Z+X. next_ro...
• プロジェクトオイラー問６２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2062 Problem 62 「立方数置換」 † 立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である. 立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ. 解法 ３乗の数字を小さいほうから試していき、数字を辞書順で並べ替えたものを基準に集計していきます。 例えば345002なら002345が一つ見つかったとそれぞれ集計していきます。 最初に5個Hitした辞書順があればそれが答えです。 集計で新しい辞書順が出て...
• プロジェクトオイラー問９１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2091 Problem 91 「整数座標における直角三角形」 † 原点Ｏと２つの整数点(x,y)、ｘ、ｙは0から５０までの数。 で何個直角三角形が描けるか答える問題。 解法 点Ａを定めたらＯＡと直角でＡを通る直線状の点だけを検討します。 それだけでパッと答えが出ます。 原点が直角になる場合だけ特別扱いしてアセプトとなります。 sum([],0) -!. sum([X|Xs],Result) -sum(Xs,Re),Result is Re+X. points([X,Y]) - between(0,50,X), between(0,50,Y), X+Y 0. calc1(_,0,_,_,50) -!. calc1(0...
• @wiki全体から「AOJ Problem Set from ALDS1 問20～24」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索