かっつのメモ帳

主に競プロ　時々日記

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

Give us sociability (Kattu, Hyado, hotman) で組んで、出場しました。

最終結果は6完7位でした。

f:id:KKT89:20220317203107p:plain

ICPC前

昨年のICPC国内予選が終わってから、チームメンバーそれぞれ大学等で忙しく、殆どチーム練習の時間は取れずに、僕自身も2月まで割と競プロから離れていた。

久々にチーム戦やりたいな〜とぼんやり話していたら、チームdiscordでチーム練の予定が次々と立って、5時間バチャを走ったという記述が(正確に数えてないけど)日記に7回程あったので、チームとしての練習は多分それぐらい。

定期的に並走してくれる方々がいらっしゃって、とても有り難かったです。この場を借りて、お礼申し上げます。

チーム練のupsolveに苦戦していたら、あっという間にICPCの時期に。

模擬地区予選

kkt89.hatenablog.com

模擬地区の辺りから、トップ10を目指したいね〜という話と、同じ早稲田のライバルチームであるMSBに勝ちたいね〜という話はチームメイトとしていた。

ICPC1日目(前日)

学生証の確認とリハーサルコンテスト、注意事項の確認等が行われた。

特に何事もなく終わり、前日も3人で大学に集まっていたので、諸々の動作確認と、翌日の持ち物の確認をして解散。

これは？

？？？

ICPC2日目(本番)

9時コンテスト開始、早すぎる…。

チーム名に反して(？)、8時半過ぎには全員大学に揃っていたので、軽く朝ご飯を食べながら談笑して過ごしていた。

どうやらシステムトラブルがあったようで、開始が遅れていた。

結局10分遅れとなり、9:10コンテスト開始。

コンテスト

AB難易度順、以降難易度シャッフルとのことだったので、僕がA、HyadoがB、後ろをhotmanが読むという分担で、スタート。

A初見、流石にビビる。

が、流石におかしいとpdfを隅々まで見ると、それっぽい数式があって安堵。

A問題 AC(0:08)

出遅れた感があったが、英語読解スピードの差だなと思い、気を取り直して次へ。


B問題を読んだHyadoが面倒な設定と言っている。順位表を見ると、強めのチームが早々にペナを出しているので不穏な匂いを感じ取る。

概要理解して、何となくの方針が浮かんだので実装をするも、WA。

自信あったのでかなり焦ってしまった。Hyadoと自分の解法を伝え議論をするが、どうも話が噛み合わず、そこで3等が2つだと勘違いしていたことが発覚した(正しくは3つ)。

自分の解法は、4桁の当選番号と2桁の当選番号を2つ全探索するものだったのだが、ここから少し手を加えると O(1) で正しい解法になることが分かったので、修正し、AC。

B問題 AC(0:41) +1

思ったより時間が経っていることに焦ったが、順位表を見ると予想以上に動きが鈍く驚いてしまった。

序盤良くなかったものの、まだ巻き返せるコンテストだなと思い、次に切り替えた。MSBがノーペナでABを爆速で解いていて、思わずやるな〜〜〜って言っていた。

f:id:KKT89:20220317232110p:plain

当日、順位表観戦してた大学の友人に送って貰った。大会終了後だと、こういうスクショは意外と貴重。


僕が2問解いている間に、Hyadoは色々な問題の翻訳をdiscordで共有してくれていた。恥ずかしい話、僕とhotmanが英語読解に苦手意識を抱えているので、弊チームはこういう立ち回りになることが多い。

序盤からACが多く出るセットだと、序盤の速度不足になるのでHyadoにもっと実装に回って欲しいと感じることは少なくないが、今大会のようにACが全然出ていない場合、こちらとしては望み通りの展開か。

hotmanは最序盤にJを読んで考えていて、初め二次元セグ木で出来るかも？と言っていたが、上手く単調性を生かせるかもしれない、と考察を残して、次にFを考えていた。

データ構造要らないならばと、次に僕がJ問題を担当することにした。


ここから暫くは中々3問目のACが出ずに、苦しい時間が続いた。

J問題、解法自体は容易い二分探索で実装可能なのだが、十字路の形にならず、長方形領域になる場合(xまたはy座標について順序関係が逆転している場合)の処理が面倒だね、ということを話していた。

取り敢えずサンプルが一致し、提出してみるもののWA。

ここですぐ愚直解と付き合わせるジャッジを書いた判断は偉かった。とはいえ、そのジャッジをバグらせたり、上記の長方形領域の場合について重複して数えていたりを修復するのに、かなりの時間がかかってしまっていた。


流石に焦りが隠せず順位表をチラチラ見ていたのだが、その時点でACが出ているのがG問題とJ問題だけみたいな時間が長く、こんなこともあるんだなぁと思っていた。

そんな中、suzukaze_Aobayama チームがD問題のFAを取って上位に浮上しており、流石にひっくり返ってしまった。続いてG問題もACして、一時は5完の2位になっているのを確認して、いやすげ〜〜と、繰り返し言ってた記憶が強い。

個人的にメンバーの方と親交があり、意識しているチームの1つではあったのだが、去年の国内予選といい、しっかり本番でチームの力を発揮し結果を残せるの、強くて良いチームだし、素直にカッコいいなと感じた。


かなり時間がかかったものの、J問題の愚直チェッカーと答えが一致したので、提出するもWA。流石に声出して焦り始める。マジで分からんな…とホーム画面を眺めていると、J問題のclarに超本質情報が書かれていて、流石にまた声を出してしまった。

結局長方形領域になる場合は考えないらしい。長方形領域の考慮で、愚直解をバグらせていたり、重複して数えているのを修正していたりしていた時間は本当に何？？？となるが、概ねのコードが流用できるので、急いで書き直し始めた。

本番では(問題文まともに読んでないので、他で正確な記述あったらすいません)、

the ordered pair <p, q> is said to cover a point (x, y) if xp ≤ x ≤ xq, yp ≤ y ≤ yq, or both hold.

この文章だけ拾って読んで、問題読解多分合ってるんじゃないかなと判断したので、険しい。問題文中に文章で埋め込むだけじゃなくて、1つ数式で正確な条件を与えてくれるだけで違うんだけどなぁ…という小さい独り言。


この後ろで、HyadoがhotmanにD問題の相談をしていて、cartesian tree を用いて解けるのでは？という話になっていた。それを聞いたHyadoがDの実装を終えて提出していた。

解法どころか問題内容すら知らなかったので、どうなんだろうと疑いの目で見ていたが、ACが出て驚いた。ずっと2完で重い空気が流れていたので、これは本当に良かった。

D問題 AC(2:23)


誤読が解けたJ問題も遂に愚直とコードが合ったので、祈る気持ちで提出する。

しかし、またもWA。人生終了。

こんなんオーバーフローぐらいのミスしか見当付かないけど、全部対策したしなぁ…と絶望しながらソースコードを読み返していると、

int solve(){}

という関数を書いていて、この問題で何度目だろうか。また声を出してしまった。

(言い訳を書くと、全部対策した記憶は間違ってなくて、誤読発覚後に色々書き換えてコピペした際に、ここの型だけ元に戻ってしまっていた。)

チームメイトに謝罪の言葉を陳列しながら、提出。ようやくACが出て、救われた。

J問題 AC(2:38) +3


丁度その頃G問題を担当していたhotmanも、ペナを重ねる度にミスを見つけて、声を出しながら修正していた。僕は全くこの問題に関われてないので、無事通してくれることを祈るような気持ちで見ていたら、何とかACしてくれて最高。

G問題 AC(2:47) +3

この時の順位表(これも送って貰った)。体感冷えてるのに6位で、且つ、上位との問題差もC問題しかないというのは不思議だった。

f:id:KKT89:20220318023408p:plain


流石にこの順位表では3人でC問題に行かざるを得ない。各々問題を読み、サンプルを手で動かしている段階で、僕が N^{2} 頂点のBFSすれば良いだけじゃない？と思いついて、hotmanに話すと同意を得られたので、すぐ実装に入った。

そのタイミングで序盤から目をつけていたF問題にhotmanを担当させ、2並列で+2完を狙う作戦に入った。


CのBFS解法というのは、前から i 文字、後ろから j 文字揃っているという状態を考えると、その文字列の末尾に a _ {k} l _ {k} を加える遷移が正しいかどうか容易に判定できて、この遷移関係をグラフにするとDAGになるので、求める文字列の最小長さを得るにはDAG上の最短経路問題になり、これは簡単。

加えて本番では気付かなかったが、00,01,02…,98,99 といった順で遷移を見ていき、初めて訪れた時のみに遷移することを繰り返せば、辞書順最小も同時に満たすことが出来る(はず)。ここまで来れば、後は易しい。

僕は辞書順最小の処理が分からずに、愚直に文字列を持ってDPしてしまったので、計算量が怪しいコードになってしまった上、その分枝狩りや前計算を色々頑張ったので実装時間も結構かかってしまった。

最悪ケースに自信無かった僕「多分TLEになるけど出します」

多分TLEになるなら出すなよ、というチームメイトの至極真っ当な反対を押し切って出したらACして、流石に脳汁ドバドバのガッツポーズ。

C問題 AC(4:00)

言い争いの時間が無ければ、凍結前に俺のAC反映されたのにな〜とはふと思ったけれど、Yes/No体験出来ると思うとそれはそれでイイな、と思い直した。


残り1時間。hotmanのF問題を応援しつつ、Hyadoと解ける問題を探しに行った。上位を見ると、I問題が1チーム、K問題が2チームなので、K行くかぁと考え始めた。

そもそも必ず構築可能なのか？ということが気になって、 n = 2 の場合で愚直ケースを回して眺めたりしていた。どうやら作れていそうだなということは分かったものの、構築方法の糸口は掴めず。

貪欲的なアプローチを考えていたものの、これも分からず。

残り時間僅かになって、hotmanのFの解法に漏れがあったことが分かり、ここで終了。

コンテスト終了後

凍結前9位。ほぼ凍結同時にC問題が通っているので、下からは完数差付けられない限り抜かされないだろうと話しており、上の2~3チームのYes/Noが気になるね〜という感じで結果発表を待っていた。


その前に問題解説。

担当した問題(ABCJ)に関してはOKという感じだった。D問題は非想定だったぽい？

F問題の解説を聴いたhotmanがとても悔しがっていた。

F問題に限らない話だが、ジャッジ側の難易度想定と実際の結果の相違を見るのはとても興味深かった。参加者の集団によって解かれ方が変化して、その順位表によりチームの戦略が変わってくるというのは、ICPCの面白いところだよなぁと改めて実感した。


F問題解説「惜しいところまで行ったチームはあったようでしたが、最終的なACは0チームでした。」

僕「おい！！！！！まだ僕達のYes/No終わってないぞ！！！！！！！！」

ネタバレには気を付けよう。

順位表凍結前に提出されたコードは、僕が誤ってJ問題をF問題に出した1件だけな筈なので、仮に凍結前の話だとしても惜しい訳ないだろwとチームで爆笑していた。


I問題、具体的な実装はまだ出来ていないが、解説の言わんとする主張は分かって、なるほどな〜となっていた。僕はチームでグラフ問題を担当することが多いので、こういう問題を通せるようになれればな、というのは感じた。

K問題、解説を聴いて感動。とにかく賢いな、と放送を聴きながら言っていた。上のI問題も解けるようになれたらな、という話をしたが、K問題のような問題は、通せるようになれたら楽しいだろうな、というのを感じていた。


遂にYes/Noの時間。参加者側として見るのは今回が初。

昨年3月、かっつくんとアジア予選のYes/Noをdiscordでしゃべりながら見ていました。来年は二人ともここに出られたらいいね～って話をしていたと思います。

ICPC2021アジア予選 参加記 - ツバサの備忘録

MSB、最終盤に提出が増えてるのを確認していて、正直厳しいか…と見ていたんだけど、ラスト5分で2問も通してくるのはビビった。流石に劇的。

6完もっと増えるかなと思っていたので、7位という順位には驚きがあった。


残りの時間は、7完勢の結果をドキドキしながら見ていた。

結局凍結前から変わらずmax7完で終了し、他のチームも苦しいセットだったのかなとは思いつつ、(ここから+1完を重ねてペナも小さくするのは、想像以上に大変なことだと思うが)まだまだ上を目指せるなという実感は得られた。

まずは大会前に掲げていた目標の2つ、トップ10と、大学内1位が達成できて、凄く満足のいく結果だった。

ただ今回の結果はかなり上振れだとは思っていて、来年更にパワーアップしてここに帰って来れるようにしたいね、と思っています。

懇親会

お爺ちゃんだから、Gather Town 使い方わからん。

オンライン懇親会に関して感想を長所と短所を感じたので書くと、

長所

  • 人物とチーム名/HNが対応してて、分かりやすい。
  • 人によっては顔出さなくて良い、というのは気楽かな。
  • 人の会話の盗み聞きが現実より容易い。

短所

  • 誰が発言してるのか、人が密集していると分からない。
  • 目線のような情報が無いので、こちらに興味を持っているか/話しかけても大丈夫か、みたいな判断が難しい。

みたいなのは感じた。現実でも話したことない人に話しかけるのは難しいんだけど、オンラインだとよりハードルが高くなるかなぁというのは、僕の感想。


mugenさんに誘われて、Gartic Phone を10人ちょっとで遊ばせて貰い、かなり楽しかったです。ありがとうございました。

後は中々話しかける勇気が出ず、人の集まっている場所の会話の盗み聞きをしていて、慶應の皆さんのお話や、Y.Y.さんのお話などで、こっそり楽しんでいました。

終了直前に、UT a.k.a Is のHIRさんとお話し出来る機会があって、貴重な体験で、とても刺激になって良かったです。

渾身の懇親会(？)になったかもしれない。本当にありがとうございました。

まとめ

ICPCの参加記書くぞ〜と意気込んで、当日の様子を必死に思い出しながら書いていたら、ダラダラと長くなって疲労感が凄いことに…。

まずは、チームメンバー、コーチ、大会運営の皆様に感謝です。

また、よく一緒に切磋琢磨してきた早稲田の競プロ勢や、5hを並走してくれた他のチームの皆さんにもありがとう、という気持ちです。


他の大学の事情をよく知らないのですが、早稲田の競プロの集まりは横にも縦にも交流が深いと思っていて、実際もう卒業されて何年か経ったような先輩方にも母校のICPCチームを応援するメッセージを頂いて、有り難かったです。

僕が競プロにのめり込むようになったきっかけが、それこそ大学1年生の時に、学内のICPC練習会に参加していたのが大きかったと思うので、これからもICPCの盛んな弊学にして行けたらな、と思います。

今回こそ上手くアジアまで来れて、良い結果を残すことが出来ましたが、他にも強いチームが学内にはいるので、まだまだ油断せず、気を引き締めて次の国内予選に備えないとなと思っています。今年も、対戦よろしくお願いします。


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