「プロジェクトオイラー解説問164」の編集履歴（バックアップ）一覧に戻る
プロジェクトオイラー解説問164 - (2013/12/06 (金) 08:40:05) の編集履歴(バックアップ)
Problem 164 「どの連続した3桁の和も与えられた数を超えない数」 †
問題
どの連続した3桁の和も9以下のような(9以下は9を含む)20桁の数(先頭の0は認めない)はいくつあるか?
解法
この問題は３桁ごとに区切った動的計画法で解きます。
頭１～３桁目。
頭１～３桁目から頭1～４桁目までの組み合わせ数を求め。
これを繰り返して
頭17～１９桁目までから頭１～２０桁目までの組み合わせ数を求めます。
只今解説準備中、解法が当たり前すぎて逆に解説が難しい状態です、配列を知っている程度の中学生プログラマでもわかるように解説をかきたいのですが難しいです。
最初頭３桁の数を考えます。
memo[10][10][10]の３次元配列を考えます。
memo[A][B][C]とします。
Ａは１桁目の0～9の数字に
Ｂは２桁目の0～9の数字に
Ｃは３桁目の0～9の数字に
対応します。
図のようなイメージですね。
図で３つ選択し、
Ａ+Ｂ+Ｃ＜＝9かつＡ＞0ならば
memo[A][B][C]=1
そうでないなら
memo[A][B][C]=0
を割り当てます。
memoの値は頭３桁の値がＡＢＣとなる組み合わせを現します。
次に１～４桁目までの組み合わせ数を考えます。
次の段階を計算するための土台
next[B][C][D]を考え配列の中身は全部0で初期化します。
Ｄは４桁目の数だとします。
赤枠から青枠を求める作業です。
memo[A][B][C]が１かつ
B+C+D=<9
ならＡの値を考慮することなく４桁目の組み合わせ数を計算できます。
３桁の和が９以下になるという条件を満たせばよいので２～4桁目が条件を満たせばＡの値は考慮することなくＢＣＤの３種類の数だけで１～４桁目までの組み合わせ数を管理できます。
単純に1～４桁目までの組み合わせ数の管理は
next[B][C][D]=next[B][C][D]+memo[A][B][C]
と足し合わせていけばよいと分かります。
難しく聞こえるかもしれませんが原理は単純です。
簡単すぎて逆に伝えるのが難しい。
手ごわい問題です。
