ICPC 2019 Asia Yokohama Regionalに参加
本記事はMuroran Institute of Technology Advent Calendar 2019 12/13の記事です．
はじめに
私はこれまで，2016年，2017年，2018年のICPC国内予選に選手として参加しています． 今回も選手として参加したかったのですが，今回は選手としての参加資格がありませんでした． 他の参加選手からコーチになるように頼まれたので，引き受けることにしました． 今回，私の大学から5チームが国内予選に参加し，そのうち1チームが横浜のアジア地区予選に出場することとなり，コーチとして一緒に行ってきました． 以下ではICPC 2019 Asia Yokohama Regionalに参加した感想を時系列順に述べます．
ICPC 2019 Yokohama Regional 国内予選
準備
コーチの最も重要な任務はチーム登録と実行委員会からのメールの伝達です． 特にチーム登録は意外と大変でした． 選手はアカウントを作成し，これをコーチに伝えます． コーチは選手を検索し，作成したチームに選手を追加します． その後，選手たちは登録情報の補充をします． あるチームでは，アカウント登録の完了がなかなか終わらずチーム登録を完了できません． また，あるチームでは，チーム登録まで完了しても，登録情報の補充が完了しない選手がいます． 催促をしてもなかなか反応がないこともありました． 登録期限が迫る中，私は選手登録とチーム登録が完了できるか心配でした． 最終的には全員参加できたので良かったです． 私が，過去にICPC国内予選に参加した時のコーチも同じような思いをしていたと思うと，改めて感謝の念を抱きました．
他にも，選手たちと一緒に監督を引き受けてくれる先生を探し，引き受けてくれるようにお願いしました． 監督の仕事は，試験監督のような感じで，国内予選当日に問題のコピーを配り，選手が不正しないようにを監視することです． また，監督は必要に応じて審判団との連絡も行います． 私の指導教員が引き受けてくれてありがたかったです．
本番
ICPC国内予選当日，コーチの仕事はありませんでした． 室蘭工業大学からはSataniChoが横浜のアジア地区予選に出場することとなりました．
問題を解いた
選手たちと同じモチベーションで打ち上げに臨むためには，同じ問題を解いて同じ熱を纏う必要があります． 研究室でICPCに参加していないメンバ2人を誘って問題を解く会を開催しました． 私たちは正式な参加ではないため，パソコンは1人1台使用可，インターネット接続可，複数ディスプレイ可で解きました． 他の2人がA，Bを担当し，私はCを担当しました． 最初C++で解こうと思いましたが，組み合わせを全て列挙すれば良いことに気がついてPythonのitertoolsを使うことにしました． 他の2人がA，Bを解き終わってからは3人で協力して解きました． ほぼ3時間以内に解き終わることができました． Pythonが遅すぎたため，最後はPyPyで実行しました． 協力しながら解きごたえのある問題を解くことができて楽しかったです．
ICPC 2019 Asia Yokohama Regional
横浜で開かれるアジア地区予選に出場するSataniChoの選手たちには旅費が支給されます． なんと，コーチにも旅費が支給され，一緒に行くことができました． 日程は3日間で，1日目はリハーサル，2日目は本番と立食パーティ，3日目は会社見学でした．
1日目
5時半くらいに起床し，荷物の準備をしました．
6:15に待ち合わせをして，選手の車に乗せていただき，室蘭工業大学から新千歳空港まで行きました．
自転車では半日かかる約70kmの道のりですが，車だったため9:30出発の飛行機に余裕を持って到着しました．
昼過ぎに羽田空港に到着し蒙古タンメンを食べに行きました．
客が並んでいたため，リハーサルの集合時刻に間に合うか際どいところでしたが，結果的には間に合ったと思います．
会場の横浜産貿ホール マリネリアに到着すると英語で質問されました．
大学名をきかれたのだと解釈し，"Muroran Institute of Technology"と回答しましたが，ピンとこなかったようだったため，"From Hokkaido"と言い直したら，受付へ通されました．
あとで考え直すと，もしかしたら北海道大学と勘違いされていたかもしれません．
アジア地区予選の公用語は英語なのかと察しました．
受付では，スタッフにStudent IDを見せてくれと英語で言われましたが，よく聞き取れずにいるともう1人のスタッフが"Gakusei shou"と分かりやすい英語で教えてくれました．
リハーサル会場にはチームごとにブースが設けられており，水，弁当，しおり，Tシャツ，参加証明書，ネームタグが支給されました． Tシャツとネームタグは大会の間はずっと付けなければいけないようでした． 今まで選手登録の度に，なぜTシャツのサイズが要求されるのか疑問でしたが，会場で支給されるからだと知ることができました． また，朝時間がなくて3日間の着替えの準備が不十分だったのですが，Tシャツが支給されたことによりこの問題が解決しました．
リハーサルでは，まず諸注意があり，デモンストレーションがあり，その後，選手たちが実際にリハーサル問題を解きます． 国内予選を勝ち抜いた選手たちからは，多くのことを学びました． C++のラムダ式は変数に代入した上で，引数で自分自身を受け取ることで再帰することができることを知った時は衝撃を受けました． また，アジア地区予選ではジャッジシステムを用いるため，実行時間に何時間も使って強引に解くことはできないことも知りました． そして，ACする度にスタッフが風船を持ってやってきて，ブースの机の横に引っ掛けていきます． これはとてもにぎやかな感じがしました． しかし，コーチがその場でするべきことは特にありません． 自分はなぜここにいるのか，という当初から存在していた答えの無い問いと向き合う決心をしました． 起床が早朝だったため，気がつくとウトウトしていました．
リハーサル後，私たちは会場の近くの中華街へ夕食を食べにいきました．
まず，インターネットで調べて人気そうだった中華料理屋に並びました．
行列に並ぶのが嫌になったため，その向かいの中華料理屋へいくことになりました．
その店は2階建てで，2階のテーブルに案内されました．
そこにはスタッフが1人いました．
2階には客用のテーブルが並んでいましたが，厨房などは無いようでした．
いったい料理はどこから来るのか，食器はどこへ帰っていくのかと思いましたが，料理用エレベータで上ってきた料理を客に出し，片付けた食器を料理用エレベータで下ろしていたのでした．
私は色々な料理を食べることのできるコース料理を注文しようかとも思いましたが，高かったため，回鍋肉定食を注文しました．
とても美味しく，また，お腹も満たされました．
ホテルに着いて21時になるとAtCoder Beginner Contest 145が始まりました． そのE問題のTLEを修正することができないまま終わってしまいました． atcoder.jp 提出したプログラムはソートとDPを組み合わせた解法で，計算量も解法も想定解法と同じはずでしたがTLEとなってしまいました． 原因の究明をしたいとは思いましたが，あまり寝るのが遅くなって寝坊したら選手たちに申し訳ないため，すぐに寝ました．
2日目
本番では，コーチは会場である横浜産貿ホール マリネリアに入ることができず，会場横の神奈川県民ホールで待機することになっていました． ここで，遂にコーチが活躍する機会が訪れました． 選手たちは時計やスマートフォンなどを会場に持ち込めないため，コーチが預かることになったのです． 選手の役に立つことができました．
神奈川県民ホールに着いたのは8:50くらいでしたが，開館時刻が9:00と書いてあったため待つこととしました． 入り口前で待っているとスタッフが1人やってきました． 公用語が英語だと察した私は，挨拶は"Good morning"か"Hello"どちらが良いかと迷いましたが，「おはようございます」言われました． そこは日本語なのか，と混乱した私から1呼吸遅れて出てきたのはカタコトの"Ohayou gozaimasu"でした． そのスタッフが言うには，神奈川県民ホールは開館が9:00であるため，そこから準備が始まるらしく，大変なんだなと思いました．
開館後どうして良いか分からなかった私は周りの人についていくことにしました． みんなの向かう先には，ステージのある大きなホールがあり，多くの椅子が並んでいました． 座っていると着々と準備が進んでいき，ステージ上で大会の中継が始まりました． しばらくすると問題用紙も配布されました． コーチはこのホールで大会が終わるまで中継を見たり，問題を読んだりしながら待機するのかと思いかけたところで，周りを見渡すと，あまりにも人が少ないことに気がつきました． 少し飽きた私はお手洗いのついでに，ホールの外のロビーの様子を見に行くことにしました．
ロビーには軽食が並べられており，問題用紙を広げながら楽しそうに議論をしている他のコーチたちが，何人かいました． ロビーの椅子の方が座りやすため，そこで軽食をいただきながら昨日のAtCoderのE問題を解き直そうと思いました． しかし，AtCoder後に充電するのを忘れていたため，私のMacBookProの充電は風前の灯火でした． 使用可能な電源がないようだったため，パソコンの使用は諦めることにしました． 大会終了までまだまだ時間があります． やることが無くて困った私はSataniChoのその時点での順位の確認をしながら，気がつくと鞄を抱き締めたままウトウトしていました． 周りが賑やかになってきたことに気がついて周囲を見ると選手たちがいて，大会が終了したことを知りました．
その後ホールに移動し，解説と最終順位の発表，協賛企業からのお話などを聞きました．
そして，みんなで横浜産貿ホール マリネリアへ向かい，そこで表彰式と立食パーティがありました．
SataniChoも何かの賞を受賞していました．
立食パーティでは，まず，ご飯を食べた後，各企業の紹介ブースを回りました． 初めて見る会社も多くあり視野が広がりました． また，鞄に入り切らないほど多くの景品をいただきました． 他にも，タピオカミルクティを獲得するために数独を解いたり，笑顔度を測定したりしました．
3日目
最終日は会社見学でした． 私たちのグループはHauwei，NEC，しながわ水族館の順に見学をしました．
Hauwei
8:15分にホテルをチェックアウトし，Hauweiへ向かいました．
そこでは，Hauweiの日本の研究所の会社説明を受け，エンジニアたちからそれぞれの仕事内容を聞き，エンジニアと昼食をいただきました．
私たちと一緒に昼食を食べたエンジニアは，写真が好きで，カメラに関する仕事をしているということで，写真やカメラに対する熱い想いを感じました．
また，しながわ水族館に先に行った他のグループは昼食をどうしているのだろうか，といった会話をSataniChoのチームメイトとした時に，私が「魚料理でも食べているんじゃないか」とジョークを言うと向かいで座っていた他チームの方が笑ってくれて良い人だなと思いました．
NEC
Hauweiの次にNECへ行きました． 移動は個人行動ということになっていたと思いますが，他の選手たちについて行きました． その選手たちも途中で道が分からなくなり，NECと書かれた大きなビルをに向かって歩きました． 一応，選手の監視役のようなICPCスタッフもいましたが，選手の引率役ではないようでした．
NECではAIの話とセキュリティの話を聞いた後で，顔認証技術を利用したシステムのデモンストレーションを見ました．
AIの話では「あの頃は CHOCOLATE」というお菓子の開発について聞きました． これは各時代の新聞から取り出した単語と単語から連想される味を組み合わせたデータを学習して，ある時代のムードをチョコレートの味で再現するというもののようです． その時に流された動画もとてもお洒落でした． しかし，AIが再現した味が本当にその時代のムードを表現できているのかどうかは，確かめられないのでは？ と思い，質問しました． これに対しNECの社員は，待ってましたと言わんばかりに回答を始め，私は一本取られたなと思いました．
また，セキュリティの話ではCTFの紹介があり，興味を持ちました．
顔認証技術を利用したシステムのデモンストレーションでは，まるでPSYCHO-PASSや攻殻機動隊のような近未来感のあるシステムが紹介され，とてもワクワクしました．
しながわ水族館
NECの後はしながわ水族館へ向かいました． その時には，私は監視役について行けば，しながわ水族館にたどり着けると気がついていました． 他の選手たちもそのことに気づいたようでした． 私は降りる駅もわからないまま監視役について行きました． まるで，ハンター試験のようだと思いました． しかし，一部の選手たちが途中で違う電車に乗ったり，別の駅で降りたりしようとした際には，監視役は選手たちが間違わないように指示を出し，最後には先頭を歩いてしながわ水族館まで選手たちを導きました． 実は優しい人だったのかと思いました．
また，移動途中の電車内においては，Hauweiで私のジョークに笑ってくれた選手が，僕たちはいつまでこのネームタグをつけていなければいけないのか，という話の中で，「ACした時の風船をつけるよりマシだ」とジョークを言っていて面白いと思いました．
しながわ水族館では，自由行動ということだったので，閉館まで見て回りました． まず，アシカかセイウチのショーを見ました． 水族館スタッフがアシカとセイウチを見分けるには耳を見れば良いと言っていた気がしますが，どっちがどっちかは，もう忘れてしまいました． 他にもクラゲ，イカ，エイ，ペンギン，サメ，ドクターフィッシュなどが印象的でした．
特にドクターフィッシュのコーナーでは水槽に手を入れると，ドクターフィッシュが群がってきて意外と高い周波数で手をつつきます． 痛くもなく，痒くもなく，くすぐったくもなく，とても不思議な感覚でした． ちょうどそこで，昼食で私のジョークに笑ってくれて，電車でAC風船のジョークを言っていた方と再会しました． 彼は，ドクターフィッシュの感覚が気に入ったようで，「家でドクターフィッシュを飼って顔を入れたい」とユーモアのあることを言っていました． 彼と話したのそれが最後ですが，TwitterのIDを聞くなど，もっと仲良くなりたかったなと少し後悔しています．
しながわ水族館の会社見学では，ショーの準備をしたり，展示物を工夫したりといった，客を楽ませるための心遣いを感じて，尊敬しました． また，水族館の仕事は展示の他にも環境保全や生態調査もあることを知りました．
帰路
しながわ水族館を出た後は，研究室の在室表のマグネットとして使用できるマグネット付きチンアナゴを記念に買い，その後夕食としてラーメンを食べました．
余裕を持って遅い出発時刻の飛行機を予約していたため，時間が余りましたが，早めに羽田空港へ行って，お土産を買ったり，プログラムを書いたりすることにしました．
空港ではさっさと保安検査場を通過した後，お土産としてすいーとぽてたまごを買い，それから搭乗時刻まで一昨日のAtCoderでTLEのまま放置してあったE問題の解き直しました．
アルゴリズム自体は想定解法通りであったにも関わらず，実行時間がかかってしまうボトルネックは，DPのメモ化に用いているstd::unordered_mapだろうと考えました．
実際，std::unordered_mapの代わりに2次元にしたstd::vectorを用いるとTLEしませんでした．
よく調べてみるとキーの衝突が頻発いていることが分かりました．
私はどうしてもDPのメモ化にハッシュマップを用いたかったため，次の三つを試してみました．
std::unordered_map::reserveを呼んでメモリ確保を最初の一回だけにする．std::arrayとstd::mapを組み合わせてシンプルな自前のハッシュマップを実装する．std::tupleに対して実装しているハッシュ関数を変更する．
まず，1.のみの場合は特に効果を感じませんでした． atcoder.jp 次に，2.のみの場合は，結果はTLEとなりましたが，TLEとなるテストケースが2個に減り，効果があることが分かりました． atcoder.jp さらに，2.と3.を同時に行うと，無事ACできました． atcoder.jp ハッシュ関数は元々Effective Javaを参考に実装していたのですが，よりハッシュ値が分散するようにチューニングしました． 最後に，標準ライブラリがある場合には出来るだけそれを使うべきだと考えて，3.のみの場合についても試してみました． atcoder.jp 結果はTLEでしたが，先ほどの2.のみの場合に残ったTLEのテストケースのうち一つがAC，もう一つがTLEであり，ACした方は実行時間が1986 msだったため，もう一度提出してみると今度は1999 msでACすることができました． atcoder.jp
新千歳空港から室蘭へは再び選手の車に乗せていただきました．
