kojingharangの日記

SRM 553 Div1 500 TwoConvexShapes

00:50 |

• W x H のグリッドに 'B' 'W' '?' のどれかが書いてある。? を B か W にする。何通りの方法があるか。
• ただし各 B, W 同士は連結じゃないといけない。あと同じ行/同じ列内では B-W-B とか W-B-W になっちゃだめ。
• W, H ≦ 50

• ...
• B と W でなんか境界線が引けそうだ
• なんか自由度がありすぎてどう数えたらいいかわからん。
• ? を B/W と仮定してそこから他の ? が自動的に B/W に決まるなら全部決めて、仮定した直後と同じならその ? は他と独立なので 2 をかけて残りを計算... かなと思いつつ終了

• あとで
• flowlight さんの回答がシンプルで美しい
• 他人様の 500 を勝手に解説するシリーズ

• 左 B 右 W となるように境界線を定める。矛盾しないような境界線が何本ひけるか数える。
• ただし、重複を数えないようにするため、境界線は下か左にしか曲がらないものとする。また、縦にまっすぐな境界線は除く。また、縦が１行しかない場合も除く。
• カウントは DP で。dp[境界線の行][境界線の列][これまで（ここを含めて上の行全部）が真っ直ぐかどうか] == その行/列から始まるそれ以降の行の境界線の個数
• これを90度ずつ回転させて４回行う
• さらに全部 W か B にできるならそれぞれ 1 ずつ足す

• これは思いつかないというか これで漏れ/重複がないかどうかもよくわからない
• 境界線 → 解の構造からしてDPで求められる くらいは気づくべき

↓実装練習 (passed system test in practice room)

(...)
#define VS vector<string>
#define VI vector<ll>
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll> > >
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i)

#define MOD 1000000007LL

int W, H;
VS rot(const VS& g) {
	VS o(W, string(H, '?'));
	REP(y, H) REP(x, W) o[W-1-x][y] = g[y][x];
	return o;
}

VVVI dp;
ll f(int y, int splitx, int co, const VS& g) {
	if(y==H) return co;
	if(dp[y][splitx][co]!=-1) return dp[y][splitx][co];
	ll ans = 0;
	REP(ns, splitx+1) {
		int ok=1;
		RANGE(x, 0, ns) if(g[y][x]=='W') ok=0;
		RANGE(x, ns, W) if(g[y][x]=='B') ok=0;
		if(!ok) continue;
		ans += f(y+1, ns, co || (0<y && ns < splitx), g);
		ans %= MOD;
	}
	return dp[y][splitx][co]=ans;
}

ll all_(char notc, VS& g) {
	ll ok=1;
	REP(y, H) REP(x, W) if(g[y][x]==notc) ok=0;
	return ok;
}

class TwoConvexShapes {
	public:
	int countWays(vector <string> g) {
		W=g[0].size();
		H=g.size();
		ll ans = all_('B', g)+all_('W', g);
		REP(loop, 4) {
			W=g[0].size();
			H=g.size();
			dp = VVVI(H, VVI(W+1, VI(2, -1)));
			ll r = f(0, W, 0, g);
			cout<<r<<endl;
			ans += r;
			ans %= MOD;
			g = rot(g);
		}
		return ans;
	}
};

ツイートする