問題C『+/- Rectangle』 : AtCoder Grand Contest 016

問題文 : +/- Rectangle

概要

の盤面に整数を書き込んで、次の条件を満たすようにできるか？できるなら具体的に作れ。

• の大きさの部分長方形を任意に取ってくると、その中での総和は必ず負
• 盤面全体の総和は正

制約

解法

全体を部分長方形で埋めつくせれば明らかに不可能。
そうでないとき、またはである。必要に応じて転置し、以下ではとする。
1次元の場合、つまり、

長さの数列で、全体の総和は正であり、長さの連続する部分列の総和はいずれも負である

が解けたとする。この数列を列だけ並べれば元の問題の解になっている。
例えば、のとき、1次元だけ考えると

が答え。すると、

が答えになる。

実は、1次元の場合は、以下のように必ず解を持つ。

とする()。長さの数列をとする(を個並べ、を個並べる)。
これを個並べて、後ろにを個並べて、長さの数列にする。
として、をうまく調節すると解が作れる。

具体的には、のとき、で

のようになる。このとき、守るべき条件はだが、
を仮定すると簡単になって、でよい。
これは、例えばとするとよい。実際には整数を並べるので、

が解。

一般化して、

を解けばよく、
だけ見るととなる。よって、とする。
このとき、が必要で、とする。
あとは、分母をはらって並べれば良い。

計算量はとなる。
各要素の大きさは高々なので、を超えない。

ソースコード

using System;
using System.IO;
using System.Linq;
class Z { static void Main() { new K(); } }
class K
{
	public K()
	{
		Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Console.Out.Flush();
	}
	void Solve()
	{
		var I = Console.ReadLine().Split().Select(int.Parse).ToArray();
		int H = I[0], W = I[1];
		var t = YesNo(H, W, I[2], I[3]);
		if (t == null) Console.WriteLine("No");
		else
		{
			Console.WriteLine("Yes");
			for (var h = 0; h < H; h++)
			{
				for (var w = 0; w < W; w++) Console.Write("{0}{1}", t[h, w], w == W - 1 ? "" : " ");
				Console.WriteLine();
			}
		}
	}
	T[,] Swap<T>(T[,] t)
	{
		var Y = t.GetLength(0);
		var X = t.GetLength(1);
		var t2 = new T[X, Y];
		for (var x = 0; x < X; x++) for (var y = 0; y < Y; y++) t2[x, y] = t[y, x];
		return t2;
	}
	int[,] YesNo(int H, int W, int h, int w)
	{
		if (H % h == 0 && W % w == 0) return null;
		if (H % h == 0) return Swap(YesNo(W, H, w, h));
		int r = H % h, s = h - r, N = H / h, a = s * (2 * N + 1), b = 2 * r * (N + 1), x = s * (N + 1);
		var t = new int[H, W];
		for (var y = 0; y < W; y++)
		{
			for (var i = 0; i < N; i++)
			{
				for (var j = 0; j < r; j++) t[i * h + j, y] = a;
				for (var j = r; j < h; j++) t[i * h + j, y] = -b;
			}
			for (var i = N * h; i < H; i++) t[i, y] = x;
		}
		return t;
	}
}

サンプルがの場合しかなくて、じゃなくてだと勘違いしていた…。