第18回JOI予選参加記

はじめに

僕も人々みたいに参加記とか解説とか書いてみたい気持ちになったのでやります。

JOI(日本情報オリンピック)予選に参加しました。結果は410点。配点は100-100-100-100-10-0です。当日の流れとか各問題について書きます。

予選開始まで

前日はABC115を全完して気持ちよくなったのでセグ木の勉強をしてました。厳密にはセグ木使って区間最大と区間最小を取れるようになりたかったので記事を探してました。Tsuta_Jさんのが最高にわかりやすかったのでもし本番で出たら貼り付けりゃいいかなぁとか思いながら寝ました。

予選中

早解きする気になれなかったので20分くらいかけて3問目までを解きました。4問目は簡単だなぁとか思ってたんですけど実装バグらせまくって辛い気持ちになりました。1時間半くらいかってます。

ここからが今回良くなかったところなんですけど、5問目をみて「あっ区間最大じゃん！！」とか思ってよく考えないまま脳死で貼り付けてmaxとる形に改変しました。なんでスニペット作って置かなかったんですかね。改変自体にもそれなりに時間がかかってました。多分20分くらい。そのあと思ったことを実装してたんですけど思いっきり間違ってたんでサンプルが合いません。絶望。残り時間が1時間を切りました。

悲しい気持ちで全探を書きました。残り時間30分。6問目を読む。全探を一から書く。バグる。予選が終わる。

予選後

ついったーを見て人々が416点ばかり取ってるのをみて悲しい気持ちになりました。TLの強い人々はみんなボーダーは416点だとか言ってるのでもっと悲しい気持ちになりました。でも実際のところボーダーは最大でも400だと思ってたので実はそこまで絶望してませんでした。

予選1ヶ月前位から封印していたCHUNITHMをやりに行きました。炎上炎上炎上炎上！！！ww
改めてCHUNITHMは楽しいねとなりました。レートが13.80になりました。金レまでがんばります。

解説

既出しまくりですし公式も出してますが一応解いたところまでは解法を書きます。

1問目

1日ずつシミュレーションをしました。forで回してカウンタ変数は外においておくと楽でいい感じです。カウンタの値-1が答えになります。

2問目

1マス進めたいコマとその次のコマを調べていけば大丈夫です。

1. 次のコマが進めるコマのマス+1にいたらダメ。
2. 今いるマスが2019だったらダメ。
3. これ以外は進めていい。

これだけ書けば通ります。

3問目

1次元DPでやりました。s[i]とs[i-1]が同じ時s[i] = s[i-1]、違うときs[i] = max(s[i-1], s[i-2]+1)をするといい感じになります。多分1,2問目よりも解くの早かったです。

4問目

ぐっと睨んだら水位の上昇で島の数は増えた後減ることがわかったので三分探索をしました。三分探索とは凸関数の極値を高速に調べられるすごいやつです。詳しくは調べてください。更に考えると島の増減が起きるのはt=各区域の高さの時だけなので、最大で10⁵種類の高さについて探索すればいいです。
三分探索は同じ値が連続する部分があると上手くいかない(らしい)のですが、それを知らなかったためWAをし続けました。つらかったです。どれくらいつらかったかはこれを見れば分かると思います。
最終的に出した高さから±いくらかの高さを全部調べてその最大を取るとかいう筋肉をしたら通ったので筋肉は強いです。

完全な余談なんですけど、この問題解法が結構あるみたいで、解き方で日本が出現したり沈没したりするのでTLが賑やかだったんですけど、僕の場合は日本浮沈でいいですかね？

5問目

bit全探索をすると10点がもらえます。

感想

部分点を先に取るべきなのは知ってたし後輩氏にも言った気がするのですが、準備してた(実際準備できていない)セグ木を使える問題に興奮して時間を消費してしまったのが本当に良くなかったと思います。そもそもこの5問目はセグ木を貼った後は簡単なDPだったみたいなので気づけなかったことが悲しいです。Aランクボーダーは391点で本戦行ける事になったので本戦では今度こそ先に部分点を取りにに行こうと思います。

ここまで読んでくださりありがとうございました
PS:本戦erエンカお願いします！！