Topcoder SRM 720 Div1 Medium - DistinctGrid
問題概要
与えられる整数n, kに対して、各行・各列をみたとき異なる数がちょうどk個存在するようなn * nのグリッドを構成せよ。解が複数ある場合は使われる数の種類が最大になるものを答えること。
3 <= n <= 50
1 <= k <= n/2
解法
1 2 3 0 0 0 0 4 5 6 0 0 0 0 7 8 9 0 0 0 0 10 11 12 15 0 0 0 13 14 17 18 0 0 0 16
証明についてはこどふぉに貼ってあったpdfが参考になった(一番下の問題)。要するに↑の形より一個でも多くの違う数を入れようとすると矛盾が起きるので背理法でokということになるらしい。
感想
これでいいの?と思って投げたら通ってこれでいいの?ってなった
コード (C++)
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; class DistinctGrid { public: vector<int> findGrid(int n, int k) { vector<int> ans = vector<int>(n * n, 0); int num = 1; REP(i, n) REP(j, k-1) { ans[i * n + (i+j) % n] = num++; } return ans; } };