第18回日本情報オリンピック（JOI 2018/2019）予選

結果

２学期期末考査の初日前日に行われた（極めて大変だった）．６問・600 点満点中，５問＋部分点・506 点で A ランクだった．１問目を解くのに想定より時間がかかってしまったが，その後は何とか解き進めることが出来たのでよかった．

競技前

去年の予選問題４，５を解いて DP を少し復習した．また，蟻本の DP のページを読んでいた．

競技中

問題１を読む．

四則演算でやるだけでは，となる

提出 -> WA (40 点・03:39)．

全くバグる原因がわからず，愚直にシミュレーションをする -> AC (100 点・20:56)．

遅すぎると焦り，問題２を読む．

実装するだけ -> AC (100 点・26:39)．

問題３を読む．

ox か xo が含まれる個数を数える貪欲法で解ける -> AC (100 点・30:04)．

問題４を読む．毎年の傾向であった DP じゃないと思った．

とりあえず座圧すればいい．

愚直解を書いて提出 -> TLE (15 点・43:12)．

時間ごとに各区画を見ていては間に合わないので，時間ごとの島の数の差分を求めたい．

適当に規則性を見つける，書いて提出 -> WA (0 点)．

海が一切ないときにバグると分かり，両端を海にして提出 -> WA (0 点)．

バグを減らすために同じ標高の区間が連続していたら１区間にまとめるようにして提出 -> WA (0 点)．

実装でのバグを見つける，修正して提出 -> AC (100 点・90:02)．

競技時間の半分でちょうど問題４まで解けたので一安心．が，問題４が DP ではなかったのでボーダーは 500 ぐらいだろうと思った．

問題５を読む．これこそ DP だと思った．

愚直に計算する DP を書いて提出 -> TLE (70 点・118:19)．

意外と点数が取れてしまい驚いた．

DP 内で計算していた部分を DP 外で前計算しておくことで高速化できる，提出 -> AC (100 点・138:48)．

流石に 500 点とれば通るだろうと予想する．

問題６を読む．満点阻止問題な気がした．

全通り試してみる -> WA (6 点・149:18)．

20 点解法として bitDP すればいいと気付いたが，ここで時間切れ．合計 506 点．

結果発表後

問題４と５の平均点がそれぞれ 9.4, 4.6 点と思っていたより低かった．それもあってか予想より少し低めの 396 点が A ランクのボーダーになった．

２月の本選でも A ランクを取って春合宿に行きたいと思った（頑張ります）．