- 川﨑 理玖 (筑波大学附属駒場高等学校3年)
今年のIOIは僕にとって2回目の,そして最後のチャンスでした.結果は4位で,自分にとっては少し不釣り合いなかなりの高順位だと驚いています.しかし,それでもなお,心残りはあります.大いにあります.この辺の事情について,僕が思うことをこの感想文に記したいと思います.
競技1日目は,競技開始の瞬間にコンテストホールに衝撃が走りました(多分).少なくとも僕は無視できないレベルのショックを受けました.なぜなら,ここ数年全く出題されることのなかった "output only task" が出題されたのです.この種の問題の特徴として,
・ソースコードではなく,手元のパソコンでの出力結果を提出する.
・(0点を除けば)全く同じ得点を複数人のコンテスタントが得ることが起きにくい.
・満点を獲得することがほとんど想定されていない.
ということが挙げられます.僕は正直,この3つめの特徴のせいで,この種の問題が嫌いでした.正確に言えば,この問題はIOIに向いていないし出てほしくない,そう考えていました.だって満点を取る夢がないじゃないですか.もちろん,僕の実力が満点を取るに値するもの,それこそ高谷君のような強さに匹敵するものだとは本気では思っていませんでした.でも,少しだけ,ほんの少しだけ,満点を取る妄想ができたっていいと思うんです.他人の心の中を覗くことはできないけど,ほとんどのコンテスタントの脳裏にも,一回くらいはそんな妄想が浮かんだことがあるんじゃないかと僕は思います.
しかし,僕が心残りに思っているのは,"output only task" が出題されたこと,ではありません.この種の問題が出ないと高を括り,対策を怠り,競技練習ですら全く手を付けようとしなかった,自分の愚かさです.僕がこの種の問題を好きではなかったということは,対策を怠った理由の一つとして挙げられるでしょう.ですが,それ以上に,この問題はみんなが出てほしくないと思っているからきっと出ないだろう,と希望的にとらえ過ぎていたことが原因としては強いと思います.ここで念を押しておきたいのが,僕は決して,嫌いなタスクについても対策をきちんとやれ,と忠告したいわけではないということです.もちろん,どんな問題ができても対応できる力を身に着けることが出来れば,それに越したことはないでしょう.ですが,僕,そしてきっとほかの全てのコンテスタントは,問題を解く楽しみに魅かれてIOIにやって来るのです.IOIのために嫌いなことをする,というのは,まあやってもいいとは思いますが,僕の個人的な意見ではそれは本末転倒だと思います.故に,僕は "output only task" の対策を怠ったことを,そこまで後悔してはいません.無論,もっと練習していればもっとよい得点が取れたのではないか,と考えてしまうことも事実です.ただ,"output only task" の文字列を見た瞬間動揺し,また競技中においても,本来なら競技練習日気づいておくべき仕様に躓き,その対応に追われて時間を浪費してしまったこと,これについては本当に悔やんでも悔やみきれません.後述しますが,競技1日目は,あともう少し時間があればかなり得点を伸ばせた可能性がありました.つまり,"output only task" に対する心構えがなかったばかりに,他の問題の得点まで失ってしまったかもしれないのです.そう,心構えが本当に大切なんです.この種の問題が出るかもしれないという心構えをして,競技練習日に少し練習しておけば,結果は変わっていたかもしれません.
さて,僕が実際にコンテストでどのように立ち回っていたかについて話をしていきます.競技開始とともに,"output only task" の文字列を見た僕は,正常な判断力を失ったのでしょうか,他の2問に目を通すことすらせず,"output only task" に突撃します.突撃する瞬間,僕は,この問題は何があっても10時(競技開始が9時なので,それから1時間後)までにある程度の点数にして,そのあとはこの問題には手を触れずにほかの問題にとりかかろう,と考えました.この作戦に問題はなかったと思います.現に僕は,そこそこの点数が取れそうな解法を9時45分くらいに実装およびバグ取りを終えました.実行すべき入力ファイルは10個あるので,一つ1分くらいで実行すれば十分に間に合うと思いました.とりあえず僕は,一番小さい入力ファイルに対してプログラムを走らせ,その出力をコピーしてテキストファイルに保存,提出しました.ここで,予想外の Wrong Answer,0点が返ってきます.結論から言えば,出力の内容は正しかったのに,テキストファイルへの保存方法が悪いために起きた Wrong Answer でした.これは,競技練習日に練習しておけば,その時に確実に気づけたミスです.しかし,何もしていなかった僕は,自分の出力が正しくないのではないかと疑い始めます.ソースコードをひたすらに睨み,あるはずのないバグの影を追い,何も得られないまま時間が過ぎていきました.2,30分経った頃でしょうか,完全に手詰まりになった僕は,なんとなくプログラムの出力を直接ファイルへ書き込むようにしてみました.すると,正の点数が得られているではありませんか.その瞬間,完全にあきらめかけていたところで解決策が見えた喜びと,あまりにもくだらないミスで貴重な時間を溶かしてしまったことに対する悲しみが,同時にこみ上げました.結局,予定より30分ほど遅れて,79.66点を得ることになりました.
残す問題は2つです.問題分を読むと,wiring という問題が,大会直前に解いた問題によく似ています.とりあえずこれをさっさと通して景気づけにしたいと思い,迷わずこれに突撃しました.ところが,思った以上に考察がうまく詰められず,この問題でやっと100点を獲得することには,コンテストの残り時間は1時間ほどしかありませんでした.競技1日目の得点は,少なくとも200点は欲しいです.死に物狂いで最後の問題,train に取り掛かります.すると驚くことに,たった5分で方針が見えてきたではありませんか.最後に簡単な問題が残ったんだな,よかったよかった,などと思いつつ,解法を実装します.しかし,0点.実装にあからさまなバグが見つかったので直して提出し,0点.何度か似たようなことを繰り返しますが,全然点が取れません.しかし,13時30分あたりで,最初の方針では微妙にカバーできないケースがあることに気が付きます.これを直すと,11点や16点が得られました.この時点で,実は満点解法にかなり迫っていました.問題のネタバレになるので詳細は省きますが,簡単に言えば,処理A,Bがあって,A->Bの順ですべきところを,B->Aの順で行っていたため,多くのケースで点数が得られなかったのです.しかし,それに気が付く前に,コンテスト終了の合図が響き,競技1日目は終了しました.コンテストが終わった後,train が実は難問であったこと,大まかな方針は正しかったことを知り,相当落ち込んだのを覚えています.ただ,金メダルラインには乗っていたので,それでかなり安堵したことも覚えています.
結局僕は,train を落としてしまった後悔と,金メダルが取れそうという希望の二つが混ざった微妙な精神状態で競技2日目に臨みました.競技が始まると,僕はまず,ちゃんと全ての問題文に目を通しました.すると,books という問題が簡単に見えたので,まずこれに取り組みました.簡単な見た目の通り簡単に満点解法が見えたので,これを実装して,50点が得られました.ここで僕には二つの選択肢がありました.一つは,他の問題にいったん移り,また時間があったら戻ってくるという戦略,もう一つは,books に突撃し続けるという戦略です.競技1日目,解放がほとんどわかったはずなのに満点を取れなかった悔しい記憶が頭を遮り,僕は後者の戦略をとりました.ここで後者の戦略を取ったこと,それ自体は間違いではなかったと思います.しかし,この戦略に固執し,12時まで得点を1点も増やせずに椅子に座っていたのは明らかに間違いでした.他の問題で時間を浪費して伸ばせるはずの得点を失った悔しさは,全く反省に活かされていませんでした.残りの問題について考えてみると,prize という問題が簡単そうだったので考えました.実際これは簡単で,13時ごろには100点を得られました.残すは simurgh という問題でした.これも実は難問だったようなのですが,運よくすぐに方針が見えました.方針が間違っていないことを入念にチェックした後,実装に移りました.しかし,これは結構処理が面倒くさく,いろいろとバグを埋め込んでしまいました.結局,14時直前の提出でも,30点しか得られませんでした.ここで完全に諦めムードに入ったのですが,奇跡が起きました.なんと,コンテストシステムに不具合が起きていたため,コンテスト時間が15分延長されたのです.このチャンスを絶対に逃してはならないと思い,必死にデバッグをすると,得点が70点まで伸びました.そして,また奇跡が起きます.なんとコンテスト時間がさらに15分延長されたのです.再度気合を入れなおし,ひたすらデバッグします.そして,コンテスト終了1分前のアナウンスがされているころ,ついにバグの正体をつかみました.急いで修正しますが,もうコンパイルをする時間すら残っていません.14時29分57秒,僕の最後の提出が受理され,その直後,コンテストが終了します.そのあとは,お昼ご飯を食べている間も,結果が見られるようになるまでずっとこの提出のことで頭がいっぱいでした.バカみたいなタイプミスでコンパイルに失敗したらどうしよう,とか,最後の変更の直後に ctrl+S を押し忘れていたらどうしよう,とか,そもそも他にもバグがあるんじゃないだろうか,とか,いろいろと考えてしまいます.解析の時間になり,コンテストホールに入れるようになっても,まだジャッジの結果は見ることができず,大いに気をもみました.隣に座っていたオーストラリアの選手が,結果が出た,と叫ぶ声を聞くと同時に,僕は自身の提出画面を開きました.100点です.このときほど感動した瞬間は今までの人生でなかったと思います.少なくとも,競技プログラミングで泣きそうになったのはこれが初めてでした.この提出のおかげもあり,僕の順位は競技終了1日目から10位ほど上がり,4位を取ることができました.
このように,最終的には非常によい順位を獲得することができたのですが,これはほぼすべて運によるものだと思います.正直のところ,コンテスト中の立ち回りに関しては去年と比べても全く成長していないです.もし "output only task" のことを少しでも念頭に置いて練習していたら,もう少し洗練された立ち回りがコンテスト中にできていたら,僕の順位はまだ上がる余地があったのではないだろうか,そんなことをどうしても考えてしまいます.
この文章を書いた目的の半分は,僕の気持ちに一定の区切りをつけて,すっきりさせることです.しかし,当り前ですが,こんなところで僕がどんなに喚いても結果は覆りません.それでも,この僕の経験が,後悔が,未来のIOI選手に少しでも役に立てばいい,そんな思いも込めて書きました.ところでこの文章,改めて見てみるとかなり恥ずかしいことを書いていますね.それだけ僕が疲れているのだと思って,温かい目で見ていただければ幸いです.
ずっと競技の話,というか自分語りばかりしてしまい,IOI全体については全くよくわからない感想文になってしまいました.実は僕は,あまりに疲弊してしまったためにエクスカーションを1日休むなどしていて,他の選手よりもエクスカーションに関する記憶が乏しいです.なので,エクスカーション等については他の選手の感想文を読んでいただくとよくわかると思います.こんな駄文に長々と付き合っていただき,ありがとうございました.
- 河原井 啓 (筑波大学附属駒場高等学校3年)
このIOIは,他のメンバーと違い,自分にとって初めての国際大会でした.しかし他の選手と同様,大会を楽しむことができました.
0日目,羽田空港に集合して直前研修をしたあと,深夜の飛行機でテヘランに出発しました.窓から中国の夜景が見えたり,空中の雷が見えたりして楽しかったです(その後ちゃんと寝ました).テヘランについてからは鳥だけの動物園のようなところに行って,イランの美しい公園を楽しみました.
1日目,競技のプラクティスと開会式がありました.プラクティスはJOIでも行われているような普通のものでした(ただし,問題は事前に公開されています).開会式では様々なハプニングもありましたが,イランの伝統的な音楽や現代的な音楽を楽しむことができました.
2日目,競技の1日目でした.自分は終了の1分前に提出したコードで点数を伸ばすようなことをしていて,心臓に悪かったですが,終了時点で金メダル圏内にいることができました.その後のネイチャーブリッジ観光では,テヘランの夜景がきれいでした.
3日目,エクスカージョンの1日目でした.午前中はイルカのショーで,日本では見ない変わった芸を見られて楽しかったです.午後に行ったミラドタワーは,見た目は京都タワーのようなのに,高さが400メートル以上あって,そのギャップが面白かったです.
4日目,競技の2日目でした.この日は30分コンテストの延長があったのですが,その延長時間に得点を伸ばしたりとまた心臓に悪い展開でした.あまりコンテストの感触は良くなかったのですが,結果として5位になり,金メダルを取れてよかったです.午後は植物園のようなところへ行き,夜中の12時頃まで散歩をしたり,星を見たり,食事をしたりしました.
5日目,エクスカージョンの2日目でした.午前中はoparkというプールに行きました.ウォータースライダーがとても怖かったです.午後はアザディタワーに行きました.これはタワーというより記念碑的な感じで,周りの芝生でイラン人がピクニックをしていました.
6日目,閉会式がありました.朝は5時に起きて山にハイキングに行きました.イラン人は山に何も持たずに登るようです.午前中はグランドバザールに行って,イラン人の熱気を肌で感じました.午後の閉会式では,また様々なハプニングがありましたが,イランの伝統的な踊りを楽しむことができました.あっさりと書いてみましたが,濃い性格のガイドさんや面白い団長団や個性豊かな選手団に囲まれて,とても充実した大会でした.
と帰りの飛行機の中で書いているのですが,隣に座っている二人の感想文が長そうなので,イランの食事について書こうと思います.
まず,イランの主食はインディカ種の米です.朝食ではパンが出たりもしますが,昼食と夕食はほぼ全て米でした.米は白米として食べることもありますが,スパイス(イランのスパイスはほとんど辛くない)と一緒に調理されて出てくることが多かったです.
また,米にはカレー(のようなもの)をかけて食べることが多く,様々な種類がありました.ここで気をつけないといけないのは,イランのカレーはほとんど辛くなく,むしろ甘いものまであるということです.自分は昼食などで緑色の香草系の味のするカレーを好んで食べていましたが,茶色の甘い味のするカレーは,初めて食べたあとは誰も手をつけようとしませんでした.
次にイランの主菜について書くと,これは豚肉以外はだいたいあります(豚肉はイスラム教で禁止されているため).まず鶏肉は,イランの辛くないスパイスに付け込まれて煮込まれているものや,手羽先焼きみたいに焼かれているものなどがあります.ユニークだったのが,米の中に鶏肉が入っている料理で,チャーハンのようなものではなく,鶏肉がメインの料理でした.美味しかったです.
次に牛肉は,ひき肉にしたものを棒状に固めて焼いたものしか見ませんでした.これにはチーズのかかっているものとそうでないものの2種類がありました.これも美味しかったです.
魚は,焼かれているものとフライにされているものがありました.この内焼かれているものは,日本のニジマスのような味がして,とても懐かしいと思いました.フライの方は普通に美味しかったです.
副菜は生野菜を結構食べているようですが,自分はほとんど食べませんでした.
飲み物は大きく謎の乳製品,ジュース,果汁系炭酸水にわけられます.謎の乳製品は日本ののむヨーグルトから甘さをなくして塩を追加し,1.5倍位に薄めたようなものです.正直美味しくありませんでした.でもイラン人は好んで飲んでいるようです.
次にジュースは,オレンジジュースとチェリージュースを見かける機会が多かったです.これはどちらも美味しいです.
そして,果汁系炭酸水はイランでとてもポピュラーな飲み物で,ファンタのようなものです(もっと炭酸は弱い).ただ,味が少し独特で,レモン味と書いてあったものは梅ジュースの味がすると言っていました.
と,バランス良く食べるものが揃っていて,イランの食事は結構安心して食べられました.満腹.
- 坂部 圭哉 (海陽中等教育学校6年)
大会に行く前,IOIと団長から練習問題が出ていたのですが,殆ど解けずにいたので,「僕みたいな人間が行って大丈夫なのだろうか」と,自信を無くしていました.直前合宿で他の3人の選手と会い,彼らは自分とは違いこれらの問題がまあまあ解けるということを知り,更に自信を無くしました.このように,出発の時,かなり自信がありませんでした.
飛行機はイランへの直行便が存在しないので,ドバイで1度乗り換える経路でした.行きのドバイ空港では,元々1時間しか乗り換え時間が無い予定だったのですが,私は,飛行機の乗り換えは2時間くらい必要だ,と思い込んでいたので,1時間しか無いと知った時は驚きました.実際はスムーズに乗り換えることができたので良かったのですが,どこかが混んでいたら間に合わなかっただろうと思います.ドバイの空港は,大きく,ターミナル間を往復する鉄道(新交通システムのようなもの)が地下にあったことが印象に残っています.
テヘランの空港に到着したのは,現地時間の昼頃でした.そこで日本担当のガイドに会い,挨拶をし,その後ホテルに移動しました.選手の部屋は2人部屋で,私は河原井選手と同じ部屋になりました.その日の午後は,"Birds Garden"へエクスカーションに行きました.鳥専門の動物園のような場所で,鳥だけでなく,木を多く植えるなどの雰囲気を良くする工夫が為されていて,楽しむことができました.夜は長旅で疲れていたので,早めに寝ました.
次の日は,プラクティス(実機練習)をしました.キーボード配列を確認したり,トイレの行き方を確認したりすることができ,プラクティスを有意義に活用することができました.午後は開会式に出席しました.開会式は"Milad Tower"という,イランで最も高い塔の近くで行われました.開会式では,ハプニングもありましたが,イランの音楽などを披露していただき,楽しむことができました.次の日はコンテストの日なので,意識して早く寝ました.
コンテスト1日目になりました.飲食物は持ち込めませんでしたが,その代わりにジュース・果物・お菓子がもともと用意されていたので,飲食物には困りませんでした.始めから終わりまで点数が伸びず,前述の通り自信も無かったので精神的に辛かったですが,終わった後に自分がメダル圏内にいることを知ると,かなりほっとしました.コンテスト後には,納得できない点を抗議するアピールタイムがあるのですが,特別アピールすることはありませんでした.その日の夜はエクスカーションに行きました.目的地に着くと,まずプラネタリウムを見ました.せっかくのプラネタリウムなので,満天の星空を見たいと思っていたのですが,太陽系の説明だけで終わってしまい,少し残念でした.また,このプラネタリウムの特徴として,3Dであることが挙げられます.始まる前は,物珍しく思っていましたが,始まってみると酔ってしまいそうな映像が多く,「3Dプラネタリウムは辛い」という気持ちになってしまいました.プラネタリウムが終わると,屋外で夕食を食べた後,"Nature Bridge"を観光しました.3層の橋だ,と言っていたので,瀬戸大橋のように層によって異なる乗り物が通るのかと思っていましたが,実際に見てみるとどの層も全て歩行者用の通路で,3層にしたのはデザインのためだったようです.きれいな夜景が見える場所として現地人にも人気でした.
次の日は,朝食後から夕食前まで,丸一日エクスカーションに行きました.夕食前にはホテルに帰ってこれる日程は個人的に嬉しかったです.午前は,イルカショーを見に行きました.基本的にはジャンプしたり,投げた物を取ってきたりと,よくあるイルカショーでしたが,最後に人間とイルカが共同で水中でパフォーマンスをしていて,これは日本には無さそうだと思いました.その後,Milad Tower(開会式場近く)のふもとのフードコートで昼食を食べました.美味しそうに見えた魚と米を注文したら,とても日本食っぽい味がして,とても美味しかったです.この魚料理はイランによくあるそうなのですが,とても日本らしくて楽しめました.午後は,Milad Towerに上りました.Towerの上からテヘランを眺めて,テヘランという都市自体についていろいろ考えていました.コンテストに備えて,夜は早く寝ました.
コンテスト2日目になりました.Day1で自信が少し戻った上,1完することもできたので,精神的にはかなり楽でした.問題が簡単だったのではないかと恐れていましたが,コンテスト後に自分の順位が銀メダル圏内に上がったと知った時は,嬉しかったです.アピールも無くコンテストは終わり,夜は植物園に行きました.イランということもあり,高山系の植物が多かったです.その後,植物園の近くの広場で夕食を待ちましたが,なかなか出てこなかったので,ひとまず日本チームは中国チームやアメリカチームと話しながら待つことにしました.その待つ過程で撮った,IOI2017の1位〜5位が全て写った写真は,私のお気に入りだったりします.夜10時くらいになってようやく食事が出てきて,ホテルに帰った頃には日付が変わっていました.
次の日はエクスカーションの日で,プールと"Azadi Tower"というモニュメントを訪れました.プールには様々なウォータースライダがあって,ただ滑るだけのものだけでなく,複数人で浮き輪に乗って滑るタイプのものもありました.ジェットコースターのように下方向に高速で落ちるものが多く,苦手な私は怖い思いをすることがありました.その後Azadi Towerへ行き,全員で集合写真を撮りました.Azadi Towerの地下には博物館のようなものがあり,天然石や歴史的な遺品などが展示されていました.天然石は好きなので,見られたのは非常に良かったです.この日の夜は早く寝る予定だったのですが,荷造りをしていたら日付けが変わってしまっていました.
次の日は任意参加の早朝ハイキングがあったので,とても眠たかったのですが,朝4時半に起きました.どこに行くのか分からないまま参加したのですが,山に行く予定だったらしく,山登りの好きな私はラッキーでした.イランの山にはほとんど植物が生えていないのですが,その割に犬や猫がたくさんいました.イランの山の岩も観察できて,楽しかったです.ハイキングの後,地元の市場にタクシーで行きました.市場では,たくさんの工芸品や食べ物が売られていましたが,すでにたくさんのお土産を買ってしまっていたため何も買いませんでした.昼食を食べた後に暇があったので,外国人と碁を打ちました.まだ決着はついていませんが,普段日本人同士でしかしていない碁を外国人と打てて,楽しかったです.そしてその後,閉会式がありました. 閉会式の場所は,開会式とは違いました.
閉会式では,ダンスや歌もありましたが,最大のイベントはメダルの授与と表彰でした.私は銀メダルをそこで貰いました.自分の実力が出た大会だと思うので,銀メダルが取れてとても嬉しいです.今年のメダルは円形ではなく,ユニークで面白いと思います.私以外の3人は上位5位以内に入り,特に髙谷選手は世界一を取り,さらに日本が国別順位で初めて1位を取るなど,日本にとってすごい回のIOIに来てしまったなぁ,と感動していました.
- 髙谷 悠太 (開成高等学校3年)
今大会の観光や運営などについては他の選手の参加記からもよく分かると思うので,これからJOIやIOIに参加したいと思っている後輩たちに向けて,実際にどのような態度で試験を受けているのかということを中心に述べていきたいと思います.(実際はすべて載せると大変長い駄文になってしまうため,抜粋しただけです.)
・直前学習会
今年の直前研修は昼から始まった.まず,研修では競技規則の確認を行った.特に見落としていたことはなく,いつも通りのルールであることに安心した.そして,後半の問題解説に移った.事前に団長さんから配られていた問題の解説である.ほとんどの問題の解法は考えていたが,(おまけ)と書かれたシラバス外の問題はあまり考えていなかったため,それらの解法を聞いて新たな知見を得ることができた.また,シラバス内の問題でも,思っていた解法よりも計算量がよくかつシンプルな解法を聞くことができた.あまり解法を詰めていなかったことを悔やんだが,解説の行間を埋めたりすることで,少し頭を動かすことはできた.
解説が終わり,その日の内に出国した.便を待っている間,選手内で川崎選手が作問した問題を考えていた.しかし,結局きれいな解法が見つからず,悲しい気持ちになった.
その後,ついに飛行機に乗り込んだ.直前の別の大会での疲れが残っていたため,最初の10時間はずっと寝ることができ,暇を持て余さずに済んだ.後半の便は2時間であったため全く寝ることはできなかったが,なんとか無事にイランに着くことができた.
・イラン一日目
選手の泊まるEvinホテルに着いてすぐ昼ご飯を食べた.昼食はバイキング形式であった.初日ということもあり,今後の食事にどの料理が最適かを決めるため,できるだけ多くの料理を取ったが,どの料理もスパイスの使い方が同じなのか味が似通っており,あまり食事を楽しむことができなかった.
まだ疲れが残っていたため,午後のExcursionのBird Gardenには行かないことにした.実際参加した人たちもあまり楽しくなかったようで,不参加にしたことは正解だったようである.
ドルを両替して,現地のお金レアルを獲得した後,団長などの大人が泊まっていたAzadiホテルで夕食を食べた.昼食と食事はほぼ同じであったが,夕食では砂糖歓迎激甘カレーを食べることができ,他の料理がよく分からないスパイスの味しかしないなか,別ベクトルの味として楽しむことができた.
・イラン二日目
朝はPracticeの時間であった.実際のコンテスト会場・環境に触れて,あらかじめ渡されていた問題を解く,という時間だ.いろいろ忙しかったため,実装するのはぶっつけ本番になってしまったのだが,どの問題も解法をきれいにすると実装がとても楽になったため,難なく通すことができた.ただし,output-only task であったSudokuという問題は解かずに放置した.
また,コンテスト環境はいつもと少し異なり,Call staff やTestingという新たな機能がついていた.Call staff という機能ではトイレや計算用紙をもらうためにstaffを呼ぶことができ,トイレに行きたくなるたびに毎回手をあげたり,無駄な紙を印刷して裏面を使ったりせずに済むようになった.また,Testingという機能は直前研修で聞いていた通り,テストをして実行時間や使用メモリを見ることができた.この機能には,コードを提出すると,提出時間の欄に誤って提出コードの実行時間が表示されてしまうバグがあり,見事それを発見することができた(川崎選手がcommitteeの人に伝えてくれた.)ただ,手元実行で十分なケースが多く,コンテスト中には使わずに終わったため,本番に修正されていたのかを確認するのを忘れてしまった.本当に直したのか気になるばかりである.
そして,午後は開会式が開かれた.英語と現地語(ペルシャ語)で同じことを2回繰り返す仕様になっており,退屈なペルシャ語に少し気分を下げられてしまった.様々な民族文化の出し物を織り交ぜながら,各国の紹介が行われ,どこかの国が投げていたチョコレートをゲットすることができた.開会式で投げられたお土産を得られたのは初めてであり,少しテンションが上がった.しかし,いつも通りの各国紹介に退屈して注意力を失ってしまったため,運営のミスに気付くことができなかった.というのも,いくつかの国の国旗を間違えていたのだ.国旗素人にはどうせ気づかないと思うかもしれないが,北朝鮮と韓国の国旗を間違えていたらしく,これを見逃したのは大変もったいないと思った.
その後は集合写真などをいくつか取って,ホテルへと帰った.Quarantineといってネットが使えなくなるため,最近解いた問題の復習を自分でまとめたものを読んですぐ寝た.
ついに明日が競技1日目である.
・イラン三日目
前日9時にベッドに入り,6時半に起きた.朝食はいつも通り軽く済ませたが,目を覚ますためにカフェモカを飲んだ.ルールでは軽食の持ち込みは禁止とされていたが,ガイドさんが持ち込めると強く押してきたため,この日はバックにお菓子とお茶を入れて会場まで行った.しかし例年のようにガイドさんが会場まで付き添ってくれることはなく,バックをガイドさんに預けることができなかったため,ホテルまで持ち帰る必要があった.さらに,お菓子やお茶も結局持ち込めなかったため,筆記用具と上着だけおいて全て持ち帰る羽目になってしまった.しかし,ホテルまでの往復(今年の会場はホテルに隣接していて徒歩で移動できた)の間で,他の国のガイドさんや日本大会のために視察にきたJTBの人たちに会うことができ,その応援を励みにしてコンテストに臨むことができた.
そして,いろいろあったが準備万端でコンテスト初日が始まった.特に開始も遅れることはなかったが,CMSのページが開かれ,Overviewにoutput onlyを見つけてしまった時は少し怒りを覚えた.というのも,output onlyの課題では一般的に満点を取るのが不可能であり,誤差ともいえるような点数差で順位が入れ替わりがちであるからだ.しかし,とにかく気を取り直して,他の2問を読んだ.
んん?あれれ?おー!
最初に見た課題(wiring)が直前研修でやった問題ととても似ていたのだ.しかし求めたいものは全く異なるため,同じテクニックが通用するかどうかは分からなかった.さらに,もし同じテクニックを使うならばad-hocの問題の中でも難しい枠に入るだろうと思い,ならば簡単枠はこれだということで3問目のtrainに時間を費やすことにした.しかし,1時間経っても何も有用なことが得られなかったため,先のwiringに戻った.直前研修での解法の証明を思い出し,同じような手法で証明を試みると実際にできた.そのため,実装することにした.とても実装は軽くすぐに提出をし,実際に満点が得られた.そのテクニックは研修で初めて聞いたため,自分の幸運を喜び,証明しているにも関わらず,満点を15分程度でとれたことに少し疑いを感じた.しかし,気を取り直して3問目に戻った.その前に書いていた落書きをもう一度見返してみると,”後ろから見る”手順を実行している形跡があり,これを利用すれば解ける気がしてきた.そうすると,各頂点に対してそこから戻っていくのではなく,各充電器についてそこから戻っていけば解けることが分かってきた.だがそれを実装しても23点しか得られなかった.この課題にはたくさんの部分点があり,そのおかげで充電器が一つの場合にしか解けていないことが分かった.この部分点は満点解法の一つ手前,つまり,最後の部分点であったため,これが解けているということは満点も間近であるという確信を得た.そこから,一つ嘘解法をしたが,”充電器から戻る”という基本方針を忘れずに頭でぐるぐるしていると,満点解法が分かった.そのまま実装すると満点が得られた.ちゃんと証明はしたが,論理的にその解法にたどりついたわけではなかったため少し変な気分になったが,output onlyに3時間余せたことに安心感を得た.
ここからはoutput onlyだけに集中した.まず,各データの特性を見るため入力ファイルをのぞき,連結性を確認すると,2ケースが岩0であり,残りも岩が疎にしか置かれていない(ただし非連結なこともある)ことに気づいた.とりあえず岩0のケースを手で構成し,それらのケースで無事9割を取ることができたため,ここからが本番だとスイッチを入れ替えた.とりあえず最初の一時間 ”穴があったら埋めたい” という方針を実装した.しかし,0点ばかりがかえってきてなぜかと考えるとそもそも答えがinvalidであることに気づいた.そもそも大きいサイズの入力ではTLEしていたため,validなケースを作る方法を考えることにし,一旦すべて木を生やしてから,そこに木を作るために木を消していけばいいと分かった.それを実装すると88点を得ることができ,乱数要素があるため,何回も繰り返してみることにすると,89点まで伸ばすことができた.しかし,そこからの残り1時間ではスコアを0.07点しかあげることができなかった.あまり乱数要素が大きくないため,何回も繰り返しても点数はほとんど伸びないことに気づくべきだった(というか気づいていた.)しかし,別のアルゴリズムで点数が伸びるかどうかの疑念と,時間をかければ0.01点でも伸びるのでそっちを優先すべきかもしれないという疑念に挟まれてしまい,結局消極的な後者を選んでしまった.コンテスト後にOBの解法を見ると,シンプルかつ自然な手入れを少ししてやるだけで数点(>1点)上がると分かった.コンテスト後すぐは1位であったが,ジャッジキューが消化し終わると2位に下がってしまったため,先の消極的な姿勢を悔んだ.しかし,「一位と自分がミスせず次の競技を切り抜ける確率」よりも「自分がミスする確率」の方が大きいと自分に言い聞かせ,気分は少し良くなった.
Analysisの時間は特に問題がなく,そのまま競技後の観光に臨んだ.コンテストの疲れもあり,その日は帰ってすぐに就寝した.
・イラン四日目
この日はエクスカーションに参加した.午前はイルカショーであったが,解説がすべてペルシャ語であったため,何をやっているのかあまり分からなかった.
そして,午後はMilad Towerに行った.昼ご飯を食べている最中は混雑もひどく,後から合流した団長たちは注文するのに一苦労のようであったが,食べ終わったころにはさすがに混雑もやんでいた.そしてエレベーターで最上階へ行くと,軍用地や古い空港,ぐるぐる巻きの高速道路など,テヘラン独特な街並みを一望することができた.空気があまりきれいでなかったため,そこまで遠くを見渡すことはできなかったが,望遠鏡が無料で使えるようになっており,拡大して細かいところまで見ることができた.また,このタワーでは静電気がよく発生し,一時は何に触っても静電気が発生した.そのため,日本選手団の中で”静電気をためる”ゲームが流行り,静電気をためて相手にアタックしようとすることもあった.それぐらい静電気が発生した.
タワーの見学が終わると,この日のExcursionももう終わりであった.Towerのふもとにあるスーパーでひまわりの種とフルーツバーを買った.意外とひまわりの種は日本でも売っているらしく,あまり面白くないなあと思ってしまった.副団長さんネタばれしないでよ~~
お土産も買い終わり,団長団ともお別れになった.明日の競技に向けてのQuarantineが始まり,食事の最後には少し緊張してきた.そして,day1の前日と同じように,解いてきた問題を見返した後,ベッドに入って寝ることにした.しかし,「明日で競技最終日だ…」とか「昨日一位の選手が満点を取ったら…」などと考えると眠れず,そのような思考を止めてもなかなか頭が寝付いてくれなかった.しょうがないので,解いていなかったJMO本選の問題を考えていた.解けない間は「もし似たのがday1のように出たら解けないじゃん…」と思って寝付けなかったが,結局解けてハッピーになった.その時点で9時に布団に入ったはずが11時になっており,結局7,8時間しか寝れなかった.
・イラン五日目
しかし,起きたときそこまで眠い訳でもなくいつもと同じようだったので,ふつうに朝ごはんを食べた.しかし,最近よくある「コンテスト前の微熱+おなかの調子の微悪」が復活して,すこし心配になった.しかし,薬をちゃんと飲んで自らを鼓舞し,day1での反省を踏まえて,眼鏡と筆箱と上着だけを持って行った.全く問題がなかったため,会場で持て余す時間も増え,「見ることすなわち支配すること」という格言(本当にあるかは知らない)に基づき,会場をぐるっと一周して辺りを見渡した.実際には会場は1階2階と2つあったためすべては支配できないであろうが,視野を広くもとうという気持ちを意識的に持つことができたと思う.そして,コンテスト直前の体調微悪を抑えるため,目をつぶって瞑想し,コンテスト開始に備えた.そして,ついに最後の競技が始まった.
Overviewを見るとすべての課題にBatchと書いてあり,あれっCommunication Taskはないのかと少しびっくりしたが,問題を見ると実際はinteractiveの課題が2つあった.まず全ての問題に目を通し,10^6->線形or定数の軽いlog解法->アルゴリズムが単純->簡単枠,という思考過程で最易枠がBooksだろうという予想を付けた.実際問題文を見たところ,それっぽい解法が見つかり,簡単という予想からどうせ満点だと思い,実装して提出した.しかし実際は50点であり,何が間違っているのか分からずパニックになってしまった.
そして1時間悩みながらも何が間違っているのか分からなかったため,他の二つの課題に移ることにした.どちらかというとPrizeの方が簡単に見えたためそちらにとりかかったのだが,平方分割してその中で二分探索というありがちな解法に気づかず,変な解法を1時間かけて見つけ,それを実装した.すると,96点当たりの点数を取ることができたのだが,day1では1.7点差ぐらいで負けていたため,ここは満点を取らなければいけないと思い,少し嘘解法ではあるのだが,パラメーターの値を小さめにとってごまかし,見事(微妙に嘘な)満点を取ることができた.2年前のTownsという問題でも嘘乱択(あまり当たる確率が高くない乱択)で満点を取っていたため,またやってしまった…という気持ちになったが,とりあえずrejudgeがかかっても96点付近を取れるので,安心して残り2問に戻った.相変わらずBooksの嘘解法がなぜ嘘なのか分からなかったため,Simurghを考えることにした.とりあえずO(m)クエリではできるだろうと思って,subtask4以降を考えていた.しかし,なかなか分からず,なぜかBooksの嘘が分かってしまった.そこで,区間を繋げて木dpということが分かり,実装したがまた嘘であった.というのも区間を繋げるステップを間違えていたのだ.真面目にやろうとすると,とても実装が重くなる気がし,残り2時間を切っていたためあまりできる気がしなかった.そこで,もう一度制約を確認し,さっきのような強実装ではlogもつくし定数も重いし通らないのではという気持ちになってきた.そこで,はじめの思考に戻り,”アルゴリズムが単純”という可能性を疑うことにし,木dpの遷移がグラフの辺を移動しているようであったので,最短路問題に帰着できるのではという仮定が見えてきた.その仮定を信じると,本当にO(n)辺の01-BFSに帰着できた.実際01-BFSはO(n)で解けるため,10^6制約であることに納得でき,もう解けると確信した.ちょうどトイレに行って思考を整理していた段階であったため,急いで席まで戻り,すぐに実装した.もちろん実装は慣れているdijkstraで書き,定数が軽いのでlogは大丈夫,と信じるとちゃんと満点が帰ってきた.その時点で残り時間は1時間半であり,落ち着いてSimurghに取り掛かろうと気持ちを切り替えた.とりあえず部分点を回収するため,解けると思っていた部分点解法を詰めることにすると,いい性質が見えてきた.するともう解法が見えてきて,”とりあえず二分探索”という定石を使える形になり,本当に二分探索するだけになった.実装時間に少し余裕があったため,部分点解法を実装したが,それは0点であった.いくつかバグを直してもWAのままであり,最終的にはジャッジトラブルが入って結果が返ってこなくなってしまった.しょうがないので,満点解法を書いてからデバックをすることにしたのだが,意外と落ち着いていたのか,いくつかのところで実装が面倒なところを省くことができた.これは前の実装でバグらせていたために,こっちはバグらないようにと気を付けていたからかもしれないし,単に面倒な実装が嫌いで避けたかったからというだけかもしれない.とにかく後半の実装は終わったが,まだ前のコードの結果が返ってきていなかったため,今書き上げたコードをとりあえず提出して,デバックに切り替えた.すると,明らかに間違っている場所があり,それを先の部分点解でも直して,部分点解法と満点解法を両方とも出した.そのころもまだジャッジが不安定であったため,コードによって結果が返ってくるかどうかはまちまちであった.そのため,(ジャッジには申し訳ないが)同じコードを何回か出してみると,たまに結果が返ってきて,まず部分点解法がちゃんと51点を取り,その後,満点解法が100点を取った.
こうして,無事300点を取ることができ,つかの間の幸福感を得ることができた.とりあえずPrizeが微妙に嘘解法なため,少しやり方を変えると無事100点を取ることができた.この時点で残り7分であり,感傷に浸った後,Minesweeperを始めた.しかし,先のようなジャッジトラブルにより,15分,また15分と試験時間が延長されてゆき,他人の点数がどんどん上がっていく中,day1一位の人が全完していないかと私の心拍数もどんどん上がっていった.そんな中ではあるが,順調にMinesweeperを進めることができ,”推理不可能詰みました”の状態から3回連続で当たりを引くことができた.しかし,結局最後の2択を外し,最後の2,3分はただただ祈っていた.そして,コンテストは30分の延長で無事終了し,一位であると分かった.そのことに安堵+歓喜し,昼食を迎えた.
昼食では日本から一緒に来ていたOBの方々がCongratulations!と言ってくれた.海外選手もCongratulations!と言ってくれた.とてもうれしかったが,歓喜の舞はコンテスト中に終わらせていたからか,その時は達成感の方が大きかった.Analysisの時間には詰まっていたジャッジの結果が公開され,なんと日本チームは1,4,5位を独占し,総得点では堂々の一位であった.
今年の問題はきれいな解法が存在する問題が多く,はまったとしても正しい解法が分かればすぐに満点が取れる仕様になっていたと思う.今年のセットには,普段から時間をかけてでも難しい問題に挑む,という練習をするのが得策であったと思うし,これは今年に限ったことではないと私は思う.
少し話がそれた.無事Analysisを終えて,Botanical Gardenへ行った.そこではたくさんの植物があったが,Iranは危険なため,あまり自由行動ができず,好きに歩き回ることはできなかった.
・イラン六日目
この日の朝はプールに行った.どこに行くか聞いたときに,ガイドさんのWaterparkの発音が変だなあと思っていたのだが,O parkという名前のプールだった.
次はAzadi Towerに行った.Azadi Towerは面白い形をしていたが,バスで寝ていたため,寝起きの直射日光に負けてしまい気分はあまりよくなかった.しかし,地下にある博物館は雰囲気もよく,とても面白かった.
・イラン七日目
午前中はタクシーで移動して,地元の商店街に行き,Iranian Carpetを買うことができた.ついでに盃のような銅カップを買った.怪しい食べ物を回避しながら,無事ホテルへ戻った.
そして,Closing Ceremonyが始まった.例年のように,一位は別表彰でトロフィーを獲得することができた.スタンディングオベーションが起こった.緊張してひたすら前を向いており,全体を見渡せなかったことはとても後悔している.英語でスピーチできるかいと言われて少しと答えて全くできなかった.英語を勉強しなければ.
そして,たくさんの人と写真を一緒に取った.けど手元に来ないのは寂しいね.最後の夕食はIranian Foodなのにおいしかった.甘いカレーが出たり,おいしい魚が出たりしたからだと思う.最後の夕食を楽しんだ後,バスに乗ってすぐに帰った.
ガイドさんは空港までは付き添わず,会場でのあっさりとした別れで終わってしまった.そして,後はただただ飛行機に乗って帰ってきた.二本目の飛行機が出るまでずっと寝てしまったので,帰りの飛行機は3本も映画を見てしまった.
日本に着くのが深夜だったため,ホテルに泊まらせてもらえ,各自部屋にばらけた.明日の朝は各自帰宅であったため本当はちゃんと別れを惜しむべきだったが,適当に部屋に戻ってしまった.悲しいね.
・日本八日目
日本にいるのが八日目とは言ってない.無事起床して家に帰った.