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); }