Google Code Jam 2016 Round1A : B. Rank and File

無駄に苦戦した…。
https://code.google.com/codejam/contest/4304486/dashboard#s=p1

問題

N*Nの行列がある。
各行及び各列の要素はそれぞれ左から右または上から下に、真に単調増加な順で並んでいる。

各行及び各列の数字を列挙したN要素の数列はN行N列で計2N個作れるはずである。
うち(2N-1)個が与えられるので、残り1個を求めよ。

解法

最初マジメに数列を置いたり並べ替えたりしてWA繰り返した。

考え方を変えると非常に簡単になる。
2N個の数列中には、各値は偶数回しか登場しない。
また、各数列には同じ要素は1回しか登場しない。
よって、入力の(2N-1)個の数列中のうち、奇数回しか登場しない値を列挙すれば、それが残り1個の数列の要素になる。

int N;
int num[2525];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	ZERO(num);
	FOR(y,N*(2*N-1)) cin>>x, num[x]++;
	_P("Case #%d:",_loop);
	FOR(i,2520) if(num[i]%2) _P(" %d",i);
	_P("\n");
	
}

まとめ

最初なんでこんなみんなあっさり解けるんだと驚愕していた。