うーむ、近いところまで行ったのに。
https://atcoder.jp/contests/agc030/tasks/agc030_c
問題
N*Nのグリッドに、1~Kの値を書き込む。
この際以下の条件を満たすようにしたい。
- 1~Kは最低1回は登場する。
- ある数字iが書き込まれたすべてのマスにおいて、隣接マス4つ(上下左右は循環しているとみなす)における他の数字の登場回数は一致する。
1000以下のKが与えられたとき、500以下のNを任意に選び、条件を満たすものを構築せよ。
解法
Kが500以下なら単純である。
位置(r,c)に(r+c)%K+1を書けばよい。
これを少しアレンジする。Kが4の倍数であるとき、N=K/2としよう。
奇数行目は(r+c)%N+1、偶数行目は(r+c)%N+1+Nを書くと条件を満たす。
これだとKの半分のNで済む。
問題はKが4の倍数でない場合である。
この場合、まずはKをK以上の最小の4の倍数にround upし、同様に処理しよう。
その後、元のKからはみ出る部分を、N小さい値に書き換えても条件を満たせる。
int K; int N; void solve() { int i,j,k,l,r,x,y; string s; cin>>K; if(K==1) { cout<<1<<endl; cout<<1<<endl; return; } int step=((K+3)/4)*4; N=step/2; cout<<N<<endl; FOR(y,N) { FOR(x,N) { r=(x+y)%N; if(y%2) r+=N; if(r>=K) r-=N; cout<<(r+1)<<" "; } cout<<endl; } }
まとめ
Kを4の倍数にするまでは思いつけたのに、そこから詰め切れなかった。