AOJ0537 Bingo

AOJ Volume5

問題リンク Bingo

  • 解法

DPで解いたわけですが、DPについて色々と考えさせられる問題でした。
まず、ビンゴカードは狭義単調増加の長さN*Nの1次元配列と捉える事が出来ます。つまり、1〜Mの中からN*N個の要素を取り出して、その和がSになるパターン数を答える問題になります。
で、これはDPで求められます。
dp[ 利用した値の個数 ][ 和 ] -> パターン数
の表で求まります。
利用する値の中の最大値に関するループを一番外側に持ってきます。

for(int m=1;m<=M;m++){
  //処理
}

このループの内側で

for(int k=N*N;k>0;k--){ //使う個数を大きい方から
  for(int s=m;s<=S;s++){ //和sはm以上だけを考えれば十分
    dp[k][s] += dp[k-1][s-m]; //利用する値k個のうち1つはmとする。すると、M未満の数の中からk-1個を選んで和がS-mになるようなパターン数をカウントアップすればいい
  }
}

という感じにします。

以下、ほぼ自分用の備忘録です。

    • F(K, M, S): M以下の数を重複なくK個使い、和がSになるパターン数 という関数について

最初はこの関数Fから出発して、
dp[k][m][s]
を埋めるようなアプローチをとりました。
関数F(K, M, S)は
Mを採用する場合と、しない場合にわかれるので、
F(K, M, S) = F(K, M-1, S) + F(K-1, M-1, S-M)
となります。これはどちらも排反なのでパターン数の和がそのままF(K, M, S)のパターン数になります。
漸化式が求まったのでこれをプログラムにしてみたのが以下のコードです。(MODの処理は省略しています)
kの部分は最大の49個まで取ってしまうとMLEになるので、再利用DPにする必要があります。

for(int k=1;k<=N*N;k++){
  for(int m=1;m<=M;m++){
    for(int s=1;s<=S;s++){
      if(k==1){
        if(s<=m)dp[k][m][s] = 1; //k==1の基底状態だけは特別処理
      }
      else{
        dp[k][m][s] += dp[k][m-1][s];
        if(s-m>=0)dp[k][m][s] += dp[k-1][m-1][s-m];
      }
    }
  }
}

JOIが公開している判定データと突き合わせると確かにこれでも答えが求まります。ただAOJに提出するとTLEとなります。

    • dp[k][m][s]からdp[k][s]へ

最初の解法で死んでしまったので他所様のブログを参考にさせてもらうことにしました。
すると、2次元のDPで解けている人が幾人が見つかりました。使う値の上限Mについての情報量を落としたDPになっています。
どうやったら、2次元のDPに落とせることに気づけるかを色々考えてみます。

関数Fをよく見てみると、Mについて必要な値は常にM-1になっています。
ここで、dp[k][m][s]のDPがdp[2][m][s]と再利用可能な形に何故変形できたかを考えると、K-1、つまりKの直前の状態についてのM*Sの情報があれば十分だったからです。F(K, M-1, S)の情報も必要になりますが、これはMについて小さい方から求めることで対処出来ます。つまり、ループを工夫することで再利用可能にしたということです。
Mも直前の情報しか要らないのだから、Mについて再利用可能な形に変形できないだろうかと考えます。つまり、dp[k][m][s]をdp[2][m][s]にするのではなく、dp[2][k][s]にするのです。
実際、これでも正しく答えを求めることができます。
参考までに以下のようなコードになります。計算量オーダーは全く同じですが、K << Mなのでメモリ面が改善されています。

int[][][] dp = new int[2][N+1][S+1];
int X = 1;
for(int m=1;m<=M;m++,X=1-X){
	for(int k=1;k<=N;k++)for(int s=1;s<=S;s++){
		dp[X][k][s] = 0;
		if(k==1){
			if(s<=m)dp[X][k][s] = 1;
		}
		else{
			dp[X][k][s] += dp[1-X][k][s];
			if(s-m>=0)dp[X][k][s] += dp[1-X][k-1][s-m];
		}
		if(MOD<=dp[X][k][s])dp[X][k][s]-=MOD;
	}
}
System.out.println(dp[1-X][N][S]);

Mについては完全に直前の状態のK*Sしか使わないので、KとSのループは昇順降順を自由に決めても正しく動きます。

で、dp[2][k][s]のDPを得ることができたわけですが、これを更に落として2次元にするっていうのに気づくのはまだ自分には厳しいです。なので、dp[k][s]がどうして機能するのかを考えることにします。

    • dp[k][s]が機能する理由

もう一度、このDPのループを確認してみます。

int[][] dp = new int[N+1][S+1];
dp[0][0] = 1;
for(int m=1;m<=M;m++)for(int k=N;k>0;k--)for(int s=m;s<=S;s++){
	dp[k][s]+=dp[k-1][s-m];
}
System.out.println(dp[N][S]);

分かっている事実を書き下します。

kのループは降順にしなければならない
sは昇順でも降順でもよい
sをm〜Sでなく、1〜Sとして書くと遅くなる(TLEする)

AOJでTLEを回避できた要因はおそらく3つ目にあって、sのループが縮まったことが爆速になった原因だと思います。

基本原理が3次元だったDPを2次元にしたということは、計算順序を工夫することにより、メモリ空間を節約している、と自分は捉えています。ここでは、3次元DPは再利用の工夫をやめて、dp[m][k][s]として考えます。
まず、3次元の漸化式と2次元の漸化式で大きく異なっているのは、3次元DPにおける
dp[m][k][s] += dp[m-1][k][s]
という式が2次元DPには存在しないということです。これは、2次元DPでは、(m, k, s)と(m-1, k, s)はdp[k][s]という同じ場所を共有しているので無くなっているのだと考えられます。

そして、唯一存在する漸化式、
dp[k][s] += dp[k-1][s-m]
は3次元DPでは
dp[m][k][s] += dp[m-1][k-1][s-m]
に相当します。
手書きでみにくいですが、(m, k, s)の状態空間とかを図示したのが以下のものです。

右側にある図が今注目している漸化式について書いてみた図です。
(m, k, s)に加える(m-1, k-1, s-m)はどこにあるのかを示してみました。軸を図の通りに取るのならば、1列左側(k-1)で、sより下側の部分(s-m)のどこかに(k-1, s-m)があることになります。これを2次元に射影すると、注目しているグリッドの1列左側で下側にある(k-1, s-m)という1マスに格納されている値を自身に足しこんでいることになります。
これが、kを降順にしなければならない理由に直結しています。
以下が、それについての図です。

2次元DPでは、mについての情報を落としているので、計算順序が重要になります。kを昇順にループさせると、(m, k, s)の更新に必要な(m-1, k-1, s-m)の部分を(m, k-1, s-m)として上書きしてしまいます。そこで、kを降順にすることで、(m, k, s)の計算に必要な部分を壊さないようにしなければならないわけです。

これでなんとかdp[k][s]が機能する理由の説明がつきそうです。

基本は関数F(K, M, S)である。この関数は問題の答えを正しく求める。
F(K, M, S) = F(K, M-1, S) + F(K-1, M-1, S-M)である
dp[k][s]は(m, k, s)と(m-1, k, s)の場所を共有しているので、F(K, M-1, S)についての漸化式が要らない
(m, k, s)の更新に必要な(m-1, k-1, s-m)を破壊しないためにkのループは降順にする
以上より、dp[k][s]はdp[m][k][s]とした場合と同じ挙動をとる。dp[m][k][s]は関数F(K, M, S)と同じなのだからdp[k][s]も正しく答えを求める
dp[k][s]は、Sについてのループを[m, S]に縮めることができるので高速になる

こんな感じでしょうか。
今回は、他所様のブログを見ることで2次元DPを知りました。2次元DPの漸化式から、どんな挙動をしているのかを観察し、うまく動くことを確認できました（たぶん間違っていないはず）。後は、これを自分で思い付けるようになりたいですね。

  • ソース
import java.util.Scanner;

//Bingo
public class AOJ0537 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int MOD = 100000;
		for(;;){
			int N = sc.nextInt(), M = sc.nextInt(), S = sc.nextInt();
			if((N|M|S)==0)break;
			N*=N;
			int[][] dp = new int[N+1][S+1];
			dp[0][0] = 1;
			for(int m=1;m<=M;m++)for(int k=N;k>0;k--)for(int s=m;s<=S;s++){
				dp[k][s]+=dp[k-1][s-m];
				if(MOD<=dp[k][s])dp[k][s]-=MOD;
			}
			System.out.println(dp[N][S]);
		}
	}

	public static void main(String[] args) {
		new AOJ0537().run();
	}
}