2018/11/17に行われたCODE FESTIVAL 2018に参加してきました。
前後泊ができたので2泊3日です。講義？知らんな……
・前日
金曜の朝から新幹線に乗ります。睡眠調整が上手なのでこの日は5時半に起きました。 予定通り郡山でいづみちはるが乗ってきます。お菓子をもらいました。
上野駅に着いたのはちょうど昼頃だったのでお昼ご飯を食べに御茶ノ水に行きます。 僕は豚野郎という豚丼の店（JAG夏合宿の初日に連れて行ってもらったところ）に行こうとしたのですが、満員だったので、ラーメンを食べることにしました。 その後いづみちはるの実家である自由が丘のセガに行き、いづみちはる経由で知り合ったそこの人々と音楽ゲームを楽しみました。
夜に秋葉原に戻ってきて、%20さん、うさぎさんと会いました。 夜ご飯を食べようとサイゼリヤに行ったのですが、待ちが10人以上いて険しい気持ちになります。 しばらく待ってから入って、食事をしつつコードゴルフの話をします。 カラオケに移動して（ここでも少し待ちが発生しました）、実際に問題を決めてゴルフすることにし、yukicoderで%20さんが最近出題した「mod数列」(https://yukicoder.me/problems/no/752)を縮めることにしました。
もともとの最短はCrystalで、これは聞けばRubyっぽくかけるコンパイル言語らしく、Rubyでは再帰が深すぎてREが出るので移植したようでした。 うさぎさんはCrystalの環境を作ってゴルフしていましたが、僕はとりあえずPerlに移植して通らないか試そうとしました。 実際これは通って、初回の提出から元最短のCrystalを30Byte弱更新できたので、やっぱりPerlだなあという気持ちになり、うさぎさんもPerlで書きはじめましたが、そこで時間が来たので中途半端に終わってしまいました。 カラオケを出てからしばらく喋り、各々別れてホテルに向かいました。
・当日
起床に成功します。ホテルに朝ごはんがついていなくて険しい気持ちになっていると、olpheさんが秋葉原でbeetさんと一緒にいるということで、僕も急いで出発しました。 パン屋に入って食事をしつつ、少しICPCの話をして、いよいよ会場に向かいます。 10問も問題があるのにコンテストが3時間しかないのは厳しいなあと思いました。
A：難しい。実は108回の計算が間に合う（えー！）。
B：MNは対数を取りたくなって、取ると全てが上手くいく。
C：制約に変な文言があるので、よく考えると二分探索できるとわかる。
D：522×90000=~=2×108しか思いつかないので投げると通る。
E：言い換えをすると区間minが欲しくなるのでセグ木を貼る。
F：後からキャンセルすることにする。ある時点でキャンセルできるような範囲が知りたいが、これは区間でのグルメ度の最大値/最小値が分かれば、二分探索で求められる。 そうして求めた範囲で美味しさが最小のものをセグ木で求める。それをキャンセルすると、グルメ度が区間で1増えたり減ったりするから、これを実現するために、グルメ度は遅延セグ木で持てばよいことがわかる。
G：ひよこの大きさでソートしてよいなあとはわかるが、DPがO(NM2)から落ちないなあとなって解けなかった。
ABCDEF六完でオンサイト29位。Fは600点、Gは700点なので当然Fのほうが簡単なのだけど解いた人数的にはそうなっていない。順位表を見て解かれている問題から解くというムーブが身についていない。
E問題は、スライド最小値を使うとセグ木が必要ないと聞いて、そうであることだなあと思う。
F問題について、両側からpopできる優先度付きキュー（キューではなくなるが）があれば解けるらしくて、さらに実はmultisetがそうなっているらしい。知らなかった。
G問題は、実は更新の範囲をしっかり計算してやると計算量が落ちて通るらしい。これが通っていれば順位が大幅に上がって賞金がもらえたのでちょっぴり悔しい。
あとはマリオカートをしたり、りんごの挑戦状を観戦したりしました。面白かった。
夜に音楽ゲームをプレイしに行きました。念願のchokudaiさんとマッチングができて非常にうれしいです。
・次の日
起床に成功します。今日は音楽ゲームをプレイする予定なので、こどふぇすの半袖Tシャツを着ることにしました。 秋葉原でいづみちはると待ち合わせて少し買い物をした後、ゲーセンに行きます。 少ししてたこノすけくんと合流できたのですが、日曜日なので人がメチャメチャいて非常に厳しい。早々にサイゼリヤで昼食を食べることにしました。 そこで よこ とも合流して、再度音楽ゲームをプレイします。場所を変えたりして、午後三時頃に、もう時間的に帰るべきだといづみちはるに言われたので、なるほどそれも一理あると考えました。 お別れをして新幹線に乗ると、自由席が満席で本当にビックリ。初めて新幹線に立って乗ることになりました。
郡山でいづみちはるが降りて行って、僕も仙台に到着します。案の定半袖はメチャクチャ寒い。まだ帰る気分ではなかったので、しばらく音楽ゲームをプレイすることにしました。 実はこどふぇすパーカーは生地が薄いので、もう仙台では着れません。来年まで眠っていてもらうことにしました。
