AtCoder AGC #006 : E - Rotate 3x3

本番はこの前の問題で時間切れして問題すら見られなかった。
http://agc006.contest.atcoder.jp/tasks/agc006_e

問題

縦3×横Nのマスがあり、初期状態では1～3Nの数字がrow-major orderで一つずつ書かれている。
ここで3*3の矩形区間を選択し、マス目を180度回転するという作業を繰り返す。

終了状態の数値配列が与えられる。
上記作業を繰り返し、与えられた終了状態にできるか判定せよ。

解法

終了状態について、各列３つの数値が昇順か降順に並んでいなければいけないのは明らかなので、それは先に判定しておく。
また、各列は回転により２列ごとしか左右に移動できないので、初期状態と終了状態で奇数列差がある場合は成立しないのも明らか。

3*3の矩形を反転するという作業は、左右の列を入れ替えたうえで全体を上下反転させる作業につながる。
上下反転をシンプルにするため、初期状態および終了状態を２列おきに上下反転させておこう。
こうすると左右列の上下判定を以降無視できる。

あとは中央列の上下反転の有無だけを考えればよい。
作業を１回行うと左右列の反転数が１増減し、上下反転数も１増減する。
よって列の反転数および上下の反転数の偶奇をそろえることを考えよう。

奇数列の終了状態の反転数の偶奇と偶数列の上下反転列数の偶奇、および偶数列の終了状態の反転数の偶奇と奇数列の上下反転列数の偶奇を調べ、ともに一致すれば条件を満たす。

int N;
map<ll,int> M[2];
ll A[3][101010];
vector<ll> V[2];
int RP[2];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};

ll array_inv(vector<ll> V) {
	static BIT<int,18> bt;
	ZERO(bt.bit);
	int x=0,i;
	map<ll,int> M;
	vector<int> V2;
	
	M[-1LL<<60]=0;
	FORR(r,V) M[r]=0;
	FORR(r,M) r.second=x++;
	ll ret=0;
	for(i=V.size()-1;i>=0;i--) {
		ret += bt(M[V[i]]);
		bt.add(M[V[i]],1);
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[0][i];
	FOR(i,N) cin>>A[1][i];
	FOR(i,N) cin>>A[2][i];
	
	FOR(i,N) {
		ll P=1+i*3, Q=P+1, R=Q+1;
		if(i%4>=2) swap(P,R);
		M[i%2][(P<<40)+(Q<<20)+R]=i/2;
	}
	FOR(i,N) {
		if(i%4>=2) swap(A[0][i],A[2][i]);
		ll k1=(A[0][i]<<40)+(A[1][i]<<20)+A[2][i];
		ll k2=(A[2][i]<<40)+(A[1][i]<<20)+A[0][i];
		if(M[i%2].count(k1)) V[i%2].push_back(M[i%2][k1]);
		else if(M[i%2].count(k2)) V[i%2].push_back(M[i%2][k2]), RP[i%2]^=1;
		else return _P("No\n");
	}
	
	if(array_inv(V[0])%2!=RP[1] || array_inv(V[1])%2!=RP[0]) return _P("No\n");
	_P("Yes\n");
	
}

まとめ

これは本番思いついたかなぁ…？