SRM720 Lv2 : DistinctGrid
作成日：2017.08.31
最終更新日：2017.08.31
問題概要
$n \times n$のマス目に整数を書き込む。
この時、各列及び各行に書かれている異なる整数は高々$k$種類となるようにし、マス目全体に書かれている異なる整数の種類は最大になるようにする。
条件を満たす書き込み方の1つを求め、$i$行$j$列に書き込む数を$i \times n + j$番目の要素とする配列を答えよ。
制約
$3 \leq n \leq 50$
$1 \leq k \leq n/2$
考え方
$k=1$の時はすべてのマス目に同じ数($0$とする)を書き込むしかない。
以下これを基準に考える。
$k$が$1$増加するごとに各列及び各行に書き込める異なる数の種類は$1$増加する。
またマス上にまだ書かれていない数のうち最も小さい正の数(一般性を失わない)をあるマス目の$0$と置き換えると、いずれかの列及び行に書き込まれた異なる数の種類は必ず$1$増加する。
さらにすでに書き込まれている数をあるマス目の数と置き換えることでは、その数がなくならない限り列及び行に新たに加えることができる異なる数の種類は増えない。
その上、ある数が置き換えられたことでマス上にその数が書き込まれていない状態になった時その数より大きい数を$1$ずつ減らすことを考えると、そのような状況を起こさなくても最善の書き込み方が得られることが分かる。
以上より、$0$と置き換える数はマス上でまだ書かれていない数に限って良く、そのような置き換えができるのは高々$n(k-1)$回である。
最大の置き換え数を達成した時、各行及び各列に$0$でない数が$k-1$個ずつ存在している。
そのような配置は1番上の行のあるマス目から斜め(両端はつながっているとみなす)に$n$個置き換えていくことを$k-1$回繰り返せば達成できる。
ソースコード
マクロ等はこちら
class DistinctGrid {
public:
vector<int> findGrid(int n, int k) {
vector<int> ans(n*n);
fill(ans.begin(),ans.end(),0);
int c = 0;
repp(i,0,k-1){
repp(x,0,n){
ans[x*n+(x+i)%n] = ++c;
}
}
return ans;
}
};解法まとめ
$x$行$(x+i)$列$(0 \leq x < n , 0 \leq i < k-1 , mod \: n)$のマス目には$0$でない互いに異なる数、
それ以外のマス目には$0$を書き込む。(5-11行)
SRM720の他の問題 Lv1 Lv3