2023 ICPC Seoul Regionalの予選の参加後記と愚痴話
こんにちは。リユナと申します。
一昨年と昨年に続いて、今年も同じメンバーでICPCのソウルリージョナルを参加することに決定されて、１０月２６日土曜日の予選に参加しました。チーム名はなぜか今回からチーム名の長さと少しの規定が新しくできて、例の「MunSongSong Eggdrop」じゃなく「Gyerantak」(韓国語で「卵パカッ」という意味です。)で参加することになりました。ただ、運営上のミスが多くて、ちょっと愚痴話もしたくなります。
チーム結成の話とか、チーム員各々の特性とかは前のポストを参考してください！
では、始まります！
0. スコアボード
今年のスコアボードは二種類あります。その理由は後で説明いたします。
1.大会中のタイムライン
(0分)私が前の部分、songCが真ん中、mhyが後ろの部分を読みました。前にある問題が全部解決できなそうで、少し悩んでいました。それでも可能性がありそうなのはDだったので、Dの解き方を考え始めました。
(6分)songCがEが簡単だと言ってすぐに実装に入り、その後ACをもらいました。
(18分)続々SongCがHをACもらいました。
(33分)Fもやはりバックトラッキングでうまく実装すればそれほど難しくない問題だったので、すぐにACをもらいました。おそらくこの時点まではスコアボードで余裕に1位になっていたと思います。
…そして大惨事になりました。
(60分ごろから..?)mhyがCを取って解き始めました。ロリハやグラフ置換とダイクストラなど色々な方法を悩んでみて、問題理解を誤ったことに気づいて再び実装し、そのうちに例題がよく出てこなくて再び実装し、間違っているようでコードを出力した後に再び実装し、など数多くの試行錯誤の末にもACが出てくる気配は見えませんでした。私とSongCはmhyが止めたと判断し、他の問題からいっそ考えることを提案しました。
(91分)DのACをもらいました。最初は本当にbinary matrixを利用して変数2000個の連立1次方程式を解かなければならないのか、、と思いました。影響を及ぼす可能性のあるものが一つの変数に多くても二つだから式が思ったよりきれいに出るのではないかと思いましたが、これはヤバすぎだと思ってsongCと相談した結果、2-SATやもっと簡単にはUnion Findで管理しながらすぐに可能だという解釈を導き出して実装して当てました。
その後、mhyはC、私はK、songCはGに死活をかけて実装しましたが、皆実装が大きくできなくなり、とても進行が足踏みされました。私たちは本当にこの時点で、このままだと本大会の受賞と月波どころか、そもそも本大会進出も危ないと思い、大いに緊張して気をもんでいました。（結論的にこの時点で大会が終わっても本選進出は可能だったから杞憂だったんですけどねww）
やがてみんなが気が抜けた2時間半後の時点あたりから、私はなんとかKプールの構想を終え、SongCはGのデバッグがほとんど終わっていくようでした。それでも4ソロ大会を終えることはできなかったので、最後までベストを尽くしました。
(169分)奇跡的にsongCのGがACをもらいました。
(175分)なんと終了わずか5分を残して、私のKデバッグが終わって提出して、すぐACをもらいました。
その後、mhyはCをずっと見ていましたが、結局間違いは見つからず、大会は終わってしまいました。大会がほぼ終わる頃に、mhyが「いや、配列を20万までにしないといけないのに、10万だからといってREが出ないといけないんだけど？なんでWAが出るんだろう？最初から実装自体を間違えたのかな？」という発言が出て、これが後起こる事態の伏線となりました。
珍しくも今回の大会はフリーズがなかったので、結論的に当時スコアボード7位で、そのまま本選進出を決め、あっさりと大会を終えました。
2.大会のあとの話
まさに大事件が起きました。
翌日、突然チーム員たちとのチャットや他の韓国の競プロ界隈からCに対してACできたコードの反例が続出し、そもそもデータが間違っているようだという話などが聞き始まりました。どうせ私たちには間違った問題で気にせずいたんですが、あちこちでこの問題によるノイズがたびたびと聞こえました。
また、公式ページのお知らせ事項で「修正事項がありますので順位表を下げ、再採点を行います」って言って、問題にあったのはCに間違いないとみんな確信する雰囲気でした。
そのあと、Cの問題のデータは本当にエラーが確認されて、「既存CがACだったチームは正解認定、既存のCが間違ったチームによっては再採点でACが出たら正解を認定し、無条件で本選大会に進出、そしてそれにより既存よりもうちょっとチームの先発を行う。」というお知らせが公告されました。スコアボードも大会当時のスコアボードと(１番目のイメージ)再採点以後のスコアボード(２番目のイメージ)がすべて公開されました。
3.愚痴話
まあ、結論的に予選の順位は本当に関係ない話だし、本選大会の進出はどんなバージョンのスコアボードでも余裕にできるので私たちに直接できな障害はなかったんですが、やっぱりあまりにも残念でがっかりしているのが本気です。
私たちのCのコードはアルゴリズムは正しかったが、配列を宣言する長さが間違ったので、もしデータが正しかったらREが出なければならないコードでした。しかしWAが出ちゃって「これはそもそもアルゴリズム自体が間違ってるのか」と思わせてずっとデバッグしましたがバグを探せず結局間違ったままに残りました。もしかして間違ってたデータがなくて結果が「RE」で正しく出たなら、私たちのデバッグの方向性は配列の宣言の長さやindexなどに集中されて難なくデバッグができたかもしれません。
実際、私たちはCの正解の有無にはあまり影響を及ぼさないレベルのチームだったんですが、こんな理由でCを十分に解けるチームだったが解けなかったチームがないとは言えません。結果的に再採点以後ACをもらったチームたちは救済を受けましたが、こんな場合は結局証明もできず、証明してもそれはそれで問題だから処理が難しいことは看過できません。そもそもこんな事態になったことが非常に残念だと思います。
実はよく知られてないことなんですが、昨年のソウルRegionalの予選の問題にもデータにエラーがありました。Hの問題の入力ファイルの一つがおかしくなってて、C++で解けばあんま問題なく入力を受けることができますが、PythonでLineを入力されて処理すれば想定外に入力が多くてWAになる問題でした。大会であの問題が解けたチームが１チームしかないほどのかなり難しい問題だったのであんまり知られてなかったんですが、もし私が大会中にPythonで解いて提出して理由も知れずWAを受けたとしたら本当に腹が立ったでしょう。
どうか私は今年を最後にICPCに出場しませんが、競プロが好きな人として、その魅力に大きな傷となり得るようなこんな事態が本大会では絶対に、そしてこれからは二度と再発しないことを心から願っています。
なにとぞ、私も最後のICPC大会で悔いのないほど燃え尽きて、すべてをつぎ込んで見ます！できればPlayoffとWFまで！
4.問題たちの解き方
予選の問題はまだBOJを含めてどのOJサイトにもまだないんですが、多分近来にBOJに投稿されると思います。問題文はここで見られます。
A.
マジで実装だけの問題、大会中に解いたチームはちょっとだけありましたが私たちはこれを解く時間なんかなかったんです。
B.
与えられた順番ではなくその逆からBSTを構築しながら、いつも最後に追加された数がルートになることを利用すれば各々の実行で変化する辺は何個あるかは分かりやすいが、何となくちゃんとしたらO(NlogN)でできそうです、、、が実装できませんでした。大会中に解いたチームもいません。
C.
「あの」事態を起こした問題です。ロリハとDPをよく利用すればできると聞きました。
D.
Union-find、またはDFSで全部チェックすることができます。
E.
説明することもあんまりないです。ABCのBくらいのレベル。
F.
二つの点の間にある直線の数の奇遇性によって解けます。
G.
任意のMSTを一つ作って、あれに入れなかった線分たちにあれらを連結するMSTの経路の点数がちょうどあの線分の重さと一緒ならType2、じゃなければType3です。MSTの中の線分については似たようにしてType1とType2が比べます。
I.
今回に初めて出たInteractive問題。4分面について分けてよくしたらできるらしいですが、実はよく知りません。。。大会中に解いたチーム無し。
J.
二つの輪がどんな線分を基準として別れるのかをよく判別して、条件に注意しながら二分探索だと聞きました。
K.
めっちゃ変な機械装置と変な言語で整列を実装したらいいんです。頭が壊れそうだったんですが、私の方法は「空いたマスたちはいつも引接しているので、どこかで青い玉を拾って空いたマスの一番右に動かして、それでできた空いたマス1つには反対から見える球をすぐ拾ってあのマスへ入る」のような感じでしたらいいんです。問題の内容が分かったら多分理解できると思います。
整列されたかどうかを判別することは、空欄から初めて「青い玉なら進め」の命令と「白い玉なら進め」の命令の後に空欄の上にあるのかどうかで判別できます。
読んでいただき誠にありがとうございます！この記事は前に韓国語のブログに書いた2024 ICPC Korea regional 인터넷 예선 후기を適当に翻訳して投稿しました。もし韓国語ができたらあっちも見てくださったら嬉しいと思います。😉
