「プロジェクトオイラー問61」の編集履歴(バックアップ)一覧はこちら
「プロジェクトオイラー問61」(2014/02/21 (金) 15:29:52) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2061
*Problem 61 「巡回図形数」 †
三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
三角数 P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
四角数 P4,n=n2 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, 8, 21, 40, 65, ...
3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.
この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
4桁の数の組で上の2つの性質をもつはこの組だけである.
三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.
解法
全探索でいい気もしますが。
一応動的計画法で解いてみました。
巡回するのでどの数から初めても問題ありません。
よって三角数を最初にして。
その後は
- 三角数の1000と100の位、
- 使用済みのn角数をビットで管理
- 一番最後に選んだ数の下2桁
この3つを主キーに、そこまでの合計値を主キーに対する値として動的計画法で回します。
n個だけ角数から選んだ状態からn+1個選んだ状態を計算します。
解が唯一であるというヒントを頼りに、主キーが同じになったものは一つだけ残して他は廃棄します。
効率化できたかどうかは微妙なところです。
ps3(N,N3):-
N3 is (N*(N+1))//2.
ps4(N,N4):-
N4 is N^2.
ps5(N,N5):-
N5 is (N*(N*3-1))//2.
ps6(N,N6):-
N6 is N*(2*N-1).
ps7(N,N7):-
N7 is (N*(5*N-3))//2.
ps8(N,N8):-
N8 is N*(3*N-2).
ps(Siki,[P1,P2]):-
between(1,200,N),
call(Siki,N,Pa),
1000=<Pa,
Pa=<9999,
P1 is Pa//100,
P2 is Pa mod 100.
ps_w(Siki,Result):-
findall(R,ps(Siki,R),Result).
one_calc([Top,Bits,Tail,Sum],Ps,[Top,Bits1,Tail1,Sum1]):-
between(0,5,No),
(Bits /\ (1<<No))=:=0,
Bits1 is Bits \/ (1<<No),
nth0(No,Ps,P),
member([Tail,Tail1],P),
Sum1 is Sum+Tail*100+Tail1.
next_calc(DP,Ps,Result):-
member(E,DP),
one_calc(E,Ps,Result).
myunion([],Set,[Set]):-!.
myunion([[Top,Bits,Tail,_]|Rest],[Top,Bits,Tail,Sum],Result):-
!,
myunion(Rest,[Top,Bits,Tail,Sum],Result).
myunion([Set|Rest],Set1,[Set1|Result]):-
!,
myunion(Rest,Set,Result).
to_seed([],[]):-!.
to_seed([[Top,Tail]|Rest],[[Top,1,Tail,Sum]|Result]):-
Sum is Top*100+Tail,
to_seed(Rest,Result).
ok_list([],[]):-!.
ok_list([[Top,_,Top,Sum]|Rest],[Sum|Result]):-
!,
ok_list(Rest,Result).
ok_list([_|Rest],Result):-
!,
ok_list(Rest,Result).
dp(6,DP,_):-
!,
ok_list(DP,Ans),
write(Ans).
dp(Deep,DP,Ps):-
!,
findall(Re,next_calc(DP,Ps,Re),NextDP),
sort(NextDP,[Top|NextDP1]),
myunion(NextDP1,Top,NextDP2),
Deep1 is Deep+1,
dp(Deep1,NextDP2,Ps).
main61:-
ps_w(ps3,Ps3),
ps_w(ps4,Ps4),
ps_w(ps5,Ps5),
ps_w(ps6,Ps6),
ps_w(ps7,Ps7),
ps_w(ps8,Ps8),
PsAll =[Ps3,Ps4,Ps5,Ps6,Ps7,Ps8],
to_seed(Ps3,Seed),
dp(1,Seed,PsAll)
.