AOJ0559 JOI Flag

問題リンク JOI Flag

• 解法

ビットDPで解きました。
旗の種類は3^(?の数)だけあります。求めたいのは良い旗ですが、その余事象である悪い旗を数えても、解が求まります。
左上からマスを決定するとして、(i, j)のマスXについて考えます。もしNマス前に、"JO"が出現していたか分かればここに"I"を置いてよいか否かが分かります。直前のN個分のマスの状態Sが必要になってきます。(i, j)の次のマスについては、Sを1ビット左にシフトして下位Nビットを残せば状態Sの更新ができます。(i, j)のマスに新たに"JO"ができたならば別途更新します。新たに"JO"が作れるかという判定のために1つ左がJかどうかの真偽値も必要になってきます(0列目は必ずfalseです)。まとめると
dp[i][j][S][isJ]: (i, j)以降を考え、直前Nマスの状態がS、左のマスがJかどうかがisJのときの悪い旗の個数
という表を埋めて解きます。
ですが、これだとメモリ制限に引っ掛かります。
(i, j)の更新には1つ手前のマスの情報のみ影響するので dp[2][S][isJ] だけで事足ります。
まだこれでも足りません。実は状態Sについて存在しうる状態数は11000くらいしかありません("JO"は隣り合うことがないので1が連続しないからです)。よって、それらの状態に番号付けを行うと、
dp[2][11000程度][isJ]
という表でDPができます。

N個手前の情報のみをビットにしてDPするタイプの問題を解けたのはこれが初めてです。
問題に取り組む際、余事象をとることと、"JO"の出現場所を覚えればよいのではないかと思い付いたまでは良かったのですが、それをどうプログラムにしたらよいかまでは分からずに公式解説を見ました。このタイプの問題には今後慣れていきたいものです。たぶんコレも、ぱっと見この問題の類題だと思うので、今度は自力で正解まで辿りついてみたいです。

• ソース

import java.util.Scanner;

//JOI Flag
public class AOJ0559 {

	void run(){
		int MOD = 100000;
		char[] ch = {'J','O','I'};
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt(), w = sc.nextInt();
		int MASK = (1<<w)-1, mask = 1<<(w-1);
		int ALL = 1;
		char[][] map = new char[h][];
		for(int i=0;i<h;i++){
			map[i]=sc.next().toCharArray();
			for(int j=0;j<w;j++)if(map[i][j]=='?')ALL=(ALL*3)%MOD;
		}
		int[] ref = new int[15000], rev = new int[1<<w];
		int ID = 0;
		for(int S=0;S<1<<w;S++){
			if((S&1)>0)continue;
			boolean ok = true;
			for(int j=0;j+1<w;j++)if(((S>>j)&1)>0&&((S>>(j+1))&1)>0)ok = false;
			if(ok){
				rev[S] = ID;
				ref[ID++] = S;
			}
		}
		int[][][] dp = new int[2][ID][2];
		int X = 0;
		dp[1][0][0] = 1;
		for(int i=0;i<h;i++)for(int j=0;j<w;j++){
			for(int k=0;k<ID;k++)for(int J=0;J<2;J++)dp[X][k][J] = 0;
			for(int k=0;k<ID;k++)for(int J=0;J<2;J++){
				int S = ref[k];
				int D = dp[1-X][k][J];
				if(D==0)continue;
				if(map[i][j]!='?'){
					if((S&mask)>0&&map[i][j]=='I')continue;
					int ns = S;
					if(J==1&&map[i][j]=='O')ns++;
					ns<<=1;
					dp[X][rev[ns&MASK]][j==w-1?0:map[i][j]=='J'?1:0] = (dp[X][rev[ns&MASK]][j==w-1?0:map[i][j]=='J'?1:0]+D)%MOD;
				}
				else{
					for(int c=0;c<3;c++){
						char use = ch[c];
						if(use=='J'){
							int ns = S<<1;
							dp[X][rev[ns&MASK]][j==w-1?0:1] = (dp[X][rev[ns&MASK]][j==w-1?0:1]+D)%MOD;
						}
						else if(use=='O'){
							int ns = S;
							if(J==1)ns++;
							ns<<=1;
							dp[X][rev[ns&MASK]][0] = (dp[X][rev[ns&MASK]][0]+D)%MOD;
						}
						else{
							int ns = S<<1;
							if((S&mask)>0)continue;
							dp[X][rev[ns&MASK]][0] = (dp[X][rev[ns&MASK]][0]+D)%MOD;
						}
					}
				}
			}
			X = 1-X;
		}
		int res = 0;
		for(int k=0;k<ID;k++)for(int J=0;J<2;J++)res=(res+dp[1-X][k][J])%MOD;
		System.out.println((ALL-res+MOD)%MOD);
	}
	
	public static void main(String[] args) {
		new AOJ0559().run();
	}
}