美しすぎるプログラムの解説

program


↓で紹介した美しすぎるプログラムの解説を少し書いておく。


美しすぎるプログラムを解読せよの巻
http://d.hatena.ne.jp/yaneurao/20101013



配列dpの意味だが、
dp[r][i0][i1][i2][i3][i4][i5][i6][i7][i8][i9]
は、r桁の数字において、10進数で各桁を見たときに
・"0"の出現回数が(3-i0)回以内、
・"1"の出現回数が(3-i1)回以内、
…
・"9"の出現回数が(3-i9)回以内
であるような数の個数。このプログラムは(3-i0)のように補数(?)になっているのでちょっとわかりにくいと思う。


さて、例えば、r = 6(6桁)の場合について考えてみると、6桁というのは、5桁の数の左に1桁追加して出来る数だから、その左側に追加される1桁の数字が"0","1","2",…,"9"の場合それぞれについて考えてみる。


0XXXXX
1YYYYY
2ZZZZZ
…
9WWWWW


対称性があるので、いま"0"の出現回数についてだけ考える。


"0"の出現回数が3回以内である6桁の数の個数は、
0XXXXX("0"で始まって、XXXXXの部分の"0"の出現回数が2回以内である数)
と
1YYYYY("0"以外で始まって、YYYYYの部分の"0"の出現回数が3回以内である数)
みたいな感じにして分解出来る。実際には、YYYYYの部分に"1"が3回使われていると、1YYYYYの"1"の出現回数は4回になるので、これは除外されなければならない。すなわち、YYYYYの部分は、"0"の出現回数が3回以内、"1"の出現回数が2回以内である数だ。


まあ、ともかく、このように分解して考えると6桁の場合は、5桁の場合に基づいて考えることが出来る。同様にr+1桁の場合はr桁の場合に基づいて計算できる。これがDP(Dynamic Programming)の考え方である。

    long long res = 0;
    res += dp[17][0][1][0][0][0][0][0][0][0][0];
    res += dp[17][0][0][1][0][0][0][0][0][0][0];
    res += dp[17][0][0][0][1][0][0][0][0][0][0];
    res += dp[17][0][0][0][0][1][0][0][0][0][0];
    res += dp[17][0][0][0][0][0][1][0][0][0][0];
    res += dp[17][0][0][0][0][0][0][1][0][0][0];
    res += dp[17][0][0][0][0][0][0][0][1][0][0];
    res += dp[17][0][0][0][0][0][0][0][0][1][0];
    res += dp[17][0][0][0][0][0][0][0][0][0][1];

ちなみにこの↑部分は、18桁の数字(先頭は0で始まるものは除外)で"0","1",…,"9"の出現回数が3回以内である個数を求めるために、
1XXXXXXXXXXXXXXXXX (X…Xの部分は、17桁で、"1"が2回以内、その他が3回以内の出現回数)
2YYYYYYYYYYYYYYYYY (Y…Yの部分は、17桁で、"2"が2回以内、その他が3回以内の出現回数)
…
9WWWWWWWWWWWWWWWWW (W…Wの部分は、17桁で、"9"が2回以内、その他が3回以内の出現回数)
を足しあわせてある。


対称性があるので単に↓のように書いても同じ意味ではあるが、まあ…、そのへんは見た目の美しさと言うか何と言うか。

    long long res = dp[17][0][1][0][0][0][0][0][0][0][0] * 9;


あと、static storageは明示的に初期化しなくとも初期値が0であることは保証されているので配列dpのゼロ初期化↓は不要だと思うが…C/C++のそれぞれの規格でどうなってるのかはあたしゃよくは知らん。

    memset( dp, 0, sizeof( dp ) );


さて、読者への宿題。dp配列のサイズは、今回のプログラムは極端に大きい。これはどれくらいにまで縮めることが出来るだろうか？