kmjp's blog

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

第二回全国統一プログラミング王決定戦予選 : F - Mirror Frame

その他コンテスト

思ったより複雑だった。
https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_f

問題

(0,0)-(N,N)を通る軸に平行な辺で囲まれた正方形領域を考える。
(1,1)-(N-1,N-1)までの、正方形内部の(N-1)^2個の格子点の位置に電球があるとする。

どれか1個電球を指定すると、そこから軸と45度傾いた向き4方向に光線が出るものとする。
この光線は正方形の境界で反射する。
この時、この光線が通過した正方形内部の格子点において、電球のon/offが反転する。

全電球のon/off状態が与えられる(一部は不定である)。
ここから、上記操作を繰り返して全電球をoffにできるような状態は何通りか答えよ。

解法

まず、各電球のon/offを切り替えるのは、(x,0)をうちどこを通る光線かを列挙し、電球を分類しよう。
各電球は、X軸上で2つの座標を通る。またその時その偶奇が一致する。

あとは、上記座標で偶数のX座標を通るものと奇数のX座標を通るものそれぞれで考える。
ある電球を指定してon/offを切り替える場合、その電球が(a,0)と(b,0)を通る光線が通過するとすると、ほかに(a,0)または(b,0)のいずれかを通る電球のon/offが切り替わることになる。

これを別の問題として考える。
今前述の分類で光線の通るX座標が偶数の物だけ考えるとする。
0～Nのうち偶数に対応して頂点をもつグラフを考える。
今(a,0),(b,0)を通る電球があるとすると、このグラフでa-b間に辺を張る。
その時、電球のon/offは辺のon/offに相当する。

電球を指定するとは、aまたはbいずれかを端点とする全辺のon/offが切り替わることに相当する。
この時、この操作を繰り返して全辺offにできるような状態の組み合わせを考える。
まず、頂点数が偶数の時、常にそのような遷移が可能である(らしい。Editorialによると。)。
なので状態未確定の辺がk個あるなら、2^k通りの組み合わせが許容される。

頂点数が奇数の場合、電球を指定する操作は常に各点を端点とするon/offは偶数個変化する。
さらに、全点につながるonの電球数が偶数であれば、全辺offにできる。
あとはこの状態を数え上げよう。
状態不定の辺でつながる連結成分を考える。
まず連結成分外の辺に関し、各点につながるonの辺の数を数えよう。これらは偶数でなければならない。

あとは各連結成分について考えるのだが、p個の頂点でq辺があるとき、木を成すような(p-1)辺さえ残っていれば端から順に偶奇を合わせることができるので、残り(q-(p-1))辺のon/offはどうでもよい。
よって2^(q-(p-1))通りの状態が許容される。

int N;
string S[1515];
int M[2][1515][1515];

int id[1515][1515];
ll mo=998244353;
int V[1500],E[1500],P[1500];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

ll hoge(int t,int N) {
	int a,b;
	ll pat=1;
	if(N%2==0) {
		FOR(b,N) FOR(a,b) pat=pat*(2-__builtin_popcount(M[t][a][b]))%mo;
	}
	else {
		UF<1510> uf;
		FOR(b,N) FOR(a,b) {
			if(M[t][a][b]==3) return 0;
			if(M[t][a][b]==0) uf(a,b);
		}
		ZERO(V);
		ZERO(E);
		ZERO(P);
		FOR(a,N) {
			V[uf[a]]++;
			FOR(b,a) if(M[t][b][a]==0) E[uf[a]]++;
		}
		FOR(a,N) FOR(b,a) if(M[t][b][a]==2) {
			P[uf[a]]^=1;
			P[uf[b]]^=1;
		}
		FOR(a,N) if(uf[a]==a) {
			FOR(b,E[a]-(V[a]-1)) pat=pat*2%mo;
			if(P[a]) return 0;
		}
		
	}
	return pat;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(y=1;y<=N-1;y++) {
		cin>>S[y];
		for(x=1;x<=N-1;x++) {
			int a=abs(x-y);
			int b=x+y;
			if(b>N) b=2*N-b;
			assert(a<=b && (a%2==b%2));
			if(S[y][x-1]=='o') M[a%2][a/2][b/2]|=1;
			if(S[y][x-1]=='x') M[a%2][a/2][b/2]|=2;
		}
	}
	
	ll ret=hoge(0,1+N/2)*hoge(1,(N+1)/2)%mo;
	cout<<ret<<endl;
	
}

まとめ

ここまで自力で考察できる気がしないなぁ…。