TopCoder SRM 784 : Div1 Hard TAASquares

証明を試みるかどうかで難易度が変わる気がする。
https://community.topcoder.com/stat?c=problem_statement&pm=16111

問題

正整数Nが与えられる。
以下の条件を満たすN*Nの行列を構築せよ。

• 各要素は0,1,2のいずれかである。
• 各列の和と各行の和、計2N個の値において、uniqueなものの数が最大である

解法

サンプルが多分にヒントになっている。
Nが偶数の時は、各列の和と各行の和を1～2Nの2N通り構築できる。
例えばN=4のサンプルの列と行を並べ替えると、以下のようになりこの時点で法則が見える。

００｜０２
００｜２２
－－＋－－
０１｜２２
１２｜２２

Nが奇数の時、各列の和と各行の和は2N-1通りとなる。
証明はEditorial参照。
2N-1通りとなることが確定していれば構築は簡単で、(N-1)のケースについて上のように構築すれば1～(2N-2)の2N-2通りを構成できて、あと0だけの行と列を足せば、和が0となる行・列を加えられる。

class TAASquares {
	public:
	vector <string> construct(int N) {
		vector<string> S;
		int x,y;
		FOR(y,N) S.push_back(string(N,'0'));
		
		if(N%2) N--;
		FOR(y,N) {
			for(x=N-1-y;x<N;x++) S[y][x]='2';
			if(y>=N/2) S[y][N-1-y]='1';
		}
		
		return S;
	}
}

まとめ

本番中N=1,3,5は確認して、証明も試みたんだけどね…。