「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枚をその週の最初の仕事に使う.
使われなかった紙は全て元の封筒に収める.
さて, 各仕事の際に, 主任は封筒からランダムに紙を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 155 「キャパシタ回路の数え上げ」 †
電気回路を題材にした問題。
18個までの同質のコンデンサのみを使って並列回路と直列回路の電気回路のサブユニットを作りそのサブユニット同士を結合してできるユニットを考える。
このユニットで得られる静電容量の種類数を答えよ。
解法
若い時前頭側頭葉認知症に近い寝たきり若者だったので、電気の知識は小学校で止まっている。
中学校レベルの教育はわずかしか受けてないし、高校は最低ランクでほとんど教育を受けてない。
私の受けた電気回路の教育は乾電池をつなぐとライトがつくというのが受けた一番高等な教育。
コンデンサ（これはなんとなく電気世界のダムみたいなもの？）？静電容量？なにそれ？
と思いつつとりあえず、問題の指定通り考えて組み合わせ論の問題として電気のことを理解せずにアセプト。
数字の上でだけ考えて解いた。
計算速度が遅いのでそのうちきちんとした形にしたいですね。
とりあえずC++で実装したコードから掲載。
C++なら早くなるかと思ったが早くならない、我慢できない速度ではないが早いわけでもない。
同じ形の組み合わせを何度も計算してるし、サブユニットの順番を並べ替えても同じ静電容量が得られる場合などの無駄な計算を排除できてない。
よい点はコードがシンプルな形になってるくらいでほめるところが全くない。
#include<stdio.h>
#include<set>
__int64 gcd ( __int64 a, __int64 b )
{
__int64 c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
struct S{
__int64 u,d;
bool operator<(const S s)const{
if(u!=s.u)return u<s.u;
return d<s.d;
}
S split(S s){
S s2;
s2.u=s.u*d+u*s.d;
s2.d=s.d*d;
__int64 div=gcd(s2.u,s2.d);
s2.u/=div;
s2.d/=div;
return s2;
}
S chain(S s){
S s2;
s2.u=u*s.u*d*s.d;
s2.d=s.d*d*(s.u*d+u*s.d);
__int64 div=gcd(s2.u,s2.d);
s2.u/=div;
s2.d/=div;
return s2;
}
};
int main(){
std::set<S> memo[19],all;
std::set<S>::iterator it1,it2;
S s1,s2;
s1.u=1;
s1.d=1;
memo[1].insert(s1);
all.insert(s1);
for(int i=2;i<=18;i++){
for(int a=1;a*2<=i;a++){
int b=i-a;
for(it1=memo[a].begin();it1!=memo[a].end();it1++){
for(it2=memo[b].begin();it2!=memo[b].end();it2++){
memo[i].insert((*it1).split((*it2)));
memo[i].insert((*it1).chain((*it2)));
}
}
}
all.insert(memo[i].begin(),memo[i].end());
printf("i=%d perm=%d)\n",i,all.size());
}
}
gcd(0, B, B):-!.
gcd(A, B, G):- A > 0, R is B mod A, gcd(R, A, G).
add(U1,D1,U2,D2,U4,D4):-
U3 is U1*D2+U2*D1,
D3 is D1*D2,
gcd(U3,D3,DIV),
U4 is U3//DIV,
D4 is D3//DIV.
calc_split(NowLimit,Memo,[U3,D3]):-
between(0,NowLimit,A),
A*2=<NowLimit,
B is NowLimit-A,
member([A,Xs],Memo),
member([B,Ys],Memo),
member([U1,D1],Xs),
member([U2,D2],Ys),
add(U1,D1,U2,D2,U3,D3).
calc_chain(NowLimit,Memo,[U4,D4]):-
between(1,NowLimit,A),
A*2=<NowLimit,
B is NowLimit-A,
member([A,Xs],Memo),
member([B,Ys],Memo),
member([U1,D1],Xs),
member([U2,D2],Ys),
U3 is U1*U2*D1*D2,
D3 is D1*D2*(U1*D2+D1*U2),
gcd(U3,D3,Div),
U4 is U3//Div,
D4 is D3//Div.
next_calc(NowLimit,Memo,Result):-
calc_split(NowLimit,Memo,Result).
next_calc(NowLimit,Memo,Result):-
calc_chain(NowLimit,Memo,Result).
all_union([],[]):-!.
all_union([[_,Es]|Rest],Result1):-
!,
all_union(Rest,Re),
append(Re,Es,Result),
sort(Result,Result1).
search(_,Memo):-nl,all_union(Memo,Memo1),length(Memo1,Ans),write(Ans),nl,fail.
search(19,Memo):-!,nl,all_union(Memo,Memo1),length(Memo1,Ans),write(Ans).
search(N,Memo):-
!,
findall(E,next_calc(N,Memo,E),AddMemo),
sort(AddMemo,AddMemo1),
N1 is N+1,
search(N1,[[N,AddMemo1]|Memo]).
test:-X is 2048*1024*1024,set_prolog_stack(global,limit(X)),
search(2,[[1,[[1,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)
となります。
プロジェクトオイラーの問題を堀江伸一さんが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 155 「キャパシタ回路の数え上げ」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20155
電気回路を題材にした問題。
18個までの同質のコンデンサのみを使って並列回路と直列回路の電気回路のサブユニットを作りそのサブユニット同士を結合してできるユニットを考える。
このユニットで得られる静電容量の種類数を答えよ。
解法
若い時前頭側頭葉認知症に近い寝たきり若者だったので、電気の知識は小学校で止まっている。
中学校レベルの教育はわずかしか受けてないし、高校は最低ランクでほとんど教育を受けてない。
私の受けた電気回路の教育は乾電池をつなぐとライトがつくというのが受けた一番高等な教育。
コンデンサ（これはなんとなく電気世界のダムみたいなもの？）？静電容量？なにそれ？
と思いつつとりあえず、問題の指定通り考えて組み合わせ論の問題として電気のことを理解せずにアセプト。
数字の上でだけ考えて解いた。
計算速度が遅いのでそのうちきちんとした形にしたいですね。
とりあえずC++で実装したコードから掲載。
C++なら早くなるかと思ったが早くならない、我慢できない速度ではないが早いわけでもない。
同じ形の組み合わせを何度も計算してるし、サブユニットの順番を並べ替えても同じ静電容量が得られる場合などの無駄な計算を排除できてない。
よい点はコードがシンプルな形になってるくらいでほめるところが全くない。
#include<stdio.h>
#include<set>
__int64 gcd ( __int64 a, __int64 b )
{
__int64 c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
struct S{
__int64 u,d;
bool operator<(const S s)const{
if(u!=s.u)return u<s.u;
return d<s.d;
}
S split(S s){
S s2;
s2.u=s.u*d+u*s.d;
s2.d=s.d*d;
__int64 div=gcd(s2.u,s2.d);
s2.u/=div;
s2.d/=div;
return s2;
}
S chain(S s){
S s2;
s2.u=u*s.u*d*s.d;
s2.d=s.d*d*(s.u*d+u*s.d);
__int64 div=gcd(s2.u,s2.d);
s2.u/=div;
s2.d/=div;
return s2;
}
};
int main(){
std::set<S> memo[19],all;
std::set<S>::iterator it1,it2;
S s1,s2;
s1.u=1;
s1.d=1;
memo[1].insert(s1);
all.insert(s1);
for(int i=2;i<=18;i++){
for(int a=1;a*2<=i;a++){
int b=i-a;
for(it1=memo[a].begin();it1!=memo[a].end();it1++){
for(it2=memo[b].begin();it2!=memo[b].end();it2++){
memo[i].insert((*it1).split((*it2)));
memo[i].insert((*it1).chain((*it2)));
}
}
}
all.insert(memo[i].begin(),memo[i].end());
printf("i=%d perm=%d)\n",i,all.size());
}
}
gcd(0, B, B):-!.
gcd(A, B, G):- A > 0, R is B mod A, gcd(R, A, G).
add(U1,D1,U2,D2,U4,D4):-
U3 is U1*D2+U2*D1,
D3 is D1*D2,
gcd(U3,D3,DIV),
U4 is U3//DIV,
D4 is D3//DIV.
calc_split(NowLimit,Memo,[U3,D3]):-
between(0,NowLimit,A),
A*2=<NowLimit,
B is NowLimit-A,
member([A,Xs],Memo),
member([B,Ys],Memo),
member([U1,D1],Xs),
member([U2,D2],Ys),
add(U1,D1,U2,D2,U3,D3).
calc_chain(NowLimit,Memo,[U4,D4]):-
between(1,NowLimit,A),
A*2=<NowLimit,
B is NowLimit-A,
member([A,Xs],Memo),
member([B,Ys],Memo),
member([U1,D1],Xs),
member([U2,D2],Ys),
U3 is U1*U2*D1*D2,
D3 is D1*D2*(U1*D2+D1*U2),
gcd(U3,D3,Div),
U4 is U3//Div,
D4 is D3//Div.
next_calc(NowLimit,Memo,Result):-
calc_split(NowLimit,Memo,Result).
next_calc(NowLimit,Memo,Result):-
calc_chain(NowLimit,Memo,Result).
all_union([],[]):-!.
all_union([[_,Es]|Rest],Result1):-
!,
all_union(Rest,Re),
append(Re,Es,Result),
sort(Result,Result1).
search(_,Memo):-nl,all_union(Memo,Memo1),length(Memo1,Ans),write(Ans),nl,fail.
search(19,Memo):-!,nl,all_union(Memo,Memo1),length(Memo1,Ans),write(Ans).
search(N,Memo):-
!,
findall(E,next_calc(N,Memo,E),AddMemo),
sort(AddMemo,AddMemo1),
N1 is N+1,
search(N1,[[N,AddMemo1]|Memo]).
test:-X is 2048*1024*1024,set_prolog_stack(global,limit(X)),
search(2,[[1,[[1,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)
となります。
