第14回日本情報オリンピック　予選３

2014年12月14日
情報オリンピック日本委員会

解説

小区画 (i, j) の上空に初めて雲が現れるまでの分単位の時間は，北から i 番目の雲がある小区画のうち，西から j 番目より西にあり，最も小区画 (i, j) に近いものから，小区画 (i, j) までのキロメートル単位の距離に等しい．

この答えは以下のようなやり方で求められる． 北から i 番目の小区画を西から東へ見ていき，最後に雲があった場所を覚えておく．小区画 (i, j) の答えは，j まで見た時に最後に雲があった小区画から (i, j) までの距離となる．

また，W 分の間，雲がどの小区画に存在するかをシミュレートしても解くことができる．

JOI 市全体の雲の位置を覚えて，1 分経つと雲の場所を 1 つ東に動かす．ある小区画の上に初めて雲が現れたら，その時刻を記録する．W分経つとすべての雲は JOI 市から外へ出ていき，これ以降雲が JOI 市の上空へ出てくることはないため，W 分間のシミュレーションをすれば十分である．

どちらのやり方でも，雲が小区画を一度も覆わなかったときは，-1 がその小区画に対する答えとなること，初めから小区画の上空に雲があるときは 0 が答えとなることに注意．