プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ。 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) の最大値を求めよ. 解法。 この問題は3種類の解法を考え付きました。 最初は賢くない解法で、次はとても速いが頭の悪い解法で最後はエレガントな解法です。 まずはそんなに賢くない解法を書きます。 a=1,b=2,,,z=26として数字に置き換えます。 たとえば左寄り辞書順で後ろの文字のセットが一か所 5,10 とあったとします。 右は5より小さい数が必ず配置可能でその0~何個かの並びは必ず降順です。 左は10より大きな数は必ず配置可能でその0~何個かの並びは降順です。 そして間の6,7,8,9は右か左に配置します。 右ならどんな選び方をしても抜き取ったものは降順に並べるしかありませんし、左に配置するなら抜き取ったものは降順に並べるしかありません。 14,13,12,9,8(5,10)7,6,4,2,1 のようになります。 降順という性質を利用して全組み合わせを計算します。 具体例で考えてみましょう。 26文字から抜き出して12文字作る場合を考えてみます。 昇順になってる2文字が5,10なら -5の左に11~26までをa文字 -6,7,8,9の何文字かを5の左にb文字 -上の残りから何文字かを10の右にc文字 -1~4までの何文字かを10の右にd文字 として12=a+b+c+dとなる場合を考えこの組み合わせ数を求めます。 5や10をほかの数字2組にし全組み合わせを計算して合計すればn=12文字の場合の答えが出ます。 nがほかの値の場合も同様に求まります。 この発想で実装したコードは以下の通り。 実行するとわかりますが5秒もかかるとても遅いコードです。 早いコードについてはページをスクロールすると私なりに考えた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と文字列を数字列に置き換えます。 するとこの問題を満たす数字列の条件は降順になってる2つの数字列となります。 数字列は数字を大きいほうから数字を取り出して考えてこの2つのどちらかに数字を振り分けるかそれともその数字を捨てるかと考えます。 できた数列は以下のようになります。 (9 7 6 2)(8,4,3) すると重要な情報は、 -左の降順の終わりが右の降順数列のトップより小さい。 -何文字使ったか。 -集計するとき右と左に最低1文字以上割り振ってるか。 この3つ以外考慮する必要がないと分かります。 これを考えるとまず2~26までの数を一文字だけ右に割り振りあとはz~aまで一つずつ文字を左数列か右数列か捨てるかに割り振ります。 計算のためのmemo配列を考えてその上で計算します。 memo[a][b][c] a=0左に割り振られてない a=1左に割り振られたが右の最大値よりまだでかい a=2左に割り振られていて左のラストが右のトップより小さい bは文字の長さ0~26文字。 cは右側の最大値2~26 でこれをループすれば非常に小さい計算量で問題が解けます。 bやcあたり配列からビット数字列にすればさらに高速になりますがそこまでするとコードがかなり意味不明な暗号になるので手を出しません。 #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) となります。