TopCoder SRM 720 Div1 Medium DistinctGrid

これMediumなのか…と思いたいが落としたので文句も言えない。
https://community.topcoder.com/stat?c=problem_statement&pm=14594

問題

以下の条件を満たすN*Nの行列を構成せよ。

• 各行・列にはちょうどK種類の数値が登場する。
• 全体でdistinctな数値の種類を最大化する。

解法

色々解法がありそうなConstruction問題なので1例を紹介。
A[y][x]には、(y*N+(N-y)+x)＜K-1なら新規の値、そうでなければ0を埋めていこう。
N=6、K=3のとき以下のようになる。

120000
034000
005600
000780
00009A
C0000B
class DistinctGrid {
	public:
	vector <int> findGrid(int n, int k) {
		int x,y,p=1;
		
		vector<int> V;
		FOR(y,n) {
			FOR(x,n) {
				if((y*n+(n-y)+x)%n<k-1) V.push_back(p++);
				else V.push_back(0);
			}
		}
		return V;
	}
}


    
まとめ
    正答者数見てもこっちEasyでよかったんじゃ。