SRM 514 600pt: MagicalGirlLevelTwoDivOne

TopCoder

問題概要

H*W(H,W<50)のボードがある。各マスは空か数字が入っている。空の部分には1~9の数字を埋めることができる。任意の箇所について、縦にN(<10)個連続する部分や横にM(<10)個連続する部分の和が奇数になっていなくてはならない。そのような埋め方は全部で何通りあるか求める問題。

考えたこと

  • 10以下という制約があるのでビットDPの可能性が高いことは分かる。
  • これは珍しく__builtin_parityが使える問題だということも分かる。
  • でも具体的な解法が分からない。本番は早めに切り上げてサンプルの弱い250の撃墜ケース作成に時間を使ってた
  • コンテスト終了後、左上のN*Mマスについて偶奇を決めれば残り全てのマスについても偶奇が定まるという指摘を受けた。なるほどそれは気付くべきことだ。
  • でもその後の方法もよく分からない。手も足も出ない感じだったのでりんごさんのコードを読んでとりあえず理解した気になった。
  • 2~3日開けて解き直してみたらちゃんとできた。
  • writerいわく、典型的DPらしい。

practiceで通したコード

りんごさんのコードを参考にした。計算量O(N*2^(2*M) + W*H)。

#include <vector>
#include <string>
using namespace std;

typedef long long int64;

const int MAX_N = 10;
const int64 MOD = 1000*1000*1000 + 7;
int64 odd[MAX_N][MAX_N];
int64 even[MAX_N][MAX_N];

int64 pat[MAX_N][1<<MAX_N];
int64 dp[MAX_N+1][1<<MAX_N];

struct MagicalGirlLevelTwoDivOne {

	int theCount(vector <string> palette, int N, int M) {
		int H = palette.size(), W = palette[0].length();

		//初期化
		for(int i=0; i<N; i++)for(int j=0; j<M; j++){
			odd[i][j] = even[i][j] = 1;
		}

		for(int i=0; i<H; i++)for(int j=0; j<W; j++){
			if(palette[i][j] == '.'){
				odd[i%N][j%M] = (odd[i%N][j%M] * 5) % MOD;
				even[i%N][j%M] = (even[i%N][j%M] * 4) % MOD;
			}
			else{
				if(palette[i][j]&1){
					even[i%N][j%M] = 0;
				}
				else{
					odd[i%N][j%M] = 0;
				}
			}
		}

		//各列に対して、パターン数を計算する
		for(int i=0; i<N; i++){
			for(int bit=0; bit<(1<<M); bit++)if(__builtin_parity(bit)){
				pat[i][bit] = 1;
				for(int j=0; j<M; j++){
					if((bit>>j)&1){
						pat[i][bit] = (pat[i][bit] * odd[i][j]) % MOD;
					}
					else{
						pat[i][bit] = (pat[i][bit] * even[i][j]) % MOD;
					}
				}
			}
		}

		//ビットDP
		dp[0][0] = 1;
		for(int i=0; i<N; i++){
			for(int bit1 = 0; bit1 < (1<<M); bit1++){
				for(int bit2 = 0; bit2 < (1<<M); bit2++)if(__builtin_parity(bit2)){
					dp[i+1][bit1 ^ bit2] = (dp[i+1][bit1 ^ bit2] + dp[i][bit1] * pat[i][bit2]) % MOD;
				}
			}
		}

		return (int)dp[N][(1<<M)-1];
	}

};