【No.027】「AOJ 0537 Bingo」
この記事は、大昔に書いたけれど、なぜか公開されていなかった記事です。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1085385#1
僕のコードが他の人よりもずっと速かったので、解説したいと思います。
dp[ i ][ j ] = 1からMまでの整数の中で i 種類の数字を選び、合計を j にする場合の数
というdp配列を用意し、答えとしてdp[ N*N ][ S ]を出力するのが方針です。
僕なりに考えた漸化式はこうです。
dp[ i ][ j ] = dp[ i ][ j - i ] + dp[ i - 1 ][ j - i ] - dp[ i - 1][ j - M - 1 ]
具体例を挙げると、
(1から9までの整数で、3種類の数字を選んで合計を15にする場合の数)
=(1から9までの整数で、3種類の数字を選んで合計を12にする場合の数)
+(1から9までの整数で、2種類の数字を選んで合計を12にする場合の数)
-(1から9までの整数で、2種類の数字を選んで合計を5にする場合の数)
となります。
とりあえず確認してみましょう。
(1から9までの整数で、3種類の数字を選んで合計を15にする場合の数)
(3+4+8) (3+5+7) (4+5+6)
(2+4+9) (2+5+8) (2+6+7)
(1+5+9) (1+6+8)
合計8種類
(1から9までの整数で、3種類の数字を選んで合計を12にする場合の数)
(2+3+7) (2+4+6) (3+4+5)
(1+2+9) (1+3+8) (1+4+7) (1+5+6)
合計7種類
(1から9までの整数で、2種類の数字を選んで合計を12にする場合の数)
(3+9) (4+8) (5+7)
合計3種類
(1から9までの整数で、2種類の数字を選んで合計を5にする場合の数)
(1+4) (2+3)
合計2種類
8 = 7 + 3 - 2
となり、一致しています。
より詳しい解説
(1から9までの整数で、3種類の数字を選んで合計を15にする場合の数)
というものは、
1を含まないグループ
(4+5+6) (3+4+8) (3+5+7) (2+4+9) (2+5+8) (2+6+7)
1を含むグループ
(1+5+9) (1+6+8)
の2つに分類できます。
１を含まないグループの数は、
(1から9までの整数で、3種類の数字を選んで合計を12にする場合の数)
に対応しています。例えば、
( 3 + 4 + 8 )の場合、
( 2 + 3 + 7 )に対応しています。
（各数字が1小さくなっている）
1を含むグループの数は、
(1から9までの整数で、2種類の数字を選んで合計を12にする場合の数)
に対応しています。例えば、
( 1 + 5 + 9 ) の場合、
( 0 + 4 + 8 ) すなわち ( 4 + 8 ) に対応しています。
（各数字が１小さくなり、1だったものが0となって消える）
しかし、このままだと9種類になってしまいます。
消えた2種類というのは(1+2+9)と(3+9)です。
この2つは、
(1から9までの整数で、2種類の数字を選んで合計を5にする場合の数)
に対応しています。
(1+2+9) の各数字を1大きくすると、
(2+3+10) となり、数字の10が生まれます。
ここで数字の10を取り除くと、
(2+3)になります。
同様に、
(3+9) の各数字を1大きくしたあと、数字の1を追加すると、
(1+4+10) となり、さらに数字の10を取り除くと、
(1+4)になります。
