JOI '08 春合宿１：３- Flu インフルエンザ
問題
https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day1_20.pdf
解法
k 日目までに感染の広がる様子をシミュレーションする．流行している都市から感染が拡大する範囲が d <= 25 と狭いので，現在流行している都市それぞれを中心とする一辺が 2 * d の正方形内にある都市を探す．ある座標に都市があるかどうかは逆配列等を用いて O(1) で求めることが出来る．正方形内にある都市のうち，正方形の中心の都市から距離が d 以内であり，まだ感染していないものに感染が拡大する．次の日はこれらの都市について同様に処理すればよい．それぞれの日で新たに流行した都市は問題文の制約より高々 10 しかないので，このシミュレーションは十分間に合う．これによって各都市について感染する日が分かったので，k 日目に各都市で流行しているかどうかが分かる．O(k * d^2 + n)．
解答
