kmjp's blog

競技プログラミング参加記です

AtCoder AGC #030 : C - Coloring Torus

うーむ、近いところまで行ったのに。
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の倍数にするまでは思いつけたのに、そこから詰め切れなかった。