AtCoder ARC #021 : A - DEAD END、B - Your Numbers are XORed...

ARC021に参加。
AでFirst Answerを獲得、Bも順調に進むもCのオーバーフローで苦しみ微妙な順位に。
http://arc021.contest.atcoder.jp/tasks/arc021_1
http://arc021.contest.atcoder.jp/tasks/arc021_2

A - DEAD END

ゲーム2048を題材にした問題。
4x4のグリッド上に2の累乗の数値が配置されている。
上下左右いずれかの方向に対し盤面を傾けたとき、その向きに隣接するセル同士が同じ数字ならそれらは合体する。
初期状態が与えられたとき、いずれかに傾けることで盤面の状態を変えられるか答えよ。

上下左右いずれかの隣接マスに同じ数字があるかチェックすればよい。

int A[4][4];

void solve() {
	int f,i,j,k,l,x,y;
	int cont=0;
	
	FOR(y,4) FOR(x,4) cin>>A[y][x];
	FOR(y,4) FOR(x,3) if(A[y][x]==A[y][x+1]) cont++;
	FOR(y,3) FOR(x,4) if(A[y][x]==A[y+1][x]) cont++;
	if(cont) _P("CONTINUE\n");
	else _P("GAMEOVER\n");
} 

B - Your Numbers are XORed...

L要素の整数列Aがあったとする。
ここから同じ長さの整数列BをB[i]=A[i] xor A[(i+1)%L] で生成したとする。
Bが与えられたとき、そのようなBを生成できるAのうち辞書順最小のものを答えよ。

A[0]を決めれば、A[1]=B[0]^A[0]、A[2]=B[1]^A[1]…A[L-1]=B[L-2]^A[L-2]よりAの各要素が求まる。
さらに最後A[0]=B[L-1]^A[L-1]が満たせればよい。

辞書順最小であればA[0]=0としたうえでA[1]～A[L-1]を求めるだけで良い。
A[0]=0の時はA[0]=B[L-1]^A[L-1]が満たせないが、A[0]>0でA[0]=B[L-1]^A[L-1]が定まるのでは？と思うかもしれないが、A[0]=B[L-1]^A[L-1]の可否はA[0]の値には依存しない。

というのもB[0]^B[1]^B[2]...^B[L-1]=(A[0]^A[1])^(A[1]^A[2])^(A[2]^A[3])...^(A[L-1]^A[0])=(A[0]^A[0])^(A[1]^A[1])^...(A[L-1]^A[L-1])=0であり、結局Bの各要素を2進数表記したとき、各ビットの数が偶数ならA[0]が何でもA[0]=B[L-1]^A[L-1]が成り立ち、奇数なら成り立たない。

int L;
ll B[100001];
ll A[100001];
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>L;
	FOR(i,L) cin>>B[i];
	for(i=1;i<L;i++) A[i]=A[i-1]^B[i-1];
	
	if(A[L-1]!=B[L-1]) {
		_P("-1\n");
	}
	else {
		FOR(i,L) _P("%lld\n",A[i]);
	}
}

まとめ

ここまでは順調。