JOI 2017/2018 本選参加記

もうすぐ春休みだというのに外が寒すぎて絶望しているふぃらっはです．

2/10から2/12にかけて，日本情報オリンピック（JOI）本選に参加してきたので，レポートを書いていきます．

1. 移動

2/10（土），津山線に乗って長旅をはじめました．片道7時間です．結構遠いですね．
ただ窓外を眺めてのほほんとしている訳にもいかないので，JOIの過去問を解いていました．

なんとか会場のつくばカピオにたどり着きました．既に多数の本選出場者が集まっていて，ああついに来たんだなあという感慨を抱きました．それにしても，中学生が多くてびっくりしました．

2. プラクティス，夕食会

最初に行われるのはプラクティス（本番環境に慣れておくための実機練習）です．本選で使用するものと同じPCを使い，実際にプログラムを提出し，競技の方法とルールを確認します．
プラクティスは別に問題を解く練習ではないので，問題には比較的簡単めの過去問が使用されます．なので，多くの参加者ははやばやと満点を取ってしまうのですが，なんとぼくは時間をフルに使っても満点を取れませんでした．既に暗雲が立ち込めています．

プラクティスが終わり，講演会があったのち，参加者同士の交流を目的とした夕食会が開かれました．他高専の方と話したり，ビール箱の上で自己紹介をしたりしました．

なお，夕食会中に，プラクティス時の成績が配布されました．つらくなりました．

3. 競技，解説

次の日は，いよいよ本選競技が行われます．朝の9時から13時にかけて，ぶっつづけで問題を解き，プログラムを書くことになります．

本選で出される問題は5問です．どれも比較的難易度が高く，時間をかけて臨まないといけません．

問題文や入出力は情報オリンピック日本委員会が公開しているので，参照してください．

1問目は，以下のように考えることで満点を得られます：
マッチが来客の数以上あるときは，ストーブを都度つけたり消したりすればよい．つまり，Nがそのまま答えとなる．
マッチが来客の数より少ないときは，各来客の来訪時間の差（T_i – T_(i-1)）を小さい順に潰していくようなストーブのつけかたが最適である．各iごとにT_i – T_(i-1)を記録しておき，それをソートして貪欲に取っていけばよい．

この解法には比較的早くたどりつけました．昨年以前の過去問の1問目はもう少し難易度が高く，1問目さえ解けないかもしれないと危惧していたので，僥倖でした．

2問目はやや難易度が上がります．解法は以下のようになります：
美術品を大きさでソートする．最小と最大の美術品を決め打ちすると，その間の美術品は全て取ることになる．これを愚直に実装すると計算量はO(N^3)となる．価値の累積和をとっておくことで計算量がO(N^2)となり，満点を得られる．

わかったふうなことを書いていますが，実はこの問題は小課題1しか取れていません（つまり，まともな解法を見いだせませんでした）．「JOIは動的計画法問題が頻出」ということが念頭にあったため，動的計画法が解法だと思い込み，3時間半頭を抱えていました．

3問目以降は問題文をさらっと読んだだけで全く触れてないので，申し訳ないんですがパスさせてください．

最終的な結果としては，110点でした．もともと100点取れるかどうかすら怪しかったので，悪くないといえば悪くないです．が，2問目は発想を転換していたら解けたなあと思えるので，割と悔しいです．ランクはBで，国際情報オリンピック日本代表の最終選考となる春合宿には進めませんでした．

4. 解説

本選競技が終わり，昼食を食べたら，問題の解説があります．国際情報オリンピック日本代表OBの方々が解説してくださいました．
2問目の解説を聞いて，膝を打つと同時に，完全に方針をミスっていたことにショックを受けました．それ以降の解説は難しすぎてあまりわかりませんでした．ただ，5問目の解説で多量のだじゃれが放たれたことだけは覚えています．感動しました（だじゃれが好きなので）．

解説が終わると，JOI本選の全行事は終了ということになります．謎おみやげや自由時間に現地で購入した本を持って帰路につきました．

5. おわりに

なんだかまとまりのない記事を書いてしまって申し訳ありません．この記事を通して何を伝えたかったかというと，競技プログラミングは決して甘くはなく，他の多くの分野と同様，たくさんの努力が必要になる，ということです．単なる言い訳になってしまいますが，JOI本選の直前まで学年末試験があり，対策がおろそかになっていました．より精進に励んでいたらもう少しよい結果を残しえたのかなあと思うと慚愧に堪えません．

JOIへ出場できるのは高校2年生までなので，ぼくはこれが最初で最後のJOI本選参加となります．現1年生のみなさん，そして数カ月後に入ってくるであろう新入生のみなさんには，まだまだチャンスが残されているので，ぜひ頑張ってもらいたいなあと思います．もちろん私も，来年度のパソコン甲子園など，まだまだ大会に出る機会はあるので，謙虚に精進をして実力をつけていくつもりです．

最後になりましたが，シス研顧問の先生方，夕食会で話しかけてくださった本選参加者の方々，大会運営スタッフの皆さん，ありがとうございました．