2022/03/15-2022/03/16に行われたICPCアジア地区横浜大会に出場しました。チームはAobayama_dropoutで、メンバーはゆきのんさん・ha15さん・僕です。

今年はサークルから2チーム出場するということで、顧問の先生の研究室を2部屋貸していただけることになりました。もうサークル運営からは退いているので、交渉は全部現サークル長にぶん投げました。お二方ともありがとうございました。

1日目（03/15）

研究室に正午集合ということになっていました。十分間に合う時間に起きたのですが、うっかりコードゴルフを始めてしまい、集合時間を過ぎてから家を出ることになりました。

到着してみるとすでに使用する部屋が振り分けられていて、他にすることもないので購買で買った昼食を食べたりPCの準備をしたりしました。今日使うのは普段研究が行われている部屋のようで、すべての席にモニターとケーブルがあったので、全員がデュアルディスプレイにしていました。

受付を問題なく済ませます。起床に失敗した人をしばらく待っていたらしく、開会式は少し遅れて始まりました。コンテストのデモで取り扱われた、 $1$ から $n$ までの和を求めるという問題文なのに実は $n\le 0$ のケースが入っているというあまりに性格の悪い問題に震え上がりました。開会式の遅れが響いて、リハーサルコンテストも20分遅れで始まるようです。

例年ならば4問のところ、今年はなんと11問もありました。適当に眺めてみると、昨年の横浜大会の問題が全部そのまま出題されているようです。昨年の問題と聞くと、C問題「Short Coding」といういかにも楽しそうな問題に特攻して、単純なミスに気付かずFAを逃したことが思い出されます。リベンジのチャンスだと捉えて、まずこの問題を解くことにしました。

CのFAはonionsの43分なので、ギリギリ負けたことになります。改めて以前のサンプルに対する出力を確認してみると、サンプル1から正しくない解を出力していることに気づきます。行数だけじゃなくてちゃんと内容にまで気を配っていれば……と後悔することしきりでした。
ICPCアジア地区横浜大会 2020 参加記 - kotatsugameの日記

解くと言っても解法を覚えているので、その通りにコーディングするだけです。慣れないswitch文を使ったのでコンパイルを通すのに少し手間取りましたが、サンプルはすぐに合って提出、無事FAを取りました。どのくらいの時間がかかったかは忘れてしまいました。

次にH問題に取り組むことにしました。これも昨年僕が解いた問題らしいですが、あまり覚えていません。解法も再度ひねり出しました。ただ、 $10^3$ より大きな素数に対して昨年より定数倍が悪い方針を取ってしまい、TLEを解消するのにかなり苦労しました。区間に対して素数とその出現回数のペアを管理し、出現回数の大きなほうから3つ管理すればよいというものです。マージ関数をいろいろ書き換えるのはあまり効果がなく、最終的にセグメント木の初期化を $O(N)$ で行うとそこそこ高速になり、1WAを挟みつつコンテスト終了直前にギリギリ通りました。

H問題のWAは、投げてからかなり時間が経って出た結果だったので、どこか大きなケースで落ちているものと思ってずっとデバッグしていたのですが、実はサンプルからすでに出力が異なっていました。どうやらICPCのジャッジは、WAの場合は全テストケースを実行してからその結果を出してくるらしいです。明日は気を付けようと考えました。

今日書いたコードをAOJに提出してみました。C++14とC++17で実行結果が違い、かなりモヤモヤしましたが、結局解決できないまま帰宅しました。夜はずっとコードゴルフなどをしていて、午後11時くらいには寝る準備が整いましたが、乱れた生活リズムですんなり眠れるはずもなく、うっかりラノベを1冊読んでしまいました。結局眠れたのは午前3時頃でした。

2日目（03/16）

今日は余裕を持って家から出られましたが、朝ご飯を買おうと思っていた購買が開いておらず、ちょっと離れたコンビニまで往復していたら思っていたより遅くなりました。午前8時45分頃に部屋に到着してPCの準備をします。今日は家からキーボードとマウスも持ってきました。Zoomを聞いているとコンテスト開始が遅れるとのことだったので、その時間で腹ごしらえをしました。午前9時10分、コンテスト開始です。

コンテスト

問題：https://icpc.iisf.or.jp/past-icpc/regional2021/problems-2021.pdf

順位表：https://icpcsec.firebaseapp.com/standings/

J問題

初動は他の2人がAとBで、僕は後ろの方の問題を眺めるという分担でした。J問題にたどり着く前にIとHを順に読んだ記憶があります。Iはハマったら辛そうだったので、HはTL 30secに恐れをなして、それぞれ解くのを諦めました。その次にJ問題を読んで、見た目にはいかつく感じましたがとりあえず少し考察してみることにしました。

2次元平面上の点が $n\le 2\times 10^5$ 個与えられるので、点のペア $( (x_p,y_p),(x_q,y_q))$ であってすべての点 $(x,y)$ が $x_p\le x\le x_q$ または $y_p\le y\le y_q$ を満たすようなものを数えよ、という問題です。 $x$ 座標と $y$ 座標がすべて異なるのがかなり優しい制約です。とりあえず点が $x$ 座標の昇順にソートされているとしても問題なく、このとき $p\lt q$ がわかります。 $p$ を決め打って $q$ を数えようとしたときの条件を整理してみます。

まず、 $y_p\lt y_q$ です（後からわかりましたが、これは嘘です）。さらに、インデックスが $p$ 以下の点のみを考えたとき、 $y$ 座標の最大値が $y_q$ 未満であり、かつ最小値が $y_p$ である必要があります。インデックスが $q$ 以上の点についても同様、 $y$ 座標の最小値が $y_p$ より大であり、かつ最大値が $y_q$ である必要があります。逆に、これらが満たされていればペア $(p,q)$ は問いの条件を満たします。

文字をいくつか導入して式で表してみます。「インデックスが $p$ 以下の点の、 $y$ 座標の最大値」を $y_l$ 、「インデックスが $q$ 以上の点の、 $y$ 座標の最小値」を $y_r$ とすると、 $y_p\lt y_q$ 、 $y_l\lt y_q$ 、 $y_p\lt y_r$ が必要です。このうち1番目の式は2番目や3番目の式から自動で満たされるので、考えなくてよいです。また「～の最小値が $y_p$ 」・「～の最大値が $y_q$ 」という条件については、それを満たす点のみ計算に含めることで常に成り立っていると扱って構いません。結局、ペア $(y_q,y_r)$ の列に対して、 $(y_l,y_p)$ よりどちらの要素も大きなペアを数えるクエリと、ペアを追加するクエリが高速に処理できれば良いです。

よく考えると値を追加するクエリは考慮せず、最初からすべての値のペアが与えられているとしてよいです。なぜなら、 $q\le p$ の場合、 $y_l$ の定義より $y_l\lt y_q$ が満たされることはないからです。もともと2次元平面における矩形内の点のカウントクエリでしたが、更新がない場合はもうちょっとシンプルなデータ構造でぶん殴ることができます。僕は蟻本p.171にある列を持つセグ木のライブラリを貼りました。

1WAしました。 $y_p\le y\le y_q$ の代わりに $y_q\le y\le y_p$ を満たしていてもよいと誤読したからでした。この場合は単純に上のコードを倍にすればよいです。逆に修正は、答えに余計な値を足している部分を消すだけで済みます。40分時点で通り、順位表ではFAに見えました。ただし、 $p$ と $q$ を列の両端に取ることで、 $y_p\lt y_q$ という条件が必要なくなる場合があります。逆に $y$ 座標の最小と最大を選んでもよいです。これらのケースを考慮しないまま通してしまいました。その後修正が入ったそうですが、僕の提出はすでにACを得ているためリジャッジの対象にはなりませんでした。

D問題（1回目）

僕がJ問題を解いている間にA問題を通したゆきのんさんは、B問題がややこしいということでそちらのヘルプに入っていました。僕はガン無視して、他に唯一ACが出ていたG問題に進みました。番号の降順に見て現在の木の数とまだ何が来るか決まっていない子の数を持つdpはすぐ思いつきましたが、ループを作ってしまうケースでどうしたらよいかわかりません。そうこうしているうちにB問題が通り、またsuzukaze_AobayamaによってD問題が通されたので、G問題は他の2人に任せてD問題に移ることにしました。

作った木の直径の最大化というのは、パスを一番長くなるように取ることを考えればよいです。パスのうち最も標高が高い点で分割するとよさそうに見えました。標高の昇順に見て、そこを端点とする最も長いパスの長さを管理しつつ、そうして作った2つのパスを接続してみます。

結論から言ってしまうと、この方針はダメダメでした。パスを最も標高が高い点 $i$ で分割したとき、 $i$ と隣り合う点 $j$ 、 $k$ が $j\lt i\lt k$ を満たすと思い込んでいましたが、そんなわけはありませんでした。例えば $j\lt k\lt i$ の場合、ある位置 $j\le l\lt k$ が存在して、 $j$ から続くパスは $l$ 以下の点のみを使い、 $k$ から続くパスは $l+1$ 以上 $i$ 未満の点のみを使うことになります。そのように分割されてしまった場合を高速に計算するのはどう考えても不可能でした。

3WAくらいしてからどうやらダメそうだということに気づきました。それからもしばらく唸っていましたが、解ける気配がないため、頭を切り替える意味でも別の問題に取り組むことにしました。

G問題（1回目）

まず、まだ解けていなかったG問題を再度考えてみます。番号の降順に見て失敗したのだから、昇順に考えてみるということを思い立ちました。すると、番号を昇順に見たときは常に木が1つしか存在できないという真っ赤な嘘を思いついてしまいました。そのような事実が存在するなら、特に深いことは考えず $O(n^2)$ のdpが行えます。制約が $n\le 300$ と $O(n^3)$ を許容しているのを訝りながらも、この方針をゆきのんさんに伝えて実装してもらうことにしました。

C問題

他に唯一ACが出ていたC問題を考えます。こちらはすでにhaさんが取り組んでいました。操作がちょっとややこしいですが、読み解いてみると、デコード後の文字列が与えられているならコードを後ろから解釈して正しくデコードできるか確かめられることがわかりました。例えば $(A_1,L_1)$ を決めたとき、エンコードした文字列を反転したものでは、この操作は $(A_k,L_k)=(L_1,A_1)$ と解釈されます。この $(A_k,L_k)$ の操作によって文字列 $s$ が完成する必要があるのですから、文字列 $s$ の後ろのほうをちょっとチェックすれば本当にそのような出力がなされるかわかります。

この考察をもとに、とりあえず答えとなる文字列のうち最短のものの長さがわかります。「正順に読んでデコードしたとき、文字列 $s$ のどこまで出力されるか」と「逆順に読んでデコードするとしたとき、文字列 $s$ のどこからがすでにエンコードされているか」の2つを持つdpは、状態数が $(|s|+1)^2$ で、遷移は $0\le A,L\le 9$ を全部試しても $100$ 通り、チェックにかかる時間を考えても十分間に合います。ただ、辞書順最小を求めるのはちょっと難しいです。

ここで、dpの状態を頂点、遷移を辺だと思うと、 $(|s|+1)^2$ 頂点の有向グラフが得られます。このグラフ（の辺を反転したもの）でゴールからBFSしておくと、スタートからどの遷移を選ぶことで最短でゴールにたどり着けるかがわかるようになります。そのような遷移であって特に辞書順最小であるようなものを常に選びつつ文字列を構築すれば、全体としても辞書順最小になるので、これで解けました。

実装がちょっとややこしいと感じたので、haさんに解法を伝えることを勝手に諦め、一人で書き始めました。幸い一発で通りました。3時間6分時点と、B問題が通ってから実に2時間以上動きがなかったことになります。

G問題（2回目）

嘘解法を実装してもらっているG問題は、当然まだ通っていません。次はこれを何とかすることにしました。書いてもらったコードを隅から隅まで読んで、 $n=3$ を全通り手で試して比較しても、何が違うのかわかりませんでした。考察に間違いがあるのではと何度も思考の過程をなぞり、ようやく先ほどの嘘、つまり2つの木をより大きな番号の頂点を使って1つの木にすることが不可能ではないことに気づきました。

絶望しつつ、改めて考えなおします。番号の降順に見たときはループの発生を止められずダメでしたが、昇順に見たときどうかはまだ考察していませんでした。2つの木を1つの木にする場合、今見ている頂点をある木の葉に入れつつ、さらにその下に別の木を入れます。このとき「今葉を使った木」を入れてしまうとループになります。ところが、このようなケースは下に入れる木を「今葉を使った木」以外のものにすれば発生しません。そのような除外すべき木は常に1つだけ存在するので、ただ係数から1を引くだけで対処可能です。

結局、一番最初に考えていた $O(n^3)$ のdpで解けそうだとわかりました。制約の $n\le 300$ にもバッチリ根拠があったということで、ミスリードか何かだと思っていた自分を恥じるばかりです。ゆきのんさんに解法をうまく伝えることができず、実装を奪い取って書き始めました。遷移でミスを重ね、+3WAくらいしつつ何とか4時間21分時点で通りました。

さて、このように番号の昇順に見て解いたG問題ですが、本質はループを作るような遷移の際に「今見ている頂点を葉に入れる」→「今見ている頂点の葉に入れる」の順に考えることで、それさえ行っていれば番号の降順に見ても解けるようです。そのような考慮の順番の入れ替えを意図せず行っていただけなので、運よく解けたという認識です。

D問題（2回目）

残り40分もないですが、何とかD問題も通したいです。haさんに自分の先ほどの解法を説明している過程で、パスのうち最も標高が高い点で分割するのではなく、その点から2方向でそれぞれ作られたパスが互いに越えられない位置で分割するのがよいのではないかと感じました。つまり、上で導入した変数 $i,j,k,l$ で言えば、 $l$ で分割するということです。

この時、左側で作るパスは使う頂点のうち最も右側のものを、右側で作るパスは最も左側のものを保存しておきたいです。逆に保存しておきたい位置の頂点に対して値を持つと考えると、パスに新たに頂点を追加するときの更新は、区間加算と1点更新で書くことができます。左側で作るパスで言えば、使う頂点のうち最も右側のものが更新されないなら、その位置で持っておいたパスが同時に1つ伸びる、つまり対応する区間に1が加算されるということです。

これらは遅延セグメント木で書けます。半信半疑でサッと実装してみるとサンプルが合い、また以前に作っておいた、これまでの提出に対するハックケースも通ったので提出、ACしました。4時間34分時点でした。

1回目の挑戦の時は、パスを2本のパスに分解するという辺りになんとなく再帰っぽさを感じて、そのような考え方にすぐ飛びつきましたが、そもそも問題に一切再帰的な構造がないことをもっと重要視すべきでした。 $i$ を決めてから $l$ を決めるのは不可能な一方、 $i$ を決めずとも $l$ は全探索できてしまったのはそこから来ていると考えています。

残り時間

残り時間でI問題を読むことにしました。1本の辺で結ばれた2頂点を取り除くのが一番うれしいので、それが行いやすいように全域木を取って考えてみます。葉から少しずつ切り取ってみて、そうできないものはウニグラフを切り取って適切な処理を行えばよさそうと思い、時間もないので実装してみることにしました。結局これは間に合いませんでしたが、改めて考えてみればこの方針が上手くいかないケースも簡単に作れてしまいました。

コンテスト後

凍結前4完は、改めて考えてもあまりにもひどいです。一応その後2つ通したということで何とか面目を施した感じもありますが、国内予選で負けてからライバル視しているsuzukaze_Aobayamaは凍結前5完、さらに2問に提出があります。こちらはペナルティが大量にあるので、勝つためには完数で差をつける必要があります。まさか地区予選でも負けてしまうのかと気が気ではありませんでした。

休憩が1時間弱あるので、その間に解散して、それぞれ自宅からGather上の懇親会に参加することになりました。Gatherにログインしてから知り合いと少し話したりもしましたが、コンテストの出来だったりYesNoに気を取られてあまり盛んに交流はしませんでした。

YesNoの結果は6完8位。変わらず5完だったsuzukaze_Aobayamaに、何とか勝つことができました。

その後はGartic Phoneに混ぜてもらったり、社会人の方々の食事事情を聞いたり、開会式のPVの裏話を聞いたりして、Gatherが閉まる午後9時過ぎまでずっと交流していました。PVについて、東大だけやけに印象に残るなと思っていたら、小節数の関係で1大学だけ少し長く表示していたらしいです。4チームもいることですし、まあ順当に思えます。ラスボス感が癖になりました。

ICPC 2021 国際大学対抗プログラミングコンテストアジア地区横浜大会、の開幕映像を担当しました！チームの記念になれば嬉しいです

ぜひ高評価、コメントいいねマイリス登録お願いします！

PV・MVの制作依頼もお待ちしてます

YouTube https://t.co/GceibJ9hNc

ニコニコ https://t.co/cYBYr9dEFg pic.twitter.com/RrF2adYHnR
— 百千万億萬 (@TumoiYorozu) 2022年3月16日

結果

直前に書いたように、6完8位でした。順位表全体を見ても、最低限解けるべきだった問題は何とか解けているように見えなくもありません。ただここから+1完はどうあがいても無理だったので、上位争いには程遠く終わりました。一方suzukaze_AobayamaはCに加えてFもAC直前まで来ていたそうだったので、今回この結果で上回れたのもたまたまな気がしてきます。

今回のコンテストは何もかもが上手くいっていません。まず僕の頭が悪いです。さらに相変わらずチーム戦が下手くそで、結局CDGJは全部僕が実装を奪い取ったりして通してしまいました。G問題をゆきのんさんに割り振ったあたりは結構考えたムーブのつもりだったのですが、肝心の解法が大嘘ということで、やはり頭が悪いと言わざるを得ません。こうやって参加記を書きながら思い返してみて、他の2人が何をしていたかというのがほとんど分かっていないことに気づきました。自分のことしか考えていない・見えていないということです。

頭が悪いのは、国内予選からこちらさっぱり精進していないからです。チーム戦が下手くそなのもチーム練習をしていないからです。もうとにかく練習不足です。

ただ、自分のことだけを振り返ってみると、今日は最初から最後までずっと問題を考えていました。一切読んでいない問題もありましたが、それらを考えている時間で他の問題が間に合わなかった可能性もありますし、またそれらは結果的に解かれなかったので、良しとしましょう。嘘解法を何度も生やし続けたとは言え、まともに取り組んだものはちゃんと全部通せたというのは、すっきり終われる結果ではありました。

今年でゆきのんさんも引退ということで、来年のAobayama_dropoutはどうなるのでしょうか。正直、今更チーム戦が上手になるとは思えませんが、かと言って一人で戦った場合は黄色3人にも負けてしまうということが分かったので、どうしようもありません。精進せねば。