Problem 164 「どの連続した3桁の和も与えられた数を超えない数」 † ---- 問題 どの連続した3桁の和も9以下のような(9以下は9を含む)20桁の数(先頭の0は認めない)はいくつあるか? ---- 解法 この問題は3桁ごとに区切った動的計画法で解きます。 頭1~3桁目。 頭1~3桁目から頭1~4桁目までの組み合わせ数を求め。 これを繰り返して 頭17~19桁目までから頭1~20桁目までの組み合わせ数を求めます。 只今解説準備中、解法が当たり前すぎて逆に解説が難しい状態です、配列を知っている程度の中学生プログラマでもわかるように解説をかきたいのですが難しいです。 最初頭3桁の数を考えます。 memo[10][10][10]の3次元配列を考えます。 memo[A][B][C]とします。 Aは1桁目の0~9の数字に Bは2桁目の0~9の数字に Cは3桁目の0~9の数字に 対応します。 #ref(e164.gif) 図のようなイメージですね。 図で3つ選択し、 A+B+C<=9かつA>0ならば memo[A][B][C]=1 そうでないなら memo[A][B][C]=0 を割り当てます。 memoの値は頭3桁の値がABCとなる組み合わせを現します。 次に1~4桁目までの組み合わせ数を考えます。 次の段階を計算するための土台 next[B][C][D]を考え配列の中身は全部0で初期化します。 Dは4桁目の数だとします。 #ref(e164_2.gif) 赤枠から青枠を求める作業です。 memo[A][B][C]が1かつ B+C+D=<9 ならAの値を考慮することなく4桁目の組み合わせ数を計算できます。 3桁の和が9以下になるという条件を満たせばよいので2~4桁目が条件を満たせばAの値は考慮することなくBCDの3種類の数だけで1~4桁目までの組み合わせ数を管理できます。 単純に1~4桁目までの組み合わせ数の管理は next[B][C][D]=next[B][C][D]+memo[A][B][C] と足し合わせていけばよいと分かります。 難しく聞こえるかもしれませんが原理は単純です。 簡単すぎて逆に伝えるのが難しい。 手ごわい問題です。