JOI2010春合宿Day4 プラグ(Plugs)

まだ僕には早かったです。

問題

http://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day4_23.pdf

ジャッジ

Welcome to 2010年日本情報オリンピック春合宿OJ - 2010年日本情報オリンピック春合宿OJ | AtCoder

解法

各ソケットと各プラグの対応(入るかもしれないか、絶対に入らないか)を示す二次元の表をつくると、問題で与えられる証言の範囲は長方形になります。
そこで、imos法を使って証言で与えられた範囲を $O(N^2 + M)$ (愚直に塗ると $O(N^2M)$ )で塗りつぶします。

まず、あるソケットまたはプラグの相手が一意に定まるならば、他のN-1個の相手とは明らかにはまりません。
この問題では対応が一意に定まることが保証されているので、全てのソケットまたはプラグについて、N-1個の相手とはまらないと必ずわかるということです。

あとは相手の分かるソケットまたはプラグを順番に見ていけばよいです。
相手の分かるプラグかソケットより、新たに相手の分かるプラグかソケットを探してくるのに $O(N)$ 、それをN回やるから $O(N^2)$ です。

前処理のimos法と合わせても $O(N^2 + M)$ で通るのですが、解いたあとでググったら実はもっと頭のよいやり方がありました。

ソケットとプラグ、つまり対応表の縦も横も見るまでしなくても、実は縦か横だけをずっと見ていれば解が求まるらしいです。実装が楽になり、かっこいいです。

適当な証明(間違っているかも)

解が1つ求まった時は対応表の行と列がそれぞれ1つずつ消えるので、N-1の問題に帰着されます。(これを1回の操作とします)
また、「相手の分かるプラグ」またはソケットとは、"N-1個の相手とははまらない"と操作をせずともすぐに分かるものとします。

さて、初期状態が、相手の分かるソケットが存在するが、相手の分かるプラグは存在しない状態だとします。
操作をするとN-1の問題の初期状態に帰着されることから、この状態が存在しないと言えれば、ソケット側かプラグ側だけをずっと見るアルゴリズムはうまくいくことが分かります。

あるソケットを見て相手のプラグが分かることによって、新たに相手の分かるソケットが現れるかもしれません。
しかし、プラグ側については、新たに相手の分かるプラグが現れることはありません。
よって、初期状態に相手の分かるプラグがいない場合、以降の操作では、相手の分かるプラグは絶対に現れません。

つまり、最後の操作でも相手の分かるプラグがないということですが、N個ずつのプラグとソケットを1つずつ消していくと最後には1対1のプラグとソケットが絶対に残るので、矛盾してしまいます。(2個以上のソケットと1個のプラグを残すことはできない)
相手の分かるプラグだけが存在する状態についても同じ証明ができます。

すごく回りくどい証明になっている気がします。。。

実装

頭悪い方のアルゴリズムです。相手の分かるソケットまたはプラグを頑張ってqueueに詰めています。

using namespace std;
 
const int MAX_N = 3000, MAX_M = 100000;
 
struct Data
{
	int id, cnt;
	Data() {}
	Data(int _id, int _cnt)
	{
		id = _id; cnt = _cnt;
	}
	bool operator < (const Data &a) const
	{
		return cnt > a.cnt;
	}
};
 
int N, M;
int sum[MAX_N + 1][MAX_N + 1], cnt[MAX_N*2];
 
signed main()
{
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--; b--; c--; d--;
		sum[a][c]++; sum[a][d + 1]--;
		sum[b + 1][c]--; sum[b + 1][d + 1]++;
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 1; j < N; j++)
		{
			sum[i][j] += sum[i][j - 1];
		}
	}
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			sum[i][j] += sum[i - 1][j];
		}
	}
	queue<Data> q;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (sum[i][j] != 0) continue;
			cnt[i]++;
			cnt[j + N]++;
		}
	}
	for (int i = 0; i < N*2; i++)
	{
		if(cnt[i] == 1) q.push(Data(i, cnt[i]));
	}
	int ans[MAX_N];
	while (!q.empty())
	{
		Data t = q.front(); q.pop();
		if (t.cnt != cnt[t.id]) continue;
		if (t.id < N)
		{
			for (int i = 0; i < N; i++)
			{
				int socket = t.id, plug = i;
				if (sum[socket][plug] != 0) continue;
				sum[socket][plug] = -1;
				cnt[socket] = cnt[plug + N] = 0;
				ans[socket] = plug;
				for (int j = 0; j < N; j++)
				{
					if (sum[j][plug] != 0) continue;
					sum[j][plug] = -1;
					if(--cnt[j] == 1) q.push(Data(j, cnt[j]));
				}
			}
		}
		else
		{
			for (int i = 0; i < N; i++)
			{
				int socket = i, plug = t.id - N;
				if (sum[socket][plug] != 0) continue;
				sum[socket][plug] = -1;
				cnt[socket] = cnt[plug + N] = 0;
				ans[socket] = plug;
				for (int j = 0; j < N; j++)
				{
					if (sum[socket][j] != 0) continue;
					sum[socket][j] = -1;
				    if (--cnt[j + N] ==1) q.push(Data(j + N, cnt[j + N]));
				}
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		printf("%d\n", ans[i] + 1);
	}
	return 0;
}

4bitにっき

ぽよ

JOI2010春合宿Day4 プラグ(Plugs)

問題

ジャッジ

解法

適当な証明(間違っているかも)

実装