ICPCアジア地区横浜大会 2022 参加記

2022/12/27-2022/12/28に行われたICPCアジア地区横浜大会に出場しました。チームはAobayama_dropoutで、メンバーはha15さん・ホスフィンさん・僕です。

これが自分にとって5回目、また早生まれでないため最後のアジア地区大会です。さらに2019年以来3年ぶりにオンサイトで開催されたということで、なかなか感慨深いものがありました。

前日（12/26）

日付が変わるくらいまで持ち込むライブラリの準備をしていました。自分のライブラリほとんどに加え他の人のライブラリからいくつか、さらにACLから二分探索付きセグ木も持ってきてA4用紙10枚分くらいになりました。特に写経のことは考えておらず、コピペ前提の長大なコードもそのまま印刷しました。

GitHub - kotatsugame/library

他の人のライブラリから窃盗してきたコードは以下の通りです。ほぼお守りみたいな感じです。

その後チーム紹介ドキュメントのメイキング記事を書いていたら寝るのが午前4時半になってしまいました。

1日目（12/27）

無事午前8時に起床し、午前9時半の新幹線に乗りました。自由席のない速い列車なので東京駅までは1時間半ほどです。車内では爆睡していました。

東京駅に着いて新幹線ホームでコーチのむげんさんやチームsuzukaze_Aobayamaの三人と合流し、そこから横浜駅に向かって自チームの残り二人とも合流しました。ちょうどお昼時だったので、横浜駅のレストラン街で昼食を摂りました。

午後1時ごろに会場に到着し、当然チーム全員が揃っているためすぐ入場しました。開始まで1時間ほど時間があるので、チーム紹介ドキュメントを読んだり、他チームと交流したりしていました。

午後2時に挨拶があって、リハーサルが開始されました。今年は4問で、Aは簡単枠、Bはインタラクティブの練習、Cはちょっと前のアジア地区A問題、Dはもっと昔の過去問でした。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1400

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1379

ホスフィンさんがAをさっと通したあと、自分がBを通しました。US配列に慣れておらずかなり苦労しました。またこのとき、Vimを使う自分とhaさんで.vimrcに書く内容について合意を取っておきました。と言ってもタブ幅と自動インデントに関することだけなので、ほんの数行です。

その後は特にやりたいこともなさそうだったので、そのままPCを占拠しDを実装しました。この問題はリハーサルの場で何度か見たことがあって、記憶の通り書いたらFAでした。

残ったCはhaさんに押し付けました。問題なく通りましたが、実装されている間に順位表が凍結され、YesNoがあるわけでもないので、結局他チームがどのくらい解いたのかはわからないままです。

その後assertや副作用のない無限ループを書いてREやTLEがちゃんと出ることを確認していました。また印刷も色々試しました。メモ用紙が欲しい場合は適当なファイルを印刷してくださいとのことだったので、/dev/nullを印刷したところ、1文字以上あるファイルを印刷しないと紙が出ないと言われました。

リハーサル後はチーム紹介です。自チームのスライドが表示された瞬間笑い声が上がったので、作った側としては報われた気持ちになりました。

チーム紹介スライド

全チームの紹介が終了し、解散してホテルに着いたのが午後5時半ごろでした。今日泊まるホテルは単にsuzukaze_Aobayamaと揃えただけですが、たまたま3年前と同じでした。ホスフィンさんと同室です。

1時間くらいしたら東北大勢全員で中華街に夕食を摂りに行くことになっていて、それまでの間に昨日書いたチーム紹介ドキュメントのメイキング記事を微修正して投稿しました。

再三強調しておきます。このコードは実行すると自分自身のソースコードをそのまま出力するプログラムになっているので、ぜひお手元で実行してみてください。チーム紹介に「Quine」と書いておきましたが、この語彙は一般的でなく、あまり伝わっていない感触がありました。

kotatsugame.hatenablog.com

中華街では当然中華を食べました。

ホテルに戻ってから、US配列に慣れるため持ってきたキーボードを使ってPCKの問題を解いていました。このキーボードは2019年、アジア地区横浜大会の企業賞で獲得したものです。

LegalForce様からUS配列のキーボードをいただくことができました！

ICPCアジア地区横浜大会 2019 参加記 - kotatsugameの日記

午後11時半ごろ就寝しました。その時間からCF div.2がありましたが、流石にパスしました。

2日目（12/28）

午前6時半に起き、ホテルの朝食を摂って、部屋に戻ってきてからは昨日のCF div.2を解いていました。結局チームで集合する午前8時半までに解き終わらず、ホテルから会場に向かう途中で実装を終えてテザリングで提出しました。なんとか通りました。

午前9時前に会場入りし準備をして、いよいよコンテスト本番です。

コンテスト

問題文：https://icpc.iisf.or.jp/2022-yokohama/wp-content/uploads/sites/9/2022/12/all_with_cover.pdf

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

序盤

全員で使うようなテンプレもないので、序盤の動きについてはあまり細かく決めていませんでした。.vimrcについては、自分が書くときにはいつの間にか必要なものが整備されていました。

ホスフィンさんがシステムへのログインとAを、haさんがBを担当し、自分はC以降を順に読んでいました。以下、読めた分までの各問題の印象です。

C：明らかにフローっぽい見た目をしていますが、どうすればいいかは全くわかりません。シャッターを「2枚」壊すというのはどうやって表現するのでしょうか。

D：ずらすコインを全探索して、平行移動はバウンディングボックスを見る、ということをしたくなりました。しかし実装もコーナーケースも辛いし、そもそもこの全探索は間に合いそうにありません。

E：dpの高速化を考えます。最近ABCで見た分割統治をしてみたくなりました。\bmod{998244353}が2べきを強調する形で書かれているので、統治部分では畳み込みをするのではないかと疑いましたが、効きそうな形にできませんでした。

F：適切な言い換えができるかどうかという問題に見えます。すぐには思いつきません。

G：木から辺を1本削除し、1本追加してできた新しい木において、特定の2頂点間の距離を最大化します。説明のため2頂点をs、tとおきます。削除する辺はもともとstパスに乗っていたものとしてよいです。どれを削除するか全探索すれば解けそうに見えました。

Gを詰めているうちに、グリッドという問題設定を完全に忘れ去ってしまいました。どういうことかというと、どんな辺でも追加してよいと勘違いしたのです。この場合、辺を削除してできた二つの連結成分それぞれでs、tから最も遠い頂点を選び、結ぶのが最適です。実装もやればできます。

このあたりですでにAは通っており、Bも提出が行われました。残念ながらWAだったのですが、ただの出力形式ミスだったのですぐ直り無事2完となりました。インタラクティブではこういうミスはありがちで、まあどうしようもなかったと思います。

G問題

Gの考察をうまく伝える自信がなかったので、自分で書いてしまうことにしました。順位表を確認すると、AB以外にACが出ているのはDEFのみのようで、FAが狙えるかもとワクワクしました。

しばらくして書き上がるも、サンプルが合いません。ここでようやく勘違いに気づきました。それと同時にまだACが出ていないことにも納得が行きました。諦めてPCを空けようとしましたが、その時点では特にすることもなかったため、そのままPCの前に座っていました。

冷静になると、追加する辺uvを全探索する方針が生えます。stパス上でuから最も近い頂点をp_u、vから最も近い頂点をp_vと置くと、p_u\ne p_vを満たす場合のみその間の辺を削除することでstパスがuvを経由するようになります。

各頂点uに対しp_u、{\rm dist}(p_u,u)、stパスにおけるp_uの位置が求まれば解けます。頂点sを根とするとp_u={\rm lca}(t,u)と書けるため、ここから他の値はすべて求められました。

LCAライブラリを貼りたくなりますが、写経が面倒です。今はクエリの片方がtと固定されているので、単にdfsするだけで求まることに気づきました。これを使って再度実装するとサンプルが合いました。

途中の計算も出力し丁寧に確認してから提出すると見事通りました。71分時点のことで、なんとFAが取れていました。結局勘違いしていたときのコードはほぼ使いませんでした。

D問題（1）

自分が実装している間に残りの問題はすべて読まれたようです。相変わらず解かれているのがDEFのみということで、多人数で詰めたほうが良さそうなDについて議論を始めました。

とりあえず、マッチ先のパターンを回転させて平行移動だけの問題にします。どれだけ移動するかをバウンディングボックスを見ることで決めたいのですが、コインの移動によって変わってしまうのが問題です。

ここで、マッチ元のパターンも回転させることで元のバウンディングボックスの左上をそのまま使えるようにするというアイディアが出ました。実はこれは正しくなく、コインを動かして置くことで4辺すべてが変化し得るのですが、気づかずに解けているものと判断しました。

細部の詰めと実装を二人に押し付け、自分は別の問題を考えに行きました。

E問題

E問題の分割統治を改めて考えます。他の\bmod{998244353}の問題も2べきを強調して書かれていたので、この書き方だから畳み込みを使うというようなことはなさそうでした。

分割統治ですから、(l,r)があったときm=(l+r)/2として、S[l,m)のsuffixとS[m,r)のprefixで足すとICPC-ishとなるものを考えたいです。prefixやsuffixに含まれるI、C、Pの文字数を、前者は(I,C,P)、後者は(i,c,p)と置き、関係を考えます。

まず、Iの文字数がCの文字数と等しく、それよりPの文字数が多いケースを考えます。条件はI+i=C+c\lt P+pで、I-C=c-iかつI-P\lt p-iと分割できます。(I-C,I-P)のようなペアを用意してsuffixとprefixを適切にソートすれば、分割方法に関するdpの遷移が簡単にまとめられました。

(l,r)に対する計算量がO( (r-l)\log(r-l))なので全体ではO(|S|(\log|S|)^2)ですが、TLが6secもあるので間に合うでしょう。

この間にDは、先程の勘違いを修正した上で実装に入っていました。印刷して一旦離れるタイミングがあったのでPCを借り実装しました。すぐサンプルが合って、ランダムケースも手元で3secだったため自信を持って提出しました。ジャッジにはしばらく時間がかかりましたが、無事通りました。

F問題

残りで解かれているのはDFKです。Dの実装が再開されたのを横目に、F問題の考察に入りました。このあたりで昼食が配られたため、すぐ食べました。

言い換えとして、それぞれの孤を始点から終点までの有向線分とみなすのを試しました。こうすると、元のループは角がすべて直角であるようなループと対応します。線分が縦横の向きになるよう全体を45度回転しておきます。

ループになるための条件の一つとして、当然ながらちゃんと始点に戻ってくる必要があります。これは、右向きの線分の長さが左向きの線分の長さと等しいこと、上向きと下向きについても同様であることが必要十分条件です。

またもう一つ、線分から孤に直した際にスムーズに繋がっている必要があります。孤に直す際には線分の向きに対し右側に膨らませるか左側に膨らませるかで2通りあって、線分の接続が直進・右折・左折のどれであるかによって規則が異なり扱いづらいです。

4方向の線分がそれぞれ奇数個ずつあれば、1回転するだけで見事に繋げられます。偶数個ずつあれば2回転すればよいです。Nは偶数なので、残りは2方向が偶数個、2方向が奇数個となるケースです。

ここで、サンプル3が見事にそのケースであることに気づきました。このケースの答えがNoであることから一般に構築できないだろうという予想が立ちます。また、実は一つ目の条件の判定がそもそも難しいので、ここで変な条件は出ないだろうというメタ読みもありました。

結局、問題は次のように書き直されました：rたちを四つのグループL,R,U,Dに分割し、\sum L=\sum R、\sum U=\sum D、|L|\equiv|R|\equiv|U|\equiv|D|\pmod 2となるようにできるか。

OpenCupで4分割を2分割2回にするアイディアを見た気がするので、その方向で考えていたところ、見事に成功しました。

rたちを総和が等しい二つの「サイズ偶数の」グループに分割する方法が、(A,B)と(X,Y)の2通りあるとします。ただし(X,Y)\ne(A,B),(B,A)です。このときL=A\cap X、R=B\cap Y、U=A\cap Y、D=B\cap Xとすれば条件を満たします。逆にA=L\sqcup U等とすれば(L,R,U,D)から( (A,B),(X,Y))を作れるので、これが必要十分条件です。

つまり分割方法を数えるdpをすれば良いです。ホスフィンさんに考察を聞いてもらって、実装はそのまま押し付けることにしました。Dが空いたタイミングで書いてもらい、横から口出ししていました。(X,Y)=(B,A)のケースを数えてしまうようでサンプルが合いませんでしたが、単に必要な分割方法を倍にすれば対処できて、無事通りました。

D問題（2）

Dは難航しているようです。印刷されたコードを少し読みましたが、時間をかけて読む必要がありそうだったので、この時点ではそのまま任せきりにすることにし、自分はKを考え始めました。

イベントの並びをbitDPで計算し、コストは折れ線のまま管理することで解けると思いました。折れ線の並行移動、累積MIN、折れ線同士の足し算・MINが必要で、それぞれ頑張ると実装できそうです。Dが通ったらすぐ書けるよう、しばらく紙コーディングしていました。

しかし、コンテストが残り30分くらいになってもDはサンプルすら通っていませんでした。この時間からKに手を付けても両方通らず終わるだけだなと確信したため、以降はDを通すことに全力投球することにしました。

今の所少なくとも、回転後の座標を回転前の座標に復元する部分にバグがあるらしいです。書かれていたコードのロジックが理解できなかったので自分の思いついた方法を伝え、さらに結局実装を奪い取って自分で書いてしまいました。

左上の2\times 2マスを見ると、縦横それぞれについて回転前の座標の増分と回転後の座標の増分の対応が取れます。ただしそういう2\times 2マスが取れるとは限りません。入力の受け取り、またバウンディングボックス外の切り詰めの際に、2行・2列に満たなければ右下に伸ばしました。左上さえ揃っていれば良いのでこの拡張は問題になりません。

10分程度かけて実装するとなんとか動き、出力も正しいものが出ました。後から考えてみればそういう対応は90度回転した回数からわかり、もともとそうするコードが実装されていたはずですが、多分マジックナンバーが間違っていたのでしょう。

見つかったコインの動かし方を一つだけ出力するのではなく全部出力してみてサンプルに対し想定通りの挙動をしているか確かめる、という方法で丁寧にチェックしました。少しだけ修正すれば残りは良さそうということで提出すると、なんと一発で通りました。

10分ちょっとの残り時間は順位表を見てワイワイ話していました。

コンテスト後

解説会まで1時間弱時間があったため、ホスフィンさんと一緒にスポンサーブースを回りました。LegalForce、現LegalOn Technologiesさんのブースがあったため、3年前に頂いたUSキーボードのお礼と感想を一方的に喋ってきました。半分くらい回ったところで時間になりました。

解説ではHが中難度枠だったということに衝撃を受けました。実は自分も目を通していたのですが、不等式が大量にあることを認識した段階で諦めてしまっていました。不等式の対称性についてはhaさんのメモにそれらしいことが書いてあったものの、真面目に考えようとはしませんでした。

またEの想定解がかなり天才寄りで面白かったです。分割統治を使わない場合でも、結局I、C、Pの個数を見てBITか何かで頑張った人が多いのではないでしょうか。自分はあまり理解していませんが、後からsuzukaze_Aobayamaに聞いた解法がそういうものでした。

CでS、T、Uが出現する位置は、問題文中で「outermost」と表現されていました。自分はこれを単に「外周のマスに存在する」と解釈したのですが、実はもっと強く、四隅のみを指していたようです。

YesNoの結果は6完9位でギリギリ一桁を達成しました。企業賞はありませんでした。

すべてのプログラムを終えた後、まずスポンサーブースの残りを回り、その後はずっと懇親していました。基本的には自分から名乗って特攻していたのですが、中にはTCO Finalsの際に公開された自分の顔を覚えていて話しかけてくださった方もいて感動しました。

午後6時くらいに会場を出ました。とうの昔に会場を去った東北大の他の人々は近くのビアバーに集まっているようだったので、そちらに合流してさらに午後8時過ぎまで喋っていました。

現在地から東京駅までの移動を考えると、実はこの時間は予定していた新幹線に間に合うギリギリです。酔っ払った状態で急いで移動し、何とか間に合いました。新幹線ではまた爆睡していました。

日付が変わる前に家に帰り着き、JAGへ入会メールを送りました。

結果

先ほども書きましたが6完9位でした。昨年の順位は8位だったため、これまで順位を単調減少させてきたのが最後の年にして失敗してしまったということになります。これは残念でした。

しかしコンテスト中の動きには満足しています。特に3人全員が2問ずつ実装していること、冷えている時間がなくコンスタントに問題を解き続けられたことが良かったと感じました。実際は冷えていないと思っていたのは自分だけかもしれません。他の二人にはDの考察・実装を押し付けてしまったので、苦しい時間が長かったかと思います。

今回のコンテスト環境に関して、コマンドラインからファイルを印刷できるのはとても便利でした。何ならモニターにかじりつかなくてもよいし書き込みも自由にできるので、これについてはオンラインでやるより快適だったかもしれません。

やはりオンサイトは非常に楽しかったです。最後の年にこのような形で大会に参加できて嬉しく思います。これまでの5年間でチームAobayama_dropoutに関わった皆様、特に自分と組んでくださったチームメイトの方々に感謝します。

kotatsugame.hatenablog.com