読者です 読者をやめる 読者になる 読者になる

dohatsutsu’s diary

日記を書いています。

【No.027】「AOJ 0537 Bingo」

この記事は、大昔に書いたけれど、なぜか公開されていなかった記事です。

 

 

ビンゴ | Aizu Online Judge

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を含まないグループの数は、

(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小さくなり、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)になります。