こんにちは。リユナと申します。
始める前に、私は韓国人の大学生で、今はKAIST（韓国科学技術院）で数学と電算学を専攻しています。翻訳機を使ってるのではありませんが、まだ日本語が完璧と言えるくらいではないので、ちょっとおかしい言葉とか文法的なミスが多いかもしれませんのでご了承ください.
0. ICPC Seoul Regionalとは？
全世界の大学生たちがそれぞれの競技プログラミング実力を誇る大会がICPCです。 World Finalという世界大会の予選格で、世界各地の地域別にregional contestがあり、例えば日本には横浜regional contestがあります。
もちろん韓国にもこのregional contestがあり、韓国のSeoul Regional Contestは当然韓国の首都であるソウルで開かれる大会…ではありません！実はソウルで行われません！ 高陽という、日本で言うと千葉くらいのポジションのソウルの衛星都市でおこなわれています。まあそれまでは理解できますが、その位置がなんと、
ソウルより北朝鮮にもっと近いのがやばいです🤣
まあそれで接近性も悪いし、チームのみんなが提出以後「これACできなかったら俺/私今から出て北行くよ！」とかジョークしたんですが、全員何かが間違ってしまって北朝鮮人になりました。
雑説はやめて、もう少し大会の説明をしますと、進め方はICPCスタイルで同じ大学の三人が一つのチームを組んでそれぞれのチームたちに与えられたパソコン一つで、与えられた問題に対する解決策を決められた時間内にできる限り多くプログラミングすることが目的の大会です。 これは韓国だけでなく日本の横浜regionalでもほぼ同じルールだと思います。 大会はオンラインで行われる予選と、（国境都市あたりに上がらなければならない）本選に分かれています。
1.チーム作り
私のチーム'MunSongSong Eggdrop'は去年から続いていたチームです。2022年にKAISTに競技プログラミングの上手い一年生が二人入って、休学を長くしてチームがなかった私は、彼らと一緒にチームを作ることにしました。チームメンバーの紹介をすると、
mhy908: MunSongSongのMunです。私たちのチーム名は名字が各々Mun, Song, Songだったので作られたチーム名です。高校生の時APIOで銀賞をもらい、KOI(韓国情報オリンピック)で銀賞2個をもらいました。複雑な問題の観察とか幾何学の問題に特に強いです。
SongC: MunSongSongのSongの一人です。韓国内で指折り数えられる競争プログラミング強者だと思います。 IOIで金賞1個、銀賞1個を受賞した華麗な経歴を持っています。全てに強いですが、特に変なデータ構造や誰もよく知らないアルゴリズムとかを全部しっています。
Eunha: MunSongSongのあと一人のSongです。私です。最年長者で紅一点でした。競プロの始まりは遅かったのでKOIで銅賞1個をもらったのが高校時代の全部ですが、大学大会への経験は比較的豊富です。本業は数学科なので数学的な問題に強いです。頭脳回転も悪くないので、解構築とか誠実の把握が必要な問題にも強いです。だが、全判的な競プロ能力は他の2人に比べては弱いです。
うまく組み合わせてチームワークが合えば、お互いの短所を補完できる良い組み合わせだと思ったし、実際に長い間同じチームで活動しながらだんだんチームワークが良くなりました。
2. 練習
普通に一週に一回を目指して練習しよう！とは言ったんですが、みんな忙しくてよくはできませんでした。主にBOJ(韓国のオンラインジャッジサイトです。)やcodeforcesで昔のICPCスタイルの大会の問題を時間を決めて本番の大会のように練習しました。
私たちのチームにはそれぞれの弱いところがたくさんあったので、改善のために次のように努力しました。
-皆が解はすぐに出てくるが、問題を組んでできない時にずっと掴んでいる場合が多い。
私も数学科であり、他の二人も高校時代まではOIをしてきたので、チーム大会への経験よりは自らが粘り強く問題を掘り下げていくスタイルにもっと慣れていました。ICPCでは、これがむしろチームメンバーのうち、他の人がキーボードを捕まえられないようにする毒になったため、誰かが長い間コンピュータをつかんでさまよっているなら、誰でもすぐにそれを中止させるルールを作りました。
あと、韓国語は普通に年上の人には親密度には関係なく敬語を使うのが普通ですが、水平的なコミュニケーションのために、皆がお互いにタメ口だけを使うことにしました。
-1問目でメンタルが壊れた始めると、すぐにスノーボールが転がっていく。
誰かがそんな悪循環に陥るとすぐコードをプリントして、キーボードから手を離せるようにしました。あと、私たちだけの規則を作ったんですが、プログラミングを始める前に、「何分かかるよ！」って宣言してその時間が過ぎたらすぐアウト！のようなチームの中の色々なルールを作って、かなり効果的でした。
こんなにチーム練習をしながら競プロ以外でも協力やチームワークなどについて色々と学ぶようになった気分でした。 これくらいなら後で履歴書に一行書いてもいいんじゃないかと思うくらいです(⁇)
3.予選
予選のスコアボードはこうです。私たちは４位をしました。序盤は凄まじく疾走しながら1位を続けていましたが、終盤で少しこじれて4位になりましたが、それでも満足的な成績で本選進出には何の問題もありませんでした。
4.本選
私たちの学校のある大田(デジョン)から高陽まで行くのが辛かったです。まずはソウルまでバスに乗って、まだここで電車に乗って、乗り換えて、そこでまだバスに乗ってまあ四時間くらいかかりました。KTXの駅も高陽には一つだけですが、実はその駅も大会場からはめっちゃ遠いし、ソウルを越えてそこまで上がるKTXの本数も1あまりなく、間に合いませんでした。
大会前日の問題セッティングのための例としては、去年の問題のうち簡単なものが3つ出てくるのが普通ですが、今回は珍しく去年1チームしか解けなかったCastle Designが出てきました。
当日の本選大会のタイムラインは大体こんな感じでした。
(0分)mhyが前の問題を、SongCが中の問題を、そして私が後ろを読みました。すぐ解けるのはまだ見えてきませんでしたが、Ｉはたぶん易い問題だし、Ｊは易くはないが私が専門と言えるスタイルの数学の問題のように見えました。
(7分)Iのファーストソルブが出ちゃいました。Iがかなり易いという結果がだし、SongCがIのプログラミングを始めました。
(23分)mhyはDの答えを出し、SongCがIを出して次々と正解になりました。あと、私はJを解いた！と思ってプログラミングしましたが、間違ってしまいました。
(37分)Jの初ソルブを奪われましたTT
mhyはあの時Cを出したが間違ってしまって、それから続いてく七転び八起きの始まりでした。
(45分)SongCがGを解きました。
(68分)SongCがHを解きました。
(その間)この時私のJ、mhyのCがそれぞれをいじめていました。 Jは一桁の場合、例外ケースをおかしくしたことに気づいて直しましたが、それでも間違って悔しかったです。 Cは考えれば考えるほど返礼ばかりたくさん出てくる不思議な問題でした。
(147分)SongCがFを解きました。あの時までは正にSongCのワンマンショーでしたね。
(その後)Bが考えよりは解けたので私とmhyがちょっと仕事を止めてBの問題の読み始めました。Bの問題はめっちゃやばいですが、Python-like pseudocodeだったのでPythonが母国語である私が解いて、具現にはセグ木が必要だったのでその部分だけはmhyに任せました。あと、キーボードが空いている間にJの検証コードを作りましたが、101、102のような中間に0が入った数字で問題が生じることを確認し、すぐにどこを直すか見つけました。 Jを直してBのコーディングを始めることにしました。
(176分)私がJを解きました。
(190分)私とmhyが一緒にBを解きました。この頃、スコアボードが閉じました。
(210分)SongCがKを提出して一度に当たりました。 おそらくファーストソルブだったと思います。 SongCは大会当時、パフォーマがすごかったです。
(240分頃)SongCはEはエイホ–コラシック法にすればいいと言い、これを始めました。 一方、mhyがコードをすべてやり直して新しく始めました。 私はLの解釈を出しましたが、プログラミングするにはもう遅い状態でした。
(280分頃)Eがエイホ–コラシック法に解けず、ハッシュをうまくやらなければならないことに気づき、時間不足に絶望しました。 mhyは完全にやり直したコードを提出しましたが、ついにCが正解でした！ ペナルティはたくさん貯まりましたが、それでも幸せでした。
(300分)大会が終了しました。
5.本選の後
大会が終わって他のチームに聞いてみたら、どうやらみんな何かこじれたようです。 上位チームにはJやCのような問題が足を引っ張るセットではないかと思います。 主催陣が「Cのような幾何問題でたくさん迷ったのですが、これから幾何をもっと出してはどうか」という衝撃的な発言をしてしまいました。
予想順位は昨年のように約7位でしたが、このように私たちの上に上がると思ったチームが予想とは裏腹に滑るところが多くて結局予選と同じ全体4位、校内2位で仕上げて銀賞を受賞しました！(あと賞金100万ウォンも！)
銀賞受賞は本当に嬉しいですし、キャリアハイというに値しますが、大会外では実は残念な部分もかなり多かったです。 全体優勝が同じ学校のチームであるPenguinsだったので、今回から適用されるルールによりますとRegional1位が出た学校は1位がWF直行、その他は校内1、2、3位がセミファイナルに行くというふうになったそうですよ。 それでPenguinsが1位になったので、私たちは学校2位にもかかわらずセミファイナルにさえ出る機会をもらえませんでした。 19年、22年に当時のルールだったらセミファイナル進出ができたので、なおさら残念でしたね。
いっそ希望がなかったらともかく、世界大会のチケットを目の前で逃した気分で、スコアボードの公開で台湾大学のstd_absチームがついにEを間違えて2位にとどまった瞬間、チームメンバー3人が絶叫しました。 世界大会進出のためには同じ学校の友達がいるチームが優勝できないことだけを祈らなければならないこの状況が本当にアイロニーでした。 どうか素晴らしいパフォーマンスで全体優勝を果たしたPenguinsチーム、心よりおめでとうございます！
とにかく一方では残念だったし、私とmhyの無冠行進を終わらせる絶好の機会は逃しましたが、それでも満足できる高い成果を得て嬉しいです！ 大会に参加した、そして運営に参加したすべての方々、本当にお疲れ様でした！
6.後は？
昨年のように「よっしゃー！このチームそのままだ！ 来年もよろしく！」という状況ではありません。 当初、私とすべてのチームメンバーは、私がこの大会を最後に引退すると思っていたので、それでMunSongSongで私の空いてる席に誰を入れるかをすでに決めておいた状態でした。 今になっては私が未練が残りすぎて卒業を延ばしてでももう一度参加しようかと悩んでいるところですが、一応既存チームを維持するのはかなり難しくなった状態です。
昨年は「来年成功できなくてもあまり落胆しないようにしています！」と書いたのですが、これが人の心が思い通りになればどんなに良いでしょうかww 実際にこんな状況になるととても未練が残ります。 むしろ最後をただ希望なしに終えたら未練もあまり残らないのに、目の前でチケットが飛んでいったような気分であまりにも残念で、このままでは競プロ悪鬼(主に韓国の競プロの人たちが、未練が残って束縛されてる浪人をこう呼びます。)になるのではないかと心配です。 何かに熱心に挑戦してだんだん成績が上がって成果が出て世界大会まで出るそんなロマンがあるじゃないですか？ 今引退してももう十分高いところまで来ましたが、残念な気持ちが残りそうです。 そういう意味で、もしかしたら自分の心の中で競プロが単なる問題解決以上に定着したのではないかと思います。 しかし、一方ではこのように結局メンタルだけが破裂して苦しんでいる場合もまた、こちらで多く目撃してきたので、私にとって最も良い選択が何なのかは依然として悩んでいる状態です。
とにかく、私が計算してみたら、驚くべきことに来年のICPCまでは出場可能なので、選択肢は次のように4つくらいあると思います。(韓国には普通男性の兵役があって、それではなくても大学生たちの休学が比較的に一般的なので、それのせいで他の国よりは二年の時間がもっと与えられる特例があります。)
1. きれいに未練を捨てて引退。
2. 色々な理由で解体する他のチームがあるので、校内のチーム員をよく集めて少なくともセミファイナルくらいは行ける戦力のチーム作り。
3. 大事にして育てた競プロ後輩たち2人が来年除隊して復学するので、彼ら2人を連れて行く。
4. 残りのチームメンバーに土下座して、無理矢理MunSongSongでもう一度出掛ける（？）
最後に、この場を借りて2年間一緒に呼吸を合わせながら走ってきたSongC, mhy908に深く感謝したいと思います。 この素敵な二人の後輩たちのおかげで足りなかった私がたくさん学びながら大きく成長することができました。 競プロ以外でも2年余り同じチームを組んで目標に向かって一緒に走っていった経験は、これからの人生で本当に大切な経験になると思います。
私は心から、私の人生で最高の競プロチーム、いや、すべての分野をひっくるめて最高のチームがどこだったのかと聞くと、躊躇なくMunSongSong Eggdropだったと言えます。 来年、もし同じチームを成すことができなくても、尊敬する2人の後輩たちが必ずRegional優勝という夢を叶え、特にmhyが無冠脱出できることを心の奥底から願っています。 ありがとうございます。
7.問題たちの解き方
全ての問題は韓国のオンラインジャッジサイトであるBOJで解いてみます。AOJや他のジャッジサイトにはあるかどうかはよくわかりません。
A. Apricot Seeds
変なクエリ問題。特定された区間でバブルソートをするクエリが入って、その結果を出す問題です。大会場ではどのチームも解けなかったんです。解き方はちらりと通りすがりながら聞いたが、私の実力が足りないのかよく思い出せない。
B. Black Box
ICPCに出ても良いのかを悩んで見せる変な問題。まずはPython-like pseudocodeが来て、これの逆関数のように作動する関数を作れば良い。 大まかに言うと、シュードコードの作動方式は、まずリストが与えられた時、特定の規則に合わせてリストから元素を取り出してスタックに満たし、そのスタックから最初の項目と再び特定の規則から出てきた項目をswapすれば良い。
swapする規則はリストの最後の元素にかかっており、最後の元素はswapに変わらないことが保障され、一旦その規則に従って再び元素を2つ変えれば良い。 その後、元のリストで必ず最初の元素がスタックでも最初に入るという点から始め、規則を満たしながら入るためにはどの位置に何が入っていなければならないのかを逆追跡して探せば良い。 この時、「n個のマスの中で空いているマスの中で何番目の席」を探さなければならないため、セグメントツリーを通じて位置にどんな元素が入ってきたのかをアップデートしながら具現しなければならないのが最も具現難易度を上げる部分だ。
しかし、具現難易度よりは解釈難易度がはるかに高い。 マンゴーキウイアップルパパイヤバナナメロンココナッツライム··· コードを読んでいると気が遠くなる。
C. Farm
幾何問題であり、私たちのチームは本当に苦労した問題だった。 座標圧縮をよくして、ずっと点をスイープしながら拡張できるところまで最大に拡張する方式ですれば、特に問題はないと言ったが、珍しい問題条件のために変な形の切れた多角形が発生する可能性があり、その場合、x軸の上に感染地が発生すると横一直線形のrectangular areaという珍しい事態が発生する可能性があり、この場合、例外処理を非常によくしなければならなかった。 しかも、このため大会中に質疑応答までしたが、yesと答えが返ってきて、かなり呆れた記憶がある。 私たちはy=-1のところから多角形が始まると仮定して解く方式にした。
D. Fraction
たぶん一番易い問題。かっこの文字列がvalidかどうか確認して、規則によって式を作って計算すればよい。私たちは規則に合わない場合に-1を出すのを忘れて一回間違った。
E. K-Lottery
手軌道にトライ木を作って、エイホ–コラシック法、、、ではなくロリハらしい。fail functionの管理について、ちょっとテクニックが必要な感じでムズイだったそう。文字列は私も弱いので、解き方を聞いたけどよく覚えてない😥
F. Lucky Draws
前から点を描くとしたら動的計画法でできそう。だが、naiveにしたらO(kN^2)という時間なので、関数のmonge誠実を探して最適化すればO(NklogN)で解けるらしい。
G. Magic Cards
実は数字が５０万までだから、1から５０万まですべての数字に対して記録したらいいです。
H. M.S.I.S.
最適に構築していれば、すべての列に対して上か下かは使用されることが分かる。 二つのうち一つ使うものを選んで位置に合わせて入れればいいという。 ここで重要な部分は、両方とも使われるものをどのようにうまく選ぶかですが、上の列に対して整列してD[i][j]=i番目まで選択、下の列から最後に選んだものはj。 という風にして点火式をうまく構築すればn^2に解けて、n=10000なのでギリギリ回るという。
I. Product Delivery
貪欲法。特に説明することもない。以上。
J. Special Numbers
digit DPっていうスタイルの問題。今までのICPCのKorea Regionalではメージャーではなかったんですが、今回に出た。
私の解き方は、f(n,k,zero)を「０からｎまでの数字の中でK-specialなことの数。zeroがTrueならばleading zeroを考える。」って定義した。あと、n の最初の桁をあらかじめ抜いておき、それが 0 のときから n の最初の桁になるまでfor文を回しながら再帰を回すようにした。 例えば、4940までの数字の中で12-specialであるのがいくつあるかを見るには、まず0から999までのうち12-specialなものの個数を数え、次に1000から1999の中で12-specialの個数を数えるが、このときはf(999, 12, True)で入れる。 これは0を0ではなく000と見て、1も1ではなく001と見て··· 同じ感じで、0をかけるといつもすべての数の倍数になるという点をうまく処理するためだ。 その次には2000から2999までの中で「6special」の数を数えなければならないが、千の位に2が入るという仮定の下で残りを数えることだからだ。 このようにメモイゼーションを伴う再帰を回せば、思ったより回る数字は大体限定的なので、時間内にとても余裕を持って帰った。
K. Tandem Copy
SongCが「うへへへ」しながら(本人によると)解いた。文字列のdpだが、変なケースがたくさんあるらしい。
L. Walk Swapping
結局、左に行って右に行く<<をすれば以前と変わることが一つもないので、ずっと左に行く/ずっと右に行くという2つの場合しか存在しない。 すると、数字一つを掴んでその子をずっと一マスずつ移動させる感じで、一周すると数列を一マスずつ左/右にシフトさせたのだ。
一旦可能かどうかを見るには、数列文字列を適当にロリハし、すべてのnに対してn番目の数を回してあれが出るかどうかを判断する方式で見て、可能であれば可能な場合に対して左まっすぐ/右まっすぐで施行回数のうちどれがもっと小さいのか、それをずっと見る方式で解けば良い。 という結論が出たが解けなかった。 実はそれで検証もできなかった。
