NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ，自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので，過去にブックマークされた記事は URL が変わってしまっている可能性があります……．

ICPC 2018 国内予選 参加記

参加記 (イベント・勉強会等) 競技プログラミング (雑記)

昨日7/6 (金)，チーム KatsuT0shiのメンバーとしてICPCの国内予選に出場しました．参加者の皆さん，関係者の皆さん，お疲れ様でした．

KatsuT0shiは情報系のM1 3人で構成されるチームです．3人のうち私を含む2人は95年生まれでこのチームで出られるICPCは最後なので，アジア横浜予選出場を目標に練習してきましたが，結果は4完54位，学内2位で国内予選通過ならずでした．この悔しさと残ったエモさを消化するべく，参加記を書きます．

f:id:noimin:20180707104235p:plain

チーム結成

結成の元々のきっかけはCODE THANKS FESTIVAL 2017に遡ります．同じ大学・学部・学科の友人であるsidebook37とCODE THANKS FESTIVALに参加しました．行きのゆりかもめの中で，彼にICPCの話を切り出してみました．

昨年度，私はICPCに出ていませんでしたが，2018年こそは勇気を出してチームを組んでICPCに出ようと思っていました．そこで，おそらく大学同期で1番強い競プロerであるsidebook37に，チームを組まないかと声をかけることにしました．彼はすでにICPCに出ていたので，来年のチームも決まってたりするのかな……と不安に思っていましたが，快く組んでもらえることになりました．

今年6月に入ってから，某研究室関係者を中心としたチーム決めに私も参加し，sidebook37と私の学部のときからの同期で私の編入同期でもあるtoshi17とともにKatsuT0shiは結成されました．

練習

6月前半までは各自精進，6月後半に2〜3日に1回の頻度でバーチャルコンテストでの練習を行いました．バーチャルコンテストではsidebook37がちょうど良い難易度の問題を選ぶプログラムを書いてくれていたのでそれを使って問題を選択し，本番環境と同じtoshi17のMacBookで問題を解きました．

私たちのおおよその作戦はこんな感じです．まず，A，B，Cをtoshi17，私，sidebook37がそれぞれ解きます．ただし，互いの得意苦手や実装の進捗に応じて問題を交換したり，ペアプログラミングを行ったりします．実際練習でも，Bがsidebook37の方が得意そうな考察重め問題，Cが私の比較的得意な構文解析のときは問題を交換したり，AやBをtoshi17とペアプログラミングするような場面は何度かありました．DやEは確実に解けるとは言えないので2人以上で相談しながら考察しますが，解法が見えたら基本的には方針を立てた人が実装します．それ以外の人は解けていない問題を考察しますが，DやEが実装重めの場合はペアプログラミングをします．F以上は練習では1度も解けませんでしたが，たまたま練習で5完したときは全員でFの考察をしていました．

つまり，全員が考察・実装・デバッグを担当しうる感じです．

初めはうまく連携が取れず3完ばかりだったのですが，徐々にチーム戦での動き方がわかってきて模擬国内では5完23位でした．学内予選での最大のライバルであったAobayama_dropoutはメンバーが1人足りない状態だったとはいえ，本番も5完できればAobayama_dropoutとKatsuT0shiのWアジア予選進出あるなぁとワクワクしました．実を言えばすっかりアジア予選に行ける気でいたし，行けなかったときのことはあまり考えたくありませんでした．

国内予選当日

11時に集合時間を定めていたら3人とも遅刻．練習セッションはご飯の後ということにして，スニペットの印刷とか書籍の用意をし他の同期チーム(Gachichi) 含めご飯を食べました．会場である某研究室に戻ってきた地点で13:00くらい．ここからそわそわタイムが始まる．

もちろん提出練習もするのですが，そわそわしすぎてsidebook37とtoshi17は釣りの動画を見始めたり，私はTwitterに連投したり，3人がそれぞれ他のチームにちょっかいかけに行ったりしてました．あ，あとは構文解析は確実に倒せるように簡単な構文解析を解いたりもした気がする．

研究室にはプログラミングサークルpuzzleknotのメンバーや今回名乗りを上げた有志含め，次々と選手が到着します．フォロワーを特定して挨拶しようかとも思いましたが，本番直前に自分の動揺を誘うようなことをするのもなぁと思って自重しました．

そうこうしてる間に競技開始．予定通り，A，B，C問題をtoshi17，私，sidebook37がそれぞれ解くことになりました．

6:09，toshi17がA問題をAC．練習よりだいぶ早かったです．

続いて私がB問題を実装．方針は定まっていましたが，疑似コードを書くところまでは終わっていなかったので少々不安に思いつつでもまぁPC空いてるしB問題だしということで実装開始．

折り紙の左下の座標の初期値を(0, 0)として，紙を1回折るたびに「左下の座標を更新する処理」と「ある行or列で重なっている紙の枚数を更新する処理」をすれば良いということはわかっていたので，実装し，サンプルが会うところまではスムーズに行きました．しかし，解答用データを入力に入れるとSegmentation fault．実は重なっている紙の枚数を管理する2次元配列をm×nしか用意しておらず，半分より上に折り目がある場合や半分より右に折り目がある場合に対応できていなかったことに気づくのにだいぶ時間がかかってしまいました．他にも細かいバグをいくつか修正し，43:21にB問題をAC．後から知ったのですがB問題ACは割と早い方だったらしく，嬉しいです．

ここでコーダーをsidebook37に交代しましたが，D問題の方針が先に立ったようなのでC問題の考察をしてほしいとのこと．D問題の方針を聞いて特に穴は見当たらなかったのでD問題を実装してもらい，その間にtoshi17と私でC問題を考えることに．

しばらく1018でかすぎ〜〜〜〜〜と2人で唸っていましたが，toshi17の「実はkってそんなに大きくならなかったりしない？」の一言で突破口が開けました．kは概算した結果50000まで考えれば余裕だろうということで，kを決めうちしてnについての方程式を解く方針で行くことにしました．確かこの辺りで隣の部屋から歓声が聞こえてかなり焦りました．たぶんAobayama_dropoutがD問題をACしたときの歓声かな？

D問題はデバッグにもう少しかかりそうとのことだったので，先に私がC問題を実装しました．特に問題もなく，サンプルも合って提出！　……したところ，今回最初にして唯一のWAを出してしまいました．落ち着いて最大ケース等で試してみたところ，切り捨て割り算関連でバグっていたことが判明．最初は焦ってソースコードのいろいろなところをいじっていましたが，落ち着いて式を変形し直し，割り算は最後までとっておく感じにしたところサンプルが合ったので提出．1:42:51にC問題AC．

ここでまたsidebook37にコーダーを交代し，まだ手がついていないE問題の概要をtoshi17から聞きながら考察．構文解析っぽいG問題も見てみたけど，残り時間も少ないしE問題のほうがまだ希望がありそうだったのでEに集中しようと決めました．Eは浮動小数点数の加算の誤差をシミュレートする問題です．繰り返し2乗法っぽく加算していけばおっけーでは？　と思って慌てて実装に取り掛かってしまいましたが，実装に落とし込むまで考察できてなかったのと「足す順番が変わってしまうが本当に良いのか？」という疑念が拭えずsidebook37にコーダーを再々交代する事態になってしまいます．結局この後sidebook37がD問題を2:35:46にACしてくれました．

サンプルを見ながら指数部は$ \lceil log_2n \rceil$じゃないか，仮数部はどうせいい感じにシフトしていい感じに足すんだろうなぁと思うも，残り一桁分でこれはもう時間内では無理だという感じ．でもせっかくなので時間いっぱい考えてました．

学内2位で50位台はさすがにアジアは厳しいとわかっていたので，終わった後はとにかく冷えてました．半分くらいICPCのために進学したようなものなのに，こんなにあっさり終わってしまったので．我慢できるかな，できないかな，と思ったころにはもう泣いてましたね．

(今回はたまたまA,Bが早く解けましたが) あまり早解きが得意ではないチームだったので，5完すべきだったし，今思うと今回のようにE問題との相性が悪かったならsidebook37がD問題の実装をしている間ペアプログラミングをすべきだったかなぁと思っています．

とりあえずさっさと会場を後にして模擬国内後のようにお酒を飲みました．今日のこと，今までのこと，将来のこと，ありとあらゆるエモい話をしました (雑) ．悔しさを共有できる人がいるっていいなあと素直に思いました．2人とは元から友人でしたが，ICPCをきっかけにより仲良くなれてそれも素直によかったなあと思います．

おわりに

チームメイトの2人，コーチの先輩，監督者を引き受けてくださった先生，応援してくださった皆さん，ありがとうございました．

チームメイトとはまた別の機会に同じコンテストに参加したりチームで何かしたりしたいです．

ICPCはこれが最初で最後でしたが，これからも強くなれるように精進します． (まずは先週先々週あまりやっていなかった研究をね)

Aobayama_dropoutの皆さん，おめでとうございます．アジア横浜予選でのご活躍をお祈りしています！

私は横浜には行けませんが，他オンサイト等でお会いした際にはよろしくお願いいたします．