プロジェクトオイラーの問題を堀江伸一さんが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枚をその週の最初の仕事に使う. 使われなかった紙は全て元の封筒に収める. さて, 各仕事の際に, 主任は封筒からランダムに紙を1枚取り出す. もしA5の紙を取り出したならそのまま仕事に使う. そうでない場合は 半分に切る ことを繰り返し, A5の紙を1枚使い, 残りは元の封筒に戻す. 週の最初と最後の仕事以外で, 封筒に紙が1枚だけ入っている回数の期待値を求めよ. 回答は, 四捨五入し小数点以下6桁で答えること (x.xxxxxxという形). 解法 １６日目の作業が終わると必ずＢ5用紙一枚入っていて途中で紙が封筒に入ってないということが絶対ない面白い問題です。 数学的に解く方法がありそうですが私は単純なシミュレーション、動的計画法で解きました。 意外と計算誤差ってたまるものだなと実感。 cut([],[]):-!. cut([A|As],[AddA|ReAs]):- AddA is A+1, cut(As,ReAs). calc([A5],[DellA5]):-!,A5>0,between(1,A5,_),DellA5 is A5-1. calc([A|As],[DellA|ReAs]):- A>0, DellA is A-1, between(1,A,_), cut(As,ReAs). calc([A|As],[A|Result]):- calc(As,Result). next_calc(Memo,[M2,Perm,Hit1,E1]):- member([M,Perm,Hit,E],Memo), findall(M1,calc(M,M1),Temp), length(Temp,Len), member(M2,Temp), E1 is E/Len, Hit1 is Hit/Len. union_sum([],Y,[Y]):-!. union_sum([[X,Perm,Hit,E]|Rest],[X,Perm1,Hit1,E1],Result):- !, Perm2 is Perm+Perm1, Hit2 is Hit+Hit1, E2 is E+E1, union_sum(Rest,[X,Perm2,Hit2,E2],Result). union_sum([X|Rest],Y,[Y|Result]):- !, union_sum(Rest,X,Result). match([0,0,1,0]):-!. match([0,1,0,0]):-!. match([1,0,0,0]):-!. calc_e([],[]):-!. calc_e([[Count,Perm,Hit,E]|Rest],[[Count,Perm,Hit1,E]|Result]):- match(Count), !, Hit1 is Hit+E, calc_e(Rest,Result). calc_e([X|Rest],[X|Result]):- !, calc_e(Rest,Result). week(16,Memo):-!,write(Memo). week(N,Memo):- findall(M,next_calc(Memo,M),Memo1), N1 is N+1, msort(Memo1,Memo2), [Top|Memo3]=Memo2, union_sum(Memo3,Top,Memo4), calc_e(Memo4,Memo5), week(N1,Memo5). main151:-week(2,[[[1,1,1,1],1,0,1]]). *Problem 158 「左隣の文字より辞書順で後になる文字がちょうど1個となる文字列を探し当てよ」 † http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20158 26文字のアルファベットから3個の異なった文字を取ると, 長さ3の文字列を作ることができる. 例えば, 'abc', 'hat', 'zyx'となる. この3つの例について調べると, 'abc'は左隣の文字より辞書順で後になる文字が2個ある. 'hat'では, 左隣の文字より辞書順で後になる文字がちょうど1個となり, 'zyx'では0個となる. 左隣の文字より辞書順で後になる文字がちょうど1個となるような長さ3の文字列は全部で10400個存在する. いま, n ≤ 26 個の異なった文字について考える. nについて, p(n) を左隣の文字より辞書順で後になる文字がちょうど1個となるような長さnの文字列の個数であるとする. p(n) の最大値を求めよ. **解法。 この問題は３種類の解法を考え付きました。 最初は賢くない解法で、次はとても速いが頭の悪い解法で最後はエレガントな解法です。 まずはそんなに賢くない解法を書きます。 a=1,b=2,,,z=26として数字に置き換えます。 たとえば左寄り辞書順で後ろの文字のセットが一か所 5,10 とあったとします。 右は5より小さい数が必ず配置可能でその0～何個かの並びは必ず降順です。 左は１０より大きな数は必ず配置可能でその0～何個かの並びは降順です。 そして間の6,7,8,9は右か左に配置します。 右ならどんな選び方をしても抜き取ったものは降順に並べるしかありませんし、左に配置するなら抜き取ったものは降順に並べるしかありません。 14,13,12,9,8(5,10)7,6,4,2,1 のようになります。 降順という性質を利用して全組み合わせを計算します。 具体例で考えてみましょう。 ２６文字から抜き出して12文字作る場合を考えてみます。 昇順になってる２文字が5,10なら -5の左に11～26までをa文字 -６,7,8,9の何文字かを5の左にｂ文字 -上の残りから何文字かを１０の右にｃ文字 -1～4までの何文字かを１０の右にｄ文字 として12＝a+b+c+dとなる場合を考えこの組み合わせ数を求めます。 5や10をほかの数字２組にし全組み合わせを計算して合計すればn＝１２文字の場合の答えが出ます。 ｎがほかの値の場合も同様に求まります。 この発想で実装したコードは以下の通り。 実行するとわかりますが５秒もかかるとても遅いコードです。 早いコードについてはページをスクロールすると私なりに考えたC++コード（計算量＝BigO(15000)）を掲載。 sum([],0):-!. sum([X|Xs],Result):-!,sum(Xs,Re),Result is Re+X. combin(_,0,A,B,Result):-!,Result is A//B. combin(N,M,A,B,Result):- !, N1 is N-1, M1 is M-1, A1 is A*N, B1 is B*M, combin(N1,M1,A1,B1,Result). combin(N,M,Result):-combin(N,M,1,1,Result). calc(N,Result):- between(2,26,R), T is R-1, between(1,T,L), CenterSize is R-L-1, RightSize is 26-R, LeftSize is L-1, between(0,CenterSize,CExtraction), CExtraction=<N, between(0,CExtraction,CExtractionL), between(0,CExtraction,CExtractionR), CExtractionR is CExtraction-CExtractionL, CSizeL is CenterSize, CSizeR is CenterSize-CExtractionL, between(0,LeftSize,LExtraction), LExtraction+CExtraction+2=<N, RExtraction is N-CExtraction-LExtraction-2, 0=<RExtraction, RExtraction=<RightSize, combin(CSizeL,CExtractionL,CPL), combin(CSizeR,CExtractionR,CPR), combin(LeftSize ,LExtraction,LP), combin(RightSize ,RExtraction,RP), Result is CPL*CPR*LP*RP. test1(Sum):- between(2,26,N), findall(Perm,calc(N,Perm),Perms), sum(Perms,Sum). print_ans([]):-!. print_ans([Perm|Perms]):-write(Perm),nl,print_ans(Perms). main158:- findall(Sum,test1(Sum),Sums), print_ans(Sums). **問158 C++ BigO(15000)版 とても速いがかなり頭の悪い解法。 発想は簡単です。 a=1,,,z=26と文字列を数字列に置き換えます。 するとこの問題を満たす数字列の条件は降順になってる２つの数字列となります。 数字列は数字を大きいほうから数字を取り出して考えてこの２つのどちらかに数字を振り分けるかそれともその数字を捨てるかと考えます。 できた数列は以下のようになります。 (9 7 6 2)(8,4,3) すると重要な情報は、 -左の降順の終わりが右の降順数列のトップより小さい。 -何文字使ったか。 -集計するとき右と左に最低１文字以上割り振ってるか。 この３つ以外考慮する必要がないと分かります。 これを考えるとまず２～26までの数を一文字だけ右に割り振りあとはｚ～aまで一つずつ文字を左数列か右数列か捨てるかに割り振ります。 計算のためのmemo配列を考えてその上で計算します。 memo[a][b][c] a=0左に割り振られてない a=1左に割り振られたが右の最大値よりまだでかい a=2左に割り振られていて左のラストが右のトップより小さい bは左右文字列の長さの合計0～２６文字。 cは右側の最大値２～26 でこれをループすれば非常に小さい計算量で問題が解けます。 ｂやｃあたり配列からビット数字列にすればさらに高速になりますがそこまでするとコードがかなり意味不明な暗号になるので手を出しません。 #include<stdio.h> #include<iostream> #include<string.h> int main(){ __int64 memo[3][28][28]; memset(memo,0,sizeof(memo)); for(int i=2;i<=26;i++)memo[0][1][i]=1; for(int num=26;num>=1;num--){ for(int b=25;b>=1;b--){ for(int c=2;c<=26;c++){ if(c>num){ memo[0][b+1][c]+=memo[0][b][c]; memo[1][b+1][c]+=memo[1][b][c]; memo[2][b+1][c]+=memo[0][b][c]+memo[1][b][c]+2*memo[2][b][c]; } if(c<num){ memo[1][b+1][c]+=memo[0][b][c]+memo[1][b][c]; memo[2][b+1][c]+=memo[2][b][c]; } } } } __int64 ans[28]={0,}; for(int i=2;i<=26;i++){ for(int j=0;j<=26;j++){ ans[i]+=memo[2][i][j]; } std::cout<<ans[i]<<"\n"; } } **問158のとても賢い解法 3つめは本当に賢い解法。 らすかるさんというかたに掲示板で教えてもらった解法です。 ***答え p(n)=(26Cn)(2^n-n-1) 。 ***理由 n文字の時、まず26文字からn文字選ぶと26Cn通りです。 このn文字をk文字とn-k文字に分け、 k文字を降順に並べた後n-k文字を降順に並べる方法は nCk通りありますが、 nCk通りのうち1通りだけは全体が降順になってしまって条件を満たしません。 よってk文字とn-k文字に分けて条件を満たすのはnCk-1通りですから、 全体では 26Cn{(nC1-1)+(nC2-1)+(nC3-1)+…+(nC(n-1)-1)} =26Cn{nC1+nC2+nC3+…+nC(n-1)-(n-1)} =26Cn{(2^n-2)-(n-1)} =26Cn(2^n-n-1) となります。
