JOI2015-2016 予選参加記

気づけば今年もあと少し、JOI予選の季節です。
JOI2014-2015 春合宿に参加したので予選は免除されますが、自分の実力を確かめるため、また図書券を手に入れるために参加しました。

C++ソースコードの前提

next<T>(): T型の値を読み込む
next<vector<T>>(X): T型の値をX個読み込んでvector<T>に格納する
dout: デバッグ時のみcout
times(n, i): for(i = 0; i < n; i++)
upto(a, b, i): for(i = a; i <= b; i++)
minA(a, b): a = min(a, b)
全文: 競プロ用テンプレート(2015/11/23) · GitHub

模擬予選

540点だった。

5番まで1h18mしかかからなかったのに残り1h42mで6番を解けなかった。駄目。
6番の入力2は手で解くことの大切さを教えてくれた。

予選

まず4～6を読んだあと、1から順番に解いた。

4 おさんぽ事情

会話地点をリストアップして各Xについて二分探索。 $O ( N + Q \log N )$
必ず $A_i \not= A_j$ なので家から1m以上歩くことになり、lower_boundやupper_boundの細部は気にしなくていい。
f:id:akouryy:20151214002248p:plain

ソースコード

13:51

5 ことうぐらし！

幅探索→宿泊料金をコストにダイクストラ。 $O ( N + M log M )$
priority_queueへのpushを負値でやるタイプの人間。
シェルターは宿泊費不要。

ソースコード

14:21

現在地とその周囲(上、右上、右、右下、下、左下、左)について既に買ったかどうかを条件にしたbitDP。 $O ( 2^8 H W )$
f:id:akouryy:20151213233000p:plain
実際は右、右下、下は絶対にまだ買っていない状態なので $O ( 2^5 H W )$ でできるっぽい。この場合は境界が面倒なので番兵を使うことになるかな。
f:id:akouryy:20151213233006p:plain