AOJ 2600 Koto Distance
センター試験まで1週間です。
気分転換に解いた
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2600
解法
imos法を使ってカバーできているかどうか調べる。
コーナーケースがあって、マスの辺はカバーできているけど中身がカバーできていないというケースがある。
そのためグリッドの幅、高さを2倍して内部も表すことができるようにする。
import std.stdio; import std.string; import std.algorithm; import std.conv; import std.range; void main(){ int N,W,H; int[] input = array(map!(to!int)(split(readln()))); N = input[0]; W = input[1]; H = input[2]; int[] Hb = new int[2*H+2]; int[] Wb = new int[2*W+2]; foreach(i; 0..N){ int x, y, w; int[] xyw = array(map!(to!int)(split(readln()))); x = 2*xyw[0]; y = 2*xyw[1]; w = 2*xyw[2]; Hb[max(y-w,0)] += 1; Hb[min(y+w+1,2*H+1)] -= 1; Wb[max(x-w,0)] += 1; Wb[min(x+w+1,2*W+1)] -= 1; } bool f = true, g = true;; if(Wb[0] == 0) f = false; foreach(x; 1..(2*W+1)){ Wb[x] = Wb[x-1] + Wb[x]; if(Wb[x] == 0){ f = false; } } if(Hb[0] == 0) g = false; foreach(y; 1..(2*H+1)){ Hb[y] = Hb[y-1] + Hb[y]; if(Hb[y] == 0){ g = false; } } if(f || g){ writeln("Yes"); }else{ writeln("No"); } }