2022-11-18

ICPC World Finals Dhaka 参加記

気付いたら帰国してから丸一週間が経ってしまいました (そ、そんな...)

当日まで

普通に病院実習 (今回は形成外科) に丸被りで困ってしまったのですが、当科の先生方にご配慮頂き、まず参加できることになりました (8月くらい)
一方、9月頃まで競プロの練習が圧倒的に不足しており、力が落ちすぎてヤバいということに気付き、HELP!に (どうして...) (マッチングが悪いよ～)
9月末から週2+ペースでチーム練が始まり、徐々に勘を取り戻しつつチーム性能を向上させていき、直前には大分仕上がった気分に。
基本的な立ち回りはmaroon: 何でもやる、幾何担当 / yutaka: 考察難や数学系など担当 / hir: 面倒枠、写経担当という感じに落ち着きました。

Day1 (11/6)

前日なかなか荷造りが終わらず、2時間睡眠で成田空港へ。

明日朝6時に家を出るんですが、まだ荷造りをまともに始めていない (ただの国内旅行との差分を気を遣って準備し満足しちゃった)
— HIR180 (@HIR180) 2022年11月5日

abemaで全日本大学駅伝を見ながら眠気覚まししてました。駒澤強すぎてウケますね～

この時点でbatonさんと会い、少し雑談しました。batonさんは貴重なOI時代からの同期なので、急遽東工大のWF参加が決まって会うことができ、嬉しいね。

過年度のWFの過去問を眺めたり、ライブラリの位置を覚えたり、寝たりしながら飛行機を乗り継ぎ、夜中にダッカ着。

バングラデシュ、道路に信号がなく、車線もあまり意味を成しておらず、また教習所の教官が見たら気絶しそうなレベルの車間距離で全てが動いており、更に各々の車が挨拶代わりにクラクションを鳴らすので本当に凄いことになっていました (tatyamさんのツイートをお借りしています)

pic.twitter.com/SvFyhCbfLh
— tatyam (@tatyam_prime) 2022年11月7日

ホテルに日付変わってから到着。抗原検査して、色々準備してから寝ました。

到着です pic.twitter.com/bEV7eqt8PC
— HIR180 (@HIR180) 2022年11月6日

Day2 (11/7)

この日はteam registrationがあり、本番使うTRD (A4 25ページのライブラリ) と辞書などを提出しました。その他は、前日の大移動の疲れが全然取れておらず、ずっと座って寝てた記憶しか残っていません...

Day2です (Registrationをしたんですが、何故かTシャツを4枚も貰ってウケています) pic.twitter.com/CTH8VAZLVd
— HIR180 (@HIR180) 2022年11月7日

WF、色々予定が詰まっていて意外と忙しないなという印象になったが、実は後の日はスカスカでした。

なんか見たことのあるような名前が pic.twitter.com/73MIkxPloG
— タッパーをオーブンで焼かない (@DEGwer3456) 2022年11月7日

↑これ寝てて見逃しており、かなしい

Day3 (11/8)

この日はicpc challengeがあったんですが、諸事情あって会場に遅れて着き、既に始まっていたので参加せず、勝手にリハーサルもどきをやっていました。

その後opening ceremonyがあり、この日はこれで終了。

帰りは信じられないほどの渋滞に巻き込まれながらホテルに戻り、夕飯。

この後の検査が本番への参加可否を決めるやつで、本当にビビっていて結果が出るまで寝つけなかったが、無事に陰性となり、安心。

Day4 (11/9)

この日はリハーサルでした。

ターミナルから提出できるの便利～とか普通に問題面倒なの多くて草とか言いながら一通り解き終え、その後は自分は使う可能性が高そうなライブラリの写経をしました。

今日はリハーサルの日でした、もう宿に戻ったのであとは夕飯を食べて寝るだけです pic.twitter.com/amolvZzaKf
— HIR180 (@HIR180) 2022年11月9日

写経にまつわる裏話として、"粘着物を使ってモニターにライブラリの紙を貼り付ければ、視線移動が減り写経が高速化出来る" という気付きと、東工大チームから教えて頂いた "ランチボックスにあるポテチの缶の側面に剥がしやすいシールが貼ってある" という気付きを組み合わせることで圧倒的に効率が良くなり、もう完全に草でした (物が足りないと創意工夫が捗って、面白いですね)

夕飯を18時に食べ、部屋に帰り、引き続き写経練習としてmodint + ntt を何回か書いて満足して寝ました。寝たとはいいつつ何度か中途覚醒はしました。

Day5 (11/10)

いよいよ待ちに待った本番。

6時半に目が醒め、少しベッドでスマホを弄ってから起きました。

この時点で出発は8:25だと思っていたので、その後シャワーを浴び、のんびり朝食会場に行くと、急ぐように伝えられ、かなり？？？という気持ちになっていたのですが、
よくスケジュールを見ると8:10が最終便と書かれており、勘違いしてたなと思いきや、なんと当日7:40に変更になっていたとのこと。どういうことやねん。

バス出発が8:25だと思ってたらスケジュールに8:10と書いてあり驚いていたところ、実際の出発時刻は7:40だったらしくかなり慌てた　(6:30に起きておいてよかった〜)
— HIR180 (@HIR180) 2022年11月10日

バスの中では問題文が長くて実装も怠いが別に難しくはない、しかしあまり解かれないタイプの問題 (WF'15 MのWindow Managerという問題からWindowをManageする枠とずっと呼んでいました) を確実に一撃で殺す機運を高めながら、ライブラリの位置を最終確認し、お気に入りのプレイリストを聴きながら気分を高めていました。

会場に移動し、色々雑談し待っていると、突然時計が残り5分から1分に進められ、焦る。リハーサルでもこれやってたし来年は心の準備をした方が良さそう。

(ここからコンテスト)

問題: https://icpc.global/worldfinals/problems/icpc2021.pdf

いつも通り大きく3分割して、順番にmaroon/hir/yutakaで読んでいく。

パッと見、E: よくわからんけど難しそうだし、多分自分の問題じゃない F: 笑 G: 典型だろうけど最初じゃないな～と言う感じで、ようやくHが簡単枠。

Hは簡単枠というか既出 (？笑) (F - Bracket Sequencing) だが、少し自信がないので確認を取って、実装。このレベルの問題ですら初めてのオンサイトWFの1問目で書くと少し混乱するし提出する時心臓バクバクでびっくりした。通ってガッツポーズ (草)

次にGを読み、まあ典型なんだけどすぐ解き方が思い出せない (カス) が、とりあえず昨日まで散々練習したmodint+ntt写経の出番はありそうだなと思う。ただ序盤ではなさそう。Eは放置、Fはmaroon行き。

そうこうしている内に、Cの解法を受け取って実装することになり、簡単だけどオーバーフローとかコーナーケースが少し怖い感じだったので、落ち着いて詰めて、Jの後に通す。ここで実装やるだけ枠としてLを受け取り、少し迷走するもまあ出来るなという気持ちになる。その後にAを見て、最大の方がいまいち良く分からないな～って思っているとFが通り、Gも例の写経をすればいけると言われたので、Lより先にやることに。

↑のテクニックを駆使 & 練習の成果が出て写経は上手く行き、その後はmaroonが実は制約にミスがあったことなど無関係にすんなりACしてくれて、後から振り返るとここまではかなりいいムーブだった感じがする。(この時点では1位だった) (FAを確信したらカメラに向かってポーズを取ろうという話をしていたので、是非アーカイブを見てください)

ここから自分はAの方針を貰って、実装し通し、またBの後にLを詰めて書いた。少し実装と認識にズレがあり1ペナ吐いてしまい悔しかったが、assertに引っかかったお陰で原因はすんなり見つかり良かった。

この時点でDEIKが残っていて、Dの実装に着手していた一方で、自分はEを一応読んで考えたり、Iの手伝いをしたりして、Iが通った後はWAしてたDのデバッグ、またKもWAした後はKのデバッグをしようとしていたが、上手くいかずそのまま終了。

終了直後はD, Kをどちらも落としてしまって落胆しており、また下手したら金すら怪しい？と思ったがそれは後から冷静に↑を見て多分大丈夫であることは気づきました。

その後の会話でPekingが10完、Zurichが9完したことを本人たちから聞き、自分たちのペナは圧倒的に少ない (MIT除く) ので、Seoul NUが10完するかどうかで3/4位が決まる、というのが唯一の本質ポイントであることを理解。

会場を出た後は別の部屋で食事を取りながら東工や京大とコンテストの感想を軽く喋ったり、写真を撮られたり、引き続きDKのデバッグをしたりしてました。

閉会式そろそろスタートみたいです pic.twitter.com/nvwq41I98J
— HIR180 (@HIR180) 2022年11月10日

閉会式は、本当に各種スピーチの類が多くて長くてうんざりし始めたところでyes/noがようやく始まり、しかしyes/noもワクワクするのは最後の1~2割とかなので割と虚無で、そこまでは近くのLatin Americaのチームたちがハイテンションで楽しんでいるのを見て楽しんでいました。

銅・銀あたりでは、HSEが冷えてて予想大外れだったのと、Carnegie Mellon U, École Normale Supérieure de Paris とか ICPCメダル界隈では珍しい学校が出てきて面白かった。DEK以外の9問は全部人間向けだと思ったが、実装がそこそこある問題が多く5時間で全て揃えられれば銀が取れる、という結果になっており、実装練習は大事...

さて、争点のSeoulの完数は9で、Asia Pacific Championを死守し日本勢最高順位にも並び、とりあえず本当の最低限はクリアできたかなと個人的には少し安心しました。

Gold Medalist
Regional Champion - Asia Pacific
The University of Tokyo

9 problems solved

Problem J - Splitstream
37 minutes

First to solve Problem G - Mosaic Browsing
85 minutes#icpcwfdhaka pic.twitter.com/bWdEkZFXby
— ICPCNews (@ICPCNews) 2022年11月10日

現場からの速報です pic.twitter.com/GJct9RewCu
— HIR180 (@HIR180) 2022年11月10日

MITはKも当然通しており、圧倒的すぎた。slime matthew jerry orz

ただ11完して並び立つことは当然出来るチームだったと思うので、圧勝させてしまったことに少し後悔はあります。

閉会式はWorld Championが表彰されるとすんなり終わり、また夕食の会場に戻っていきましたが、気分が落ち込んでいてあまり交流のモチベが湧かず、割とすぐホテルに帰りました。(狭義WFはこれで終了です)

ホテルに帰った後は、スーツケースに全てを押し込み、ゆっくり寝ました。

Day6 (11/11)

ホテルでの最後の食事に行き、荷造りし、チェックアウト。

その直後に9年前に知り合ったバングラデシュの友人と直接会う機会があり、貴重な経験が出来ました (バングラデシュのお土産をたくさん頂きました) (日本にも来て欲しいね)

WFの思い出なんですが、9年前にcodeforces上のメッセージで話が弾んで友人になったバングラデシュの人が、自分のことを覚えていてくれて、都合が合い現地で初めて会うことが出来ました (嬉しいね)

自分と年度が違ったから気づかなかったけど、IOIのバングラデシュ代表になってたらしく、びっくりです pic.twitter.com/zoTTT0oDX8
— HIR180 (@HIR180) 2022年11月15日

その後はチーム+コーチ 4人でバスの時間までの時間潰しとして、周囲を散策しました↓

各フロアに小さい店舗が密集してる感じで、基本衣類とか電子機器とかが売られていますが、宝石とか金のアクセサリー？的な店ばっかりのフロアがあり海外を感じました↓

この後夕方に空港へバスで移動し、飛行機まで約6時間ほど暇を持て余していたので、henoさんに現地通貨を頂いてスーツケースを縛るテープを買ったり、売店を散策したり、夕飯を食べたりしました。

コンテストまでは集中したかった&コロナのこともあり、またコンテスト直後は落胆していたので、この時間に初めてまともに海外チームと交流できた気がします。

23:55の便でシンガポールへ。

Day7 (11/12)

シンガポールへの便であまり寝られなかったので、空港のソファーで大爆睡し、トランジット8時間を消し飛ばしました。その後お土産を買って、日本への便の中ではあまり眠くなかったが、なんとか寝て暇を潰し、ついに帰国。

飛行機自体の遅延 + 荷物回収に時間がかかり、終電バトルが開幕して慌ただしく解散。

羽田からだったので自分は割とすぐ家に着き、WFは完全に終わりました。

まとめ

最後に、今回参加して感じた、ICPC WFでのtipsを (来年の自分のためにも) まとめておきます:

寒さ: 特に1年中暑い国では、逆に室内はクソ寒いことが多く、体が冷えると当然指先がかじかんでタイピングに支障をきたします。そこで、防寒対策が必要なのですが、コンテスト当日は支給されたTシャツを外側に身に着けることを強制されるので、薄手の長袖の服を用意するのが良いです。
声かけ: 本番、特に最終盤はテンパりすぎていつも出来ることが出来なくなります。REが取れないならassertを全部消したか？とか幾何でハマっているならepsを変えたか？とか (今回のDはepsを1e-9から1e-10にしたらACしたと後から聞きました) 、そういう典型的な声かけ集をチーム練の時からまとめて、直前に確認するとかしておけば、と個人的に思いました。
ライブラリ写経: 上記の通り、シールを探す旅に出て、見つかれば、勝ちます。(かなりしょうもない話だと思うんですが、こういう工夫がメンタル面でプラスに働き、実際に写経も捗ったので、やらない手はないです)
荷物: 鞄やスーツケースの容量をかなり開けておかないと、大量に配られる各種お土産が入らない (いくつか向こうに置いてきました) だけでなく、表彰式で大量に重くかさばるプレートを貰ったり、ICPC challengeでPCを貰ったり、それこそWorld Championのトロフィーを貰ったりした時にとても困ることになるので、コンテストとは無関係ですが、注意しましょう。
その他: ある程度交流を楽しみたいなら英語をやっておくべき。 (自戒) あとどこの大学にどんな人がいるかを下調べしておくと観察が捗るので、おすすめです。

次回のエジプトのWFには再び UT a.k.a Isで臨みますが、その時には自分は研修医になっている (なっていてくれ) し、他2人も本業のウェイトが増していくと思うので、どの程度練習が積めるか不明ですが、悔いなく終われるようにはしたいなと思っています。また、次回はコンテストだけでなく、年に一度のお祭りということで、楽しむ気持ちも持ち合わせて行くつもりです。

とりあえず初手として、向こうで師匠とhenoさんにCFに復帰すると宣言したので、無理なく出られるdiv1には参加していくつもりです。

本当の最後に、今回のチームは間違いなく世界一になれるポテンシャルがあったと信じていて、結果としては届きませんでしたが、一番アツいポジションでWorld Championという大きな夢を見せてくれたチームメイト2人に感謝してもしきれないです。

また、2020年秋ごろから2年間、___ KING ___を応援して頂いた皆様、ありがとうございました。

2021-11-06

ICPC 国内予選 2021 参加記

チーム UT a.k.a Is (yutaka1999, yokozuna57, HIR180) で参加して、優勝しました。

f:id:Hiro180:20211106145401p:plain

ICPCは完全に引退したつもりでいましたがWF2020の特例措置で生き返ったので、個人としては5回目 (正真正銘のラスト) 、チームとしては3回目 (2018, 2019, 2021) の出場となりました。

大まかな戦術としては、今年は他チームが強いことが分かっていたので、去年みたいにエンタメ要素はなしで普通に前からやることにしました。

当日

6:30に起床 (え？) 、大学行ってから家に戻り、昼食&昼寝した。

直前まで打ち合わせしてなかったのでD以降の割り振りはad hocに決めることとし、コンテスト開始。

A-yokozuna, B-HIR, C-yutakaで始めたが、Cにこの世の終わりみたいな図が書いてあるのを見てB, Cをswap。

Cは解法自体はぱっと出るが、全方位木DPに苦手意識がありCでこんな問題出るか？？と疑念を抱いて少し考え直す。が冷静にそこまで大変じゃないので黙って実装することにする。

通常の木DPまで書いた段階で2乗解を回し始めたが全然終わらず、結局全方位書いて通した。かなり手間取ったけどペナ吐かなくて良かった。

この時点でもうABDが終わっていて、Eももう師匠が実装に入っているとのことだったので、yokozunaに合流してFを考える。

その後すぐyokozunaが解法を思いつき、僕が実装した。かなり手間取り、また強連結にするパートで少し怪しい部分があったが、国内だし実行出来れば正義！wって言ってassertてんこ盛りにしてゴリ押し実装したら無事一発で通った。OK。

その後はHを見て、反転してn=4の場合が解ければ解けるね～という話をしたが当然間に合わないので諦め、Gと格闘してる師匠を応援してコンテスト終了。

感想

G,Hを振り返ると7完するのは相当調子良くないと無理そうでしたが、結局6完速度勝負で勝てたので良かったと思います。4年弱前の結成時からチーム性能の圧倒的な向上を感じました。

個人としてはC, Fどちらも実装でかなりタイムロスしたので、実装練習しないとダメだなと思いますが、とりあえず去年のDみたいに炎上はしなかったのでよしとします。

横浜は勿論優勝してWFの権利を勝ち取るのもそうですが、久々にオンサイトでコンテストやりたい気持ちが強いのでなんとか現地開催されるよう祈っています。

ここまで読んでいただきありがとうございました。

2021-03-18

ICPC アジア地区予選横浜大会 2020 参加記

チーム___ KING ___ (yutaka1999, maroonrk, HIR180) で参加して、国内予選に続き優勝しました。

f:id:Hiro180:20210318152343p:plain — 順位表

国内予選の時はmaroonを幾何だけに充てることになりましたが、アジア地区では普通に3並列でバリバリ解いていくことにしました。

1ヶ月くらい前からcodeforcesのgymなどで練習を数回やりました。

模擬地区は特に問題なく2.5時間で全完できたので良かったですが、本番は激ムズ (ex. 去年のセット) だと思っていたので、当日は結構冷や冷やしていました。

本番

A: HIR, B: maroon, C以降読み: yutaka で始めました。

Aは少し手間取ったと思いましたが、FAが取れて良かったです。

Bもすぐ通り、E: maroon、G: HIR、H: yutaka で30分過ぎに5完まで行きました。

その後、師匠がJK、僕がIを通し、それぞれD, Cに着手しだしたころに、

maroonが自信満々な感じでFに3乗解を投げると言ったので、皆でjudgeを眺め、かなり時間が掛かったものの通ったので、してやったりという感じで盛り上がりました。

この後は、僕は右手法を勘違いしていてmaroonに助けを求めたり、バグったりしましたが何とかCを通し、師匠とmaroonのD速度バトルを応援していました。

バトルはmaroonの勝利ということで、3時間過ぎでコンテストが終わりました。

f:id:Hiro180:20210318154546p:plain — domjudgeのアカウントを無効化されるというレアイベントが発生しました

終わった後は恒例の反省会をし、それでも暇だったんですが、雑談したり、寝たりして時間を潰しました。

表彰式は他の上位チームの人々の話を生の声で聞けて面白かったです。

懇親はあまり渾身ではなかった (このネタ何回目？) ですが、gather townのシステムは面白くてすげ～ってなってました。

感想

実は競技プログラミングで金メダルを貰うのが初めてなので密かに喜んでいます。

あと全体FAも狙っていたので何とか取れて嬉しかったです。基本的には序盤力を発揮するのが大事な仕事だと思っているので、今後も宇宙人たちをサポートする人間枠として頑張っていきます。

ICPCは (いつやるか未定ですが) World Final 2020, 2021を残してもう参加することは出来なくなってしまいましたが、今後は何らかの形でお手伝いが出来たら良いな、と思っています。

最後に、今回は大変な社会情勢の中新しい形式の大会を準備されるということで、多くの障壁があったと思いますが、このような素晴らしい機会を提供頂き本当に感謝しています。

個人的に、ICPCは大学以降競技プログラミングを続ける一番大きなモチベーションとなっていたので、現役生活の最後にWorld Finalで好成績を残すことを通じて、多くの方に競技プログラミングの魅力、楽しさをお伝え出来たら良いな、と思っています。

今後も他のことと平行しつつ頑張っていきますので、是非World Finalに出場する際には応援よろしくお願いします。

2020-11-07

ICPC 国内予選 2020 参加記

チーム___ KING ___ (yutaka1999, maroonrk, HIR180) で参加して、優勝しました。

f:id:Hiro180:20201107003558p:plain — 全完! (3年ぶり2回目)

メンバー紹介 (国内予選2020ver)

yutaka... メインコーダー。基本的に何でもできる。

maroon... 何でもできるが、現状唯一の幾何担当なので、後ろに露骨に時間がかかりそうな問題 (主に幾何) があった場合、まずそれを倒す。

HIR... 他2人を補う形で、主に面倒な問題を担当する。

やっぱり全完を目指したいという共通の意思があったのでこのような分割になり、

実際に模擬国内でmaroon幾何ワンポイントがハマって全完できたので本番もこの形になりました。

(僕はと言うとサイコロで炎上してチームメイトを冷や冷やさせていました -19980412点)

本番

皆自宅から参加。

最初見てHIR: A, yutaka: B, maroon:Hからスタートする。

次に僕がCを解き、

Dが構文解析の見た目をしているので、師匠のEと交換して取り組む。

Dの中身は普通の問題だったが、計算量見積もりが甘すぎて実行に無限時間掛かるコードになってしまったので、とりあえず合っていると信じて既にEFを終えた師匠とGを考える。

Dを何とか通し、程なくGの方針が立ち、2人でフローのグラフ作りと、辞書順最大のための微調整を分担することにする。

割と時間がかかってしまったが、コンパイルが通った後はすんなりACできてほっとする。

最後に、maroonがひたすらHと格闘しているのを応援してたが、残り8分辺りで突然1個目のケースが通った、と言ったのでかなり盛り上がる。

それから間もなくして、全部の問題が緑に光って勝利を確信。やったぜ。

f:id:Hiro180:20201107005310p:plain — これすき

最後に一通り問題を振り返って、国内予選は終わりました。

感想

個人的なパフォーマンスは良くなかった (HELP!!) のでチームメイトにひたすら感謝です...。

来年3月の横浜までにまたコンディション作って頑張りたい。予定では6月にUT a.k.a Isで臨むWFもあるしね。

ここまで読んで頂き、ありがとうございました。

追記

進級が掛かったCBTが2週間後に迫ってるので熱烈QB精進しないとヤバくて困っています誰か助けてください

2020-09-15

TopCoder Algorithm Target になりました

この前のTCO 2020 Round4のレート更新でTopCoder Algorithm Targetになりました

f:id:Hiro180:20200915202949p:plain — このマークが自分の名前の左にある事への違和感が凄い...

f:id:Hiro180:20200915195824p:plain — 灰からTargetになるのは結構珍しい気がする？

f:id:Hiro180:20200915200121j:plain — ランキング17位 (TCO2020 R4直後)

2012年9月に競技プログラミングを始めたときから最終的に到達できたらいいな、くらいの気持ちでTargetになりたいという思いを持っていましたが、本当に達成できるとは思いませんでした。

僕が競技プログラミングに触れ始めたころはCFは頻繁に遅延 & 鯖落ちする黎明期のサイトで、(直近のラウンドが#670ですが、僕が初参加したのは#139) AtCoderにはそもそもレーティング制度がなく、SRM一強の時代でした。 (今では考えられないですね....)

当時は (JOIも目標にしていましたが、) SRMで赤くなることを目指して頑張っていました。2014年6月に最初に赤くなって、このまま順調に上がっていくかな？と夢を見ていましたが、実際は受験勉強のブランク等々で滅茶苦茶なことになっています (↑のグラフ参照.)

大学に入って、夏まではバイトや部活を頑張っていましたが、もう一度競プロに打ち込みたいと思って秋からはかなり集中して精進する日々を過ごしました (↑のグラフを見ても2017-18の上り幅が凄い)
最近ではICPC WFが延期になってしまい、また上位との壁を感じることが多く、大学も忙しくなってきてしまったので昔ほど時間を取れなくなりましたが、その中でなんとか這い上がって目標を達成できたのはとても幸福なことでした。

スピード + 確実性の比重が重いSRMが比較的得意と自己評価していますが、実際最近はある程度自信を持って出したものはほぼ通っていたので、(R4の既出も含め) かなり上ブレしてる感じです。今後は落ちることも当然あると思いますが、落ちても戻ってこられるようにもう少し地力を上げていきたいです。(あと1年？くらいロスタイムがあるので、まだ伸びると信じています)

最後に、後日オンラインでTCO Finalに参加するので、出ただけで終わらないように、見せ場が作れるようになんとか食らいついていきたいです。