加賀一稿一記

心は戦国

第一回日本最強プログラマー学生選手権決勝 に参加しました

2019年9月29日に開催された
第一回日本最強プログラマー学生選手権決勝 - AtCoder
に参加しました。
感想とかダラダラ書きます。

前日
前日のうちに東京に移動して前泊。
ホテルからABC142出るか〜と思っていたけど、部屋のテレビがラグビーW杯日本-アイルランド戦を放送し始めたのでそちらを優先。後で問題読んだらFが解けそうでバグらせそうな見た目をしていた。

当日
考察をiPad+Apple Pencilで行うユーザがそれなりにいるっぽくて嬉しくなった。僕も1年くらい使っているけど、競プロ考察でこれより便利な筆記具は思い浮かばないんだよな。

事前情報として配点が300-400-700-800-800-800-1200-1400な事を知っていたので、「AB速解きして時間を作って、残り時間でCDEFから一番解かれているものに挑戦する」流れになると予想していました。
しかし...
A問題Square Routeに似ているけど、同様にやるとTLEしてしまう。重みが妙に小さい事を利用したいが分からん、これは0完か???みたいな思考が開始後数十分続く。

順位表を見るとAよりBの方が解かれているので読む。問題文がややこしくて嫌な感じだけど、これを解かないと本当に0完になるので頑張って読んだ。実はシンプルで、言われた通りに辺を切り張りして矛盾がないか調べるだけだった。
開始後70分でBをAC。

Bが解けたのでAに戻るがやはり分からん。
"find two pairs from two arrays equal sums"とかでググりまくるも進展せず。

開始後90分になっても綺麗な解法が思い浮かばないので、諦めて強引な実装に切り替えた。
「2つの数列から距離が等しいペアを探す問題。距離はせいぜい1〜10^6」だと考えて、候補の距離を1から調べていくことにした。
愚直にやれば当然TLEするが、調べる距離をsetとか使ってゴリっと決めてやれば早くなりそう(ヤケクソ)で実装した。
開始後114分でAをAC。
Submission #7782243 - 第一回日本最強プログラマー学生選手権決勝

なぜ通ったのかよく分からないなあとか思いながら順位表を見る。
CとFが20人くらいに解かれてるので読む。
Fは数学なので諦めが肝心。
CはCで意味不明。手元でゴニョゴニョやるけどダメ。
苦しみながら3時間が過ぎ去った。

結果は83位。レーティング順位よりも良い結果なので嬉しいけど、やったことが300, 400を1問ずつ解いただけなので達成感は微妙。

コンテスト後TLを賑わせていた鳩の巣原理を念頭に置きながらAの再考をしたら綺麗な解法が浮かんだ。天才だなあ。

ホゲーってしてたらセミナーやトークセッションが行われた。コードを書くアウトプット作業だけでなく、イベントでインプットもできるのはいいですね。(レーティング向上に繋がる内容だともっと嬉しかった)

エモい感想
今年度中に同規模のコンテストが開かれる場合は別ですが、今回が学生最後のオンサイトになったんじゃないかなと思っています。
結果として決勝に滑り込んで二桁順位を残せたので、「学生の間は最後まで頑張れた」と言えるような気がします。(何を持って頑張れたとするかは人によるとは思います。)

ネガティブな感想:東京は遠い
僕の住んでいる県には新幹線の駅や空港がなく、東京は遠いです。
当日中に帰るため、懇親会を諦めてトークセッション終了後に帰りました。
懇親会に参加しないとなると、オンラインジャッジ利用のために東京往復をしていることになり、ちょっとモヤっとしてしまいます。
いっそ交通費や宿泊費の補助ではなく、オンライン参加を選択できたらいいのになと思いました。