kmjp's blog

競技プログラミング参加記です

CODE FESTIVAL 2017 Qual A : E - Modern Painting

その他コンテスト

これは落ち着いて考えるとそこまで難しくなかったが、Dで手間取りすぎて本番中は無理。
http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_e

問題

H*Wの２次元グリッドがあり、各マスは初期状態で白である。
さて、外周マスの外側の一部に人がおり、辺に垂直な向きでグリッドに入るよう向いている。

これらの人がランダムな順で動くことを考える。
人が動き出すと、移動先のマス目が白いか、反対側の外周に到達するまでマスを辿り、自分の色で塗っていく。
さて、最終的な色の塗り分け方は何通りか。

解法

以下最初に縦に塗る場合のみ考える。最初に横に塗る場合は、全体を90度回転させて同様に考えればよい。
縦で上から下、もしくは下から上まで塗り切れるもっとも左の列をL、右の列をRとする。
(L,R)を総当たりしつつ、L列の左側と、R列の右側の塗り分け方の積を取れば求める解が得られる。
また、(L,R)の間の列に上下両方とも移動可能な人がいる列があれば、その数だけ全体の組み合わせは倍になる。
以下左側について考えよう。

L列より左に縦移動できる人が１人もいない場合は1通り。
また、左に右移動できる人がおらず、縦移動できる人がいる場合は0通りである(L列が上から下まで移動できるもっとも左側の列なので、それ以上縦移動できる人が左にいてはならない)
よって以降は左に右移動できる人が１人以上いる場合を考える。

この場合、先ほどと同じように、左からL列目まで右に移動する人を総当たりすることが考えられるが、これを愚直に行うとTLEする。
よってそのような組み合わせをもっと高速に計算することを考える。
左端にいる人がどこまで右に塗れるかを考えると、上の行から順に単純増加し、いずれ１人以上L列目まで到達する人がいて、またその後単調減少することになる。
これは人のいる列・行で座標圧縮すると、よくある格子点を右か下だけ移動する経路を求める問題となり、Combinationで計算できる。
今回は左右方向についてはL列目まで行って戻るが、これは合計で2L列移動すると考えればよい。

こうしてL列より左側、R列より右側の組み合わせを求めよう。
実際は(L,R)を総当たりするとそれだけでTLEするので、Lに対しRを動かしたときの累積和を求めるようにするとよい。

int H,W;
string A,B,C,D;
ll mo=998244353;

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll modpow(ll a, ll n=mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll L[101010],R[101010],P[101010],RS[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>A>>B>>C>>D;
	FORR(c,A) c-='0';
	FORR(c,B) c-='0';
	FORR(c,C) c-='0';
	FORR(c,D) c-='0';
	s=A+B+C+D;
	
	if(count(ALL(s),1)==0) return _P("1\n");
	ll ret=0;
	FOR(i,2) {
		ZERO(L);
		ZERO(R);
		ZERO(P);
		ZERO(RS);
		
		int NL=count(ALL(A),1);
		int NR=count(ALL(B),1);
		int NT=0,NB=0;
		P[0]=1;
		FOR(x,W) {
			if(C[x]==0 && D[x]==0) {
				L[x+1]=0;
			}
			else if(NL==0) {
				if(NT+NB==0) L[x+1]=1;
				else L[x+1]=0;
			}
			else {
				L[x+1] = combi(NT+NB+NL-1,NL-1);
			}
			P[x+1]=P[x];
			if(C[x]&&D[x]) P[x+1]=2*P[x]%mo;
			NT+=C[x];
			NB+=D[x];
		}
		NT=0,NB=0;
		for(x=W-1;x>=0;x--) {
			if(C[x]==0 && D[x]==0) {
				R[x+1]=0;
			}
			else if(NR==0) {
				if(NT+NB==0) R[x+1]=1;
				else R[x+1]=0;
			}
			else {
				R[x+1] = combi(NT+NB+NR-1,NR-1);
			}
			(R[x+1]*=P[x+1])%=mo;
			(RS[x+1]=RS[x+2]+R[x+1])%=mo;
			
			(ret += (C[x]+D[x])*L[x+1]*RS[x+1]%mo*modpow(P[x+1]))%=mo;
			
			NT+=C[x];
			NB+=D[x];
		}
		
		
		swap(H,W);
		swap(A,C);
		swap(B,D);
	}
	cout<<ret<<endl;
	
}

まとめ

これ説明がすごく面倒で、手を動かしながらでないと理解できないと思う…。
Combinationにで計算する部分は幸い自分でうまく思いつけた。