JOI春合宿 2010-day4 plugs

問題文 : プラグ

解法 :
n * nグリッドの真理値表を考える.
マス(i, j)は "プラグiがソケットjに使われるか"を表し, (i, j) が0ならtrue, それ以外ならfalseとする.
上の真理値表でM個の証言で示される長方形領域をすべて塗りつぶすが, その際にはいもす法 (JOI2012年本選4問目解説(5-11ページ目, pdf注意)を参照)を使う.

真理値表を埋めた後は次のようにして対応を求める.
真理値表から一意に答えが定まることが明示されているので, 少なくとも真理値表を埋めた時点で対応するソケットが1つだけのプラグがあるあずである.
そのような場所をみつけ, 真理値表を細かく作っていくと, すべてのプラグについて対応するソケットが1つだけになっていくので, すべての対応が求まる.

いもす法の部分をO(M+N^2)時間, 真理値表からプラグを対応される操作をO(N^2)時間で行なっているので, この解法はO(M+N^2)時間で動作する.

コード :

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	static int map[3001][3001];
	int N, M;
	int ans[3000], count[3000];
	
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < M; i++){
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		map[a - 1][c - 1]++;
		map[b][c - 1]--;
		map[a - 1][d]--;
		map[b][d]++;
		
	}
	
	for (int i = 0; i < N; i++){
		for (int j = 1; j < N; j++){
			map[i][j] += map[i][j - 1];
		}
	}
	
	for (int i = 1; i < N; i++){
		for (int j = 0; j < N; j++){
			map[i][j] += map[i - 1][j];
		}
	}
	
	for (int i = 0; i < N; i++){
		count[i] = 0;
		for (int j = 0; j < N; j++){
			count[i] += !map[i][j];
		}
	}
	
	bool update = true;
	while (update == true){
		update = false;
		for (int i = 0; i < N; i++){
			if (count[i] == 1){
				int j;
				for (j = 0; j < N; j++){
					if (!map[i][j]){
						ans[i] = j + 1;
						break;
					}
				}
				for (int k = 0; k < N; k++){
					count[k] -= !map[k][j];
					map[k][j] = 1;
				}
				update = true;
			}
		}
	}
	
	for (int i = 0; i < N; i++){
		printf("%d\n", ans[i]);
	}
	
	return (0);
}