Shirotsume の日記

嘘Greedyを生やすな

ICPC 2024 Asia Yokohama Regional 参加記

2024年12月22日~23日に開催されたICPC 2024 Asia Yokohama Regionalに神戸大学からShirotsume+fky_+tmb=Uriboysで参加しました。

事前情報

チーム名について

神戸大学のマスコットとして神大うりぼー*1がいるので、それにちなんでUriboが名前に入っています。そして、年初にあった某炎上サークルにあやかって（？）boysをsuffixに付けることに。かなり攻めた命名で、最初はそのままBadboys *2 にしようぜと言ったのですがさすがにチームメイトから反対されこの名前に（正解でしたね）

チームメンバー

Shirotsume

Highest: A 2051 H 1621

すみません　去年よりレートが下がっています　典型が得意　ARC Div2で太陽を生やすなど活動は多岐にわたる

fky_

Highest: A 1625 H 2368

実装&構築が強い。US配列をよく利用しているので、ICPC本番でもほとんどつっかからずにコードを書いていてすごいと思った。

tmb

Highest: A 1789 H 1762

期待の超新星 AHともに実力をめきめきと上げている　考察も強いので、アドホック系は考察をガンガン投げてもらうようにしていた

練習について

大学コンに参加したり、ABC後に感想会をやったりしました。ICPCに向けたというよりかは、競プロ全体の力を上げるという方向で今年はやってみました。これは全員集まって練習する時間を取るのが難しかったためなので、集まれるなら集まったほうが良いと思います。また、JAG夏合宿にチームで参加しました。コンテスト経験だけでなく、他大学の方々との交流によって全員のモチベ&実力向上に大変寄与したと思っています。JAGのみなさまありがとうございました。

TTPCなどチーム戦の各種コンテストにもいくつか参加しましたが、これはICPCルールに厳密に則るわけではなかったので、ICPCに向けた練習と言えば微妙かもしれません。

ライブラリについて

ライブラリを整備しました。といっても自力で作ったわけではなく、noimiさんが公開されていたSpeed Starのライブラリに使用例や簡単な説明をつけ、ダイクストラやDSUなどいくつか必要と思えるコードを追加したものを持ち込みました。もともとは全部自前で用意する予定でしたが、工数的に無理だったのでありがたく拝借しました。

リポジトリを貼っておきます。最後スペースが余ったので バグった原因集 - Motsu_xe 競プロのhogeやfuga を引用したり好きなシャドバカード発表ドラゴンを召喚したりしました *3（ICPC舐めてる？）これらも含めると30ページになりました（正味29ページ） github.com

ライブラリKPT

やってよかったこと:

  • 使い方説明を付けたこと。これをやる過程で自然に全コードを読んで使うことになるので、特に他人の物を拝借した場合は必須だと思いました。横浜はページ制限ないので付けて損しないし。

  • 写経検証用ハッシュを使えたこと。実際にコンテスト中にも検証して有効だったのでよかった。せっかく用意してくださった機能は使うべき。

問題だったこと:

  • 必要なライブラリの洗い出しが不十分だった？ とくに強いチームのライブラリを窃盗してくる場合、彼らには不要だが自分たちには必要なアルゴリズムがいくつかあります。例えば、ダイクストラはシンプルだが適当に書くと計算量が悪化する罠がいくつかあるので、よほど自信があるという場合でなければライブラリを置いておくべきでしょう。横浜にはページ制限ないし。

今後やってみたいこと:

  • ハッシュで写経検証できるのはよいが、全体があっているかしかわからないのが問題。例えば行ごとにハッシュを書いておけば、間違えた時に行で手動二分探索することで誤っている行を高速に発見できます。私たちのチームは前日にこれに気づいて、絶対に写経するであろうテンプレートに対しては適当な区切りごとにハッシュを手書きで付け加えました。実際にコンテスト中にこれが役立ったので、可能なら行ごとのハッシュを用意しておくべきだと思いました。

コンテスト時系列

ここからは時系列順にコンテストまでの流れを振り返ります。解いた問題についてかなりちゃんと書こうと思っているので、ネタバレ注意です。

Day -1 (12/19)

実はこの日から関東にいました。新宿マルイメンでやってたレイジングループ *4 のポップアップストアに行きました。 謎解きイベントがあったのですが荷物が多いし、横でめちゃくちゃライブやってて音が大きかったので謎解きはやらず、グッズをいくつか購入しました。

買ったもの: 回末李花子*5ぬいぐるみ、泰長 *6フィナンシェ、ケムコアドベンチャーパック本編 *7

本編買った時店員さんにマジ？みたいな反応されたけど気のせいかな？気のせいだな　りかこぬいはICPC本番にも持っていきました。

Day 0 (12/20)

某があったのでそれに行きました。その後の飲み会に参加しましたが、アルコールは一切摂取しませんでした。夜11時30分くらいまで東京都にいて、そこから横浜のアパホテルまで移動して、着いたのが12時半くらいでした。飲み会などは楽しかったのですが、かなり疲れたからかBAD入っていて友達LINEグループに「電話しよ…」って言ったりしていました。*8

Day 1 (12/21)

アパ11時チェックアウトだと思ったら10時で焦る。ほかのメンバーは今日新幹線で来るのでそれまで待機。GIGO中華街に行ってチュウニズムをやり条件が緩和されていたメッちゅう殴打*9のアンロックチャレンジを解禁したり、レートを16に戻したりしていました。

tmbとfky_がついたので合流。一旦ホテルに荷物を預け、お昼は中華街の適当な中華屋に入り、餃子とか点心をいくつか頼んで分け合った。餃子が革命的においしかったです。

午後会場に行きチェックインをしました。ライブラリ印刷をお願いしていたtmbがイーブイのぬいぐるみを持っていたが、ライブラリを持っていなくて笑った。

リハーサルについては、問題を一通りガチで解いた後、一通りジャッジステータスを試したり印刷クエリを投げたりしていた。ShirotsumeだけPythonを使う可能性があったので、Pythonについても一通り通すまでの予行演習をしておいた。

自己紹介についてはほかのメンバーに喋る担当を押し付けられたので自分が話すことに。英語が崩壊していたが誰も気にせんやろ。

終了後はご飯。昼夜中華はどうなんだということで、適当な洋食屋？に入って、ステーキ載せピラフ(1780円）を食べました。実質中華でしたがめちゃうまかったです。

ホテルにチェックインしたあと、ABCに参加するまでの準備。Shirotsumeはずっと「ABC全完してから優雅に風呂入るわｗｗｗ」とか言っていたが実際はABC前真っ先に風呂に入る。熱い掌返し。また、コンセントが少なく争いが発生するかと思いきや全員のPC電源コードがめちゃくちゃ長いことが判明し事なきを得たり、fky_ & Shirotsume が思ったことをそのまま喋り続けるモードに入ったりとかなり騒がしいチームになった。

ABCは5完。終わっている。Fに固執してWAが出ていたが、GはFPS知ってればやるだけだったのでこっちに行くべき。判断が遅い。

tmb も5完だったので、じきに実力は抜かされるだろうなあという思いをさらに強めることになりました。

ABC終了後は素早く就寝。消灯後はイヤホンでオモコロウォッチを聞いたりしてました。

Day 2 (12/22)

Day 2 は7時に起床。Shirotsumeだけ早く起きて近くのコンビニにコーヒーを買いに行きました。

突然ラブライブの話になり、怒涛の μ's メドレーが始まる。

全員が準備完了後、朝はすき家に行くことに。去年も行ったので神戸大ICPCの伝統にしてほしいね。

牛丼（並）を完食後会場に向かいました。少しお腹が痛いのでトイレに行ってからチェックイン。

当初の予定から前倒しでコンテストがすぐにスタート。まず取り決め通り、fky がA問題を解くことに。当初の立ち回りルールでは、A, Bをfky_が解くことにしていた。ただし、どちらかにおいてShirotsumeがPythonで解いたほうが早いと判断した場合強権を発動して交代すると話していた。

Aはぱっと見で極大な区間を埋めていくしかなさそうで、計算量はなんでも許されるのでfky にお任せすることに。無事AC(0:20)。

Bについては、答えとpopcountを持ちながら1桁目を決めていくメモ化再帰が高速と判断。解法を説明するのが面倒かつたぶんPythonのlru_cacheが高速なので強権発動。ShirotsumeがPythonで実装し無事AC(0:36)。

しばらく色んな問題を読んであーでもないこーでもないと言っていたが、fky がEを簡単と主張。自分はまだあまり問題設定がわかっていないが任せることに。その間もずっとほかの問題を考えていた。fkyがすぐにEをAC(1:01)。

fkyがEを実装する間、Cから順番に問題を読んでいた。Cは全域木についての問題は超簡単か超難関のどちらかと思っているので、うちの実力なら一旦順位情報を待ってもよさそうと判断。tmbがHがワンチャンありそうというも、こちらも問題文の読解が難しく、一旦他を見ようと判断。

Iが典型の見た目をしていたのでこちらに移動。まず、選ぶ値の片方を固定した場合、gcdとしてありうるのはその値の約数に限られる。よって、gcdの値 gと、選ぶ値の片方xを固定したとき、もう一方の値は、gcd(x, y) = gを満たすyであってxから最も近いものになる。これは、Aの要素を試し割で約数列挙しながら、約数ごとのindexを持って走査すればペアを全部列挙できる。このあたりでセグ木の匂いがしたので、tmbに写経の構えをしてもらう。上記の考察より、問題は次の形に落ちる。

  • O(N \sqrt{max(A)}) 個の重み付き区間 (l, r, g) がある。各クエリについて、区間 (L, R) に含まれる区間の最大値を求めよ。

これは、クエリを L の降順にソートすると、セグ木の1点更新区間maxで解くことができる。これをC++で自力で実装するよりかは、解法を説明してtmbに書いてもらったほうが良いと判断し、解いてもらう。1ペナをもらうも、デバッグ出力やコード睨みつけなどのテクニックを駆使し、なんとかAC(2:20+1)。

tmbにIを書いてもらっている間、Cが解かれていることに気づき、再度考えてみる。主客転倒をすると、コストは各頂点について頂点1からの距離×重みとなり、これは各頂点に対して最短経路で辿った時の距離が下界となる。そして、最短経路木をとることで実際にこれが達成できるので、ダイクストラをやるだけで解ける。ダイクストラのライブラリを持ち込んでいたので自力で書いてもいいが、tmbがダイクストラをソラで書けると言っていて、罠については自分なら大丈夫だろう（慢心）ということで空で書いてもらうことに。解法をざっくり言ったがあまり納得いっていないようだったので、とりあえずダイクストラを書いてください。そして各頂点についてPと掛け算してください。ほらサンプル合うでしょう？とマジシャン的な言いくるめ術を行い提出。無事ACを得る(2:44)。

Kが可能枠に見えたので向かう。タイブレークがやばそうだが、各iについて最適なjを選ぶという方針になると、i, j が重複するケースは考えなくてよいことがわかる。よって、あらかじめbit集合ごとに最適な相手を前計算することでiごとの最適ペアがわかり、それらを比較できれば良いことになる。実行時間に不安があったのでC++でShirotsumeが実装。ゼータ変換は書きなれているので特に苦労することなくできたが、文字列の取得でセグフォを食らいひっくり返っていた。チームメイトに相談しつつ解決。無事ACを得る。(3:39)

一旦実装キューが空になる。ShirotsumeはDかLが行けると思っていたが、fkyがGの解法がわかったと主張。しかし、聞いてみるとかなり方法が際どく、なおかつインタラクティブを時間内に実装できる自信もお互いなかったのでDの考察に。しかし、Dのサンプルを手で試したりしても全く分からず、最後1時間何の成果も得られず終わってしまった。

今思えば、Dに執着しすぎだった。順位表情報からはD <<< G, Lだったが、実際の難易度としてはそうではなかったと思う。なので、Lをもう少し考えるか、ワンチャンに賭けてGの実装をやってもらうかすればよかった。

コンテスト終了後は部屋を移動しYesNoに。自分たちのチームは解凍なしだったので、少し寂しい気持ちになったが、全体の盛り上がりは楽しかった。

写真を撮ってから、懇親会に行きました。お話してくださった方々ありがとうございます。個人的に驚いたのが、後ろに気配を感じて振り返ったらchokudaiさんがいたことでした。ここが戦場なら死んでた。 *10

主に実力が少し～けっこう上の人々を中心に話しかけに行ったりしていました。*11ごはん全体的においしかったですが、エビは凍っていました。

他の2人は就活世代なので企業ブースに行っていたが、自分はあまり行かなかった（すみません）。

19時ごろ荷物をまとめて撤収。すぐに新横浜までバスで移動し、お土産を買って新幹線で帰った。帰りの新幹線でtmbとICPCのyoutube配信を見たりしていた。名古屋あたりで寝て、2人に新大阪に着いたときに起こされた。本当にその間の記憶がなくて、ワープしたかと思った。

日付が変わる前に無事帰宅。

感想

6完で全体26位という結果でした。残りの問題について、今の私たちの実力では時間内に通すのは厳しいというのが率直な感想でした。しかし、去年に比べると順位は上がっていますし、tmbやfky_もモチベが高まっている感じがするので、神戸大は来年もっと上まで行けるんじゃないかなという気がしています。

FORCIAさんのゆるふわコンでsquare1001さんに神戸大も出ろやと言われたのがきっかけで昨年からICPCのチームを組んだのですが、今思うと本当に組んでよかったなと思います。私は今年でラストですが、残り2人については来年以降も誰かメンバーを捕まえて出てくれたらなぁと思っています。

競技プログラミングに興味があるという本学の学生も何人かいて、話をしたり観測したりするので、あわよくば2チーム以上参加する未来もあるんじゃないかと期待しています。今後も引き続き頑張ってください。

社会人になって以降の競プロ生活については未知数ですが、元気とモチベが続く限りAtCoderには出続けようと思っています。また、行事としてのICPCにも強い魅力があると思っているので、できればJAGに入ってお手伝いをしたいと考えています。

コンテストのスタッフ、審判団の皆様。JAGの皆様。コーチを引き受けてくださったY先生 *12 や、予選や練習の場所を提供してくださった研究室の皆様、本当にありがとうございました！！

*1:かわいい。が現物は全く可愛くない上に怖いので注意。本学は夜になるとイノシシの親子のお散歩姿を見ることができます。https://www.kobe-u.ac.jp/ja/about/public-relations/uribo/

*2:学生の不適切な行為についてのお詫び | 国立大学法人 神戸大学 (Kobe University)

*3:リーシェナ: アミュレットが強くて好き バルバロス: 打点でかくて好き。エンハ使うか使わないかの択も深くなって好き。エレノア: 能力が好き。ウィッチで早投げしたくなるデザイン、良い エイラの祈祷: リメイク版を一生擦ってた。清浄の領域: こちらも回復するとバフする奴。

*4:「人狼」をモチーフにした和風ホラーアドベンチャー。姉妹作（実は姉側)のデスマッチラブコメ！とのセットパッケージがSwitchで最近出た

*5:「レイジングループ」のキャラクター。蜘蛛を守護獣とする回末家の長者。かわいい。

*6:「レイジングループ」のキャラクター。織部家の長男。頭が良くてやがる。

*7:大ヒット人狼アドベンチャー「レイジングループ」 その姉妹作である「デスマッチラブコメ！」が 1本になって登場!!

*8:結局風呂入ってるとかで電話できんかった

*9:STEAKA feat. 山田じぇみ子の楽曲。譜面定数はMASTER 14.1。このときはLIFEが150まで緩くなっていた

*10:AC, そのまさかだよ

*11:これは主観だし、話しかけなかったとしても実力下に見てるとかじゃ全然ないです。強い人には喋りに行きにくいので、目標として積極的にいこうってノリです

*12:Y.Y.さんではない。Shirotsume/fkyの指導教員。fkyは金曜締め切りの原稿提出を金曜の朝に投げつけていてやばかった