Problem 164 「どの連続した3桁の和も与えられた数を超えない数」 †
解法
この問題は３桁から初めて１桁ずつ伸ばしていく動的計画法で解きます。
最初３桁で条件を満たす組み合わせをすべて元ます。
それに一桁ずつ足して４桁、５桁、、、の場合の組み合わせ数を計算し数字列と組み合わせ数のデータを２０桁まで伸ばします。
伸ばすとき簡単な理由から末尾３桁で分類しながら組み合わせ数を計算すればよいのですが、それについて今から説明します。
最初頭３桁の数を考えます。
memo[10][10][10]の３次元配列を考えます。
memo[A][B][C]とします。
Ａは１桁目の0～9の数字に
Ｂは２桁目の0～9の数字に
Ｃは３桁目の0～9の数字に
Ｄは４桁、、、
、、、
Ｔは20桁目の0～9
に対応します。
図のようなイメージですね。
図で３つ選択し、
Ａ+Ｂ+Ｃ＜＝9かつＡ＞0ならば
memo[A][B][C]=1
そうでないなら
memo[A][B][C]=0
を割り当てます。
memoの値は頭３桁の値がＡＢＣとなる組み合わせ数を現します。
次に１～４桁目までの組み合わせ数を考えます。
次の段階を計算するための土台
next[B][C][D]を考え配列の中身は全部0で初期化(0クリア)します。
nextは４桁目の組み合わせ数を管理するためのデータです。
Ｄは４桁目の数です。
赤枠から青枠を求める作業を行います。
memo[A][B][C]が１かつ３桁の和が９以下になるという条件を満たしているもので、２～4桁目が条件を満たせばＡの値は考慮することなくＢＣＤの３種類の数だけで１～４桁目までの組み合わせ数を管理できます。
単純に1～４桁目までの組み合わせ数の管理は
ABCDは0000～9999まで全てためせばよく,４重ループで片が付きます。
４重ループの中でB+C+D=<9
ならＡの値を考慮することなく４桁目の組み合わせ数を計算できます。
ループの中で
next[B][C][D]=next[B][C][D]+memo[A][B][C]
と足し合わせていけばよいと分かります。
難しく聞こえるかもしれませんが原理は単純です。
4桁はＡＢＣとＢＣＤの連続した桁の和が9以下になればよくＡＢＣはmemoの時点で検証済みです。
よって４桁の組み合わせを管理するには４桁の末尾ＢＣＤだけで組み合わせの計算を管理すればよいと判明するわけです。
５桁を計算するときは４桁で末尾がＢＣＤのものにＥを追加するのですから、ＣＤＥが9以下を判断するためにＣＤに分けて組み合わせ数を記録するのが必須であると判明します。
nextの計算がすべて終わったらmemoの内容をnextで上書きします。
そしてnextを0クリアします。
－５桁目
３桁から４桁の組み合わせ数を求めた上記と同じことを行うと今度は５桁となります。
ＢＣＤからＣＤＥを求めます。
ＢＣＤの組み合わせ数は３桁でＡＢＣが条件を満たし、ＢＣＤの３桁も条件を満たしたものだけがmemoに残っています、よって次もＡＢを考慮することなくＣＤＥだけで管理すればよいと分かります。
next[C][D][E]で５桁の場合の組み合わせ数を計算します。
計算法はＢＣＤＥを0000～9999までためし
C+D+E<=9となるものだけ
next[C][D][E]=next[C][D][E]+memo[B][C][E]
と計算すれば５桁目が出ます。
４桁の時と同様にnextの内容でmemoに上書きしnextを０クリアして。
あとは同じ要領で末尾３桁だけで組み合わせ数を管理しながら６ケタ～２０桁の計算を行います。
最後にmemo[R][S][T]にできた組み合わせ数を集計すれば答えとなります。
蛇足
誰にとっても呼吸するように簡単にコードが欠ける問題というのがあると思います。
私にとってはこの問題はそういう問題でした。
そういう問題は自分にとってあまりにあたりまえに書けるために他人に伝えようとしたときどう伝えたらいいのかよくわからない状態です。
最終更新：2013年12月11日 12:48
