kmjp's blog

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

AtCoder AGC #016 : C - +/- Rectangle

サンプルにやられた人多そう。
http://agc016.contest.atcoder.jp/tasks/agc016_c

問題

H×Wの2次元グリッドの各セルに-10^9~10^9の範囲の整数を埋める。
この時以下の条件を満たすグリッドを構成せよ。

  • 全セルの総和は正である。
  • h×wの矩形領域を選ぶと、その内部のセルの総和は負である。

解法

サンプルをうのみにして、
「h*w毎に区切って、角に-h*w、残り1を書くといいんじゃない?」
とやると失敗する。
この時の状況を考えると、h*wの領域ごとに総和が-1になり、余ったセルの分だけ+1になる。
よってh*wの矩形領域を取れる数が余ったセルより多いと全体が負になってしまう。

そこでどうするか。
余ったセルのプラス分ができるだけ大きくなるようにしよう。

aを((h*w-1)*a+1)が10^9を超えない最大の整数とする。

h*w毎に区切って、角に-((h*w-1)*a+1)を配置し、それ以外aを配置しよう。
こうするとh*wの領域ごとに総和が-1になり、余ったセルの分だけ+aになる。
aが2以上なら先ほどの例よりも全体の総和を正にしやすいのがわかるはず。

int H,W,h,w;
int G[505][505];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>h>>w;
	if(h==1&&w==1) return _P("No\n");
	ll sum=0;
	ll mul=999999999/(h*w-1);
	FOR(y,H) {
		FOR(x,W) {
			G[y][x]=mul;
			if((y%h==h-1) && (x%w==w-1)) G[y][x]=-mul*(h*w-1)-1;
			sum += G[y][x];
		}
	}
	
	if(sum<=0) return _P("No\n");
	_P("Yes\n");
	FOR(y,H) FOR(x,W) _P("%d%c",G[y][x],(x==W-1)?'\n':' ');
	
	
}

まとめ

強い人も結構サンプルにやられてる。