2022/11/27に開催された模擬地区予選にチームAobayama_dropoutで参加しました。メンバーはha15さん・ホスフィンさん・僕です。

今年はどうやら横浜大会がオンサイトで行われそうだということで、競技ルールもコロナ禍前と同様のものが推奨されていました。

よって我々も国内予選の時に使った大学の演習室に集まり、コピペなし・検索なし・同時コーディングなしで参加しました。

ただしPCが各自1台ずつあったのと、部屋の壁がホワイトボードで覆われていたのは本番と大きく異なる点です。

問題文：2022/Practice/模擬地区予選/問題文とデータセット - ICPC OB/OG の会

戦略

チームメイト二人が簡単とされているA・Bを通している間に自分が残りを読むというのはこれまで通りですが、そこで解けた問題があったとしてもすぐコーディングに入らず、他の人に任せてそのまま別の問題を読み続けました。これを徹底したという点で、これまでとは大きく異なる立ち回りでした。

読んだ問題の概要と制約、さらに解法がわかっているものはそれもホワイトボードに書きました。これはオンラインの頃HackMDでやっていたことの再現です。本番では、少し煩雑ですが紙を1問につき1枚用意するなどして対応することになるでしょう。

自分が読んで解法を考えた時間と、それが実装され通った時間が少し離れています。以下は時系列をできるだけ保存した状態で書きましたが、コンテスト中の行動を逐一覚えているわけではないため、一部前後する出来事があるかもしれません。

A問題のACまで

Cから開いて読み始めました。

Cはグリッドグラフ上ですべての辺を通る閉路ということで、ハミルトンだったかオイラーだったか覚えておらず検索しそうになってギリギリで思い留まりました。問題自体はすぐ解けるようには見えなかったので次に進みました。

Dは問題文がシンプルでとっつきやすそうです。実際、 $O(N^2)$ 状態のdpの遷移をデータ構造で頑張ることで、すぐ $O(N^2\log N)$ になりました。制約が $N\le 5000$ なのでちょっと怪しいですが、通るだろうと判断し、解けたことにしました。

E、Fは読んだだけです。

このあたりでホスフィンさんのAが2WAくらいしており、自分も読んでみたのですが、二人して信号が切り替わるタイミングの把握に失敗し、もう一つWAを重ねてしまいました。

改めて読みなおし、都合4度目の提出でようやく通りました。ヘルプに入ったならちゃんと腰を据えて読まなければなりませんでした。

B問題のACまで

haさんが読んでいたBはもう書けるそうなので実装してもらい、自分はまた問題を読み続けました。ホスフィンさんにもLから逆順に読んでもらいました。

Gも読んだだけでした。

Hはまたとっつきやすそうと判断しました。ちょっと考えてみると、SCCした後のDAGが一直線になっているため、そこを遡るようにdpすることでコストが求まりそうです。これも解けたと判断し、チェックの意味を込めてホスフィンさんに解法の説明をしました。

Iは読んだだけです。このあたりでBが通ったはずです。

D問題のACまで

今のところ解けているのがDとHです。Dは適当なデータ構造を、HはSCCを必要とするので、どちらにしても写経の必要がありました。Dのほうが素早く書けるだろうということだけ伝え、分担は二人に任せて自分はさらに問題を読んでいました。

Jは答えを二分探索すると、 $N$ 個の円で領域が覆われないか判定する問題になります。2円の交点や境界と円の交点であってほかの円に含まれないものが存在するかチェックすれば解けそうですが、計算量が $O(N^3)$ になってしまいました。

Kは構文解析で、どこかで見たような圧縮が施された文字列に関する問題です。

Lはホスフィンさんが書いた概要で把握していました。これで自分は全問題の概要を知ったことになります。

Kに見込みがありそうだと思ってしばらく考えてみたのですが、圧縮部分をスキップしようとしてもうまくいかないことに気づき、諦めました。

この間にDをホスフィンさんが担当することに決まって、データ構造としてBITの写経がされていました。区間MAXをする必要があるので普通ならセグ木を持ち出すところですが、区間の左端が常に全体の左端と一致するためBITでも書けます。定数倍的にも実装量的にもセグ木を持ち出す理由はないと説明し、そうしてもらいました。

さらに解法のコーディングも終わりかけていたので、少し見てインデックスなどに口出ししました。順調にサンプルが合って提出すると通りました。

H問題のACまで

haさんがSCCの写経を始めたのを後目に、I問題を考えてみました。情報を重み $x$ の辺 $a\rightarrow b$ と重み $-x$ の辺 $b\rightarrow a$ のことだと思います。すると情報の矛盾は辺の重みの和が0にならない閉路に対応します。

情報をちょうど一つ削除すると矛盾が解消されるそうですから、そのような情報は矛盾する閉路すべてに乗っています。さらに、矛盾しない閉路に乗る辺を一つ削除しても閉路の残りの部分が削除した情報と同じ意味を持つため、そのような閉路に乗っていないということも言えます。

このあたりで解法に見覚えがあることに気づきました。後から調べるとMulti-Universities Campの9回目で出題されていたようです。自分が担当した問題だったので記憶に残っていたのでしょう。

Cは重み付きの単純グラフに関する問題。ただしこの重みは、辺eeについて順方向に通れば+Pe+Pe、逆方向に通れば−Pe−Peとなる。
週記（2022/08/15-2022/08/21） - kotatsugameの日記

https://ac.nowcoder.com/acm/contest/33194/C

dfs木の後退辺で作られる閉路だけ考えたり、木上のimos法を使ったりすることで検出できることを覚えていました。ちょうど一つだけが候補になることを確認し、答えとすればよいです。

解けましたが、当時合わせるのに結構苦労した覚えがあったので、こればかりは自分で実装することにしました。

次は順位表を見て、C問題を改めて考えてみました。冷静になると全頂点の次数が偶数になるように辺を足せばよいです。最初の時点で次数が奇数の点は、グリッドの上下左右の辺上にあるもののみです。当然偶数個なので、それらの間のパスを考え、最小重み完全マッチングを解けばコストの最小値が求まります。

ただ、一般に解くのが難しいどころかライブラリを持っておらず不可能なので、どうにかして二部マッチングだと思う必要があります。ホスフィンさんが左右の辺と上下の辺で分ける方法を提案し、一度は解けた気になりましたが、後から間違っていることに気づきました。

このあたりでHが一旦書きあがり、バグった状態のコードが共有されました。

サイズ1の強連結成分の間に張られた辺をひっくり返さないような場合分けが入っていました。ひっくり返してしまうと元の向きに移動できないからとのことです。聞いた瞬間は確かになと思ったものの、よく考えるとその周りが残っていれば変わらず移動可能のはず。なのでその場合分けを抜いてもらいました。

ほかにもいくつか修正してもらい、サンプルが合ったところで提出。無事通りました。

I問題のACまで

I問題の実装に入りました。一度書いたことがあるコードなのですぐ書きあがり、サンプルも即座に合ってそのまま通りました。

C問題のACまで

上で紹介した二部グラフの分け方は、例えば辺を1本足して隣り合う頂点の次数を同時に変えるケースで壊れます。そこでグリッドの辺上の点を一周ぐるっと列挙して、source側とsink側に交互に振り分ければよいのではないかと思いつきました。

いくつかのケースを試してみてよさそうだったので、これで実装に入ってもらうことにしました。ホスフィンさんが担当することになりました。最小費用流の写経が必要でかなり大変です。

その間に考察を進めます。Lが解かれていたので考えました。まず、頂点の対応が1組わかっていれば木dpで解けそうです。

肝心の対応ですが、根を取り換えながら根付き木の同型判定を行うことでvalidなものを数えられます。先ほどの木dpも部分木同士の同型判定が必要なので、その結果を再利用できそうでちょっと嬉しくなりました。

根付き木の同型判定はハッシュを使うはずでしたが、どうするか覚えていません。仕方なく括弧列を使う方法をロリハで書くことを提案しました。頑張れば全方位木dpにもできるはずなので、根の取り換えが行えます。以上で理論的には解けました。

Cの写経が難航しているようなので、見て口出ししたり部屋をうろうろしたりしていました。この時点では、残り2時間以上あるのでC・Lを通してもう一問いけるかもなあと思っていました。

Eを考えてみることにしました。2-SATからSCCに帰着してもあまり嬉しくはなさそうなので、そのまま取り扱ってみます。clauseに関する条件から直前二つの変数の状態を持てばdpできます。

ここで、これまでいくつの変数を真にしたかを多項式で持ってみることにしました。するとdpの遷移が多項式の行列になります。特にどの多項式も高々1次なので、セグ木のようにマージしていけば $O(N(\log N)^2)$ です。

実際はここに行列積ぶんの定数倍が掛かりますが、TL 8secなのでこれで解けているものと考えました。実は全然ダメだったということを後から説明します。

Cは最小費用流の写経が終わり、いよいよ本題のアルゴリズムに入ったようでした。sourceとsinkに分ける部分で少し手が止まったのを見て、我慢できず実装を奪い取り、そのまま書き終えました。

しばらくデバッグし、サンプルが合ったところで提出。しかしTLEでした。間違いを見つけるのは任せて別の問題の実装に入るか悩みましたが、そのままPCにかじりついて自分でデバッグすることにしました。

dijkstraのpriority_queueが逆になっていたのと一部オーバーフローしていたのを直すと無事通りましたが、さらにWAを一つ出してしまいました。

コンテスト終了まで

残り1時間ちょっとあって、解けたと思われる問題がEとLです。Eのほうがすぐ終わりそうに見えたし、AC数が少なくて見栄えするだろうと思って取り組みました。

ところで、先ほどの解法はdpの遷移を要素が多項式の行列で表すというものでした。dpは4状態あるので行列のサイズは $4\times 4$ であるべきです。

ここを $2\times 2$ だと思い込んでいて間に合うと主張したのですが、行列積ぶんの定数倍がさらに8倍になるとかなり話が変わってきます。このことにNTTの写経を含めた実装を終えてから気づいたため、大変なことになってしまいました。

積の順番を勘違いしたりしつつ残り20分くらいで何とかサンプルが合いました。しかし提出するとTLE。 $O(N(\log N)^2)$ に定数倍64がつくとさすがに無理らしいです。手元で18sec程度だったので高速なNTTを使えば通る可能性はありそうですが、書き直す時間がありません。

最後の時間は、clauseを書き換えてインデックスの差を1以下にできないか考えていました。

振り返り

6完14位です。最後にEではなくLに取り組んでいればもしかしたら通っていたのかもしれませんが、実際に書いてはいないので何とも言えません。

自分がEと格闘している間にhaさんがKの考察をされていたらしく、ロリハでどこまで一致するか探索する方法を教えてもらいました。実装は相変わらず困難なものの、解法としてはかなりよさそうでした。

Dは $\log$ を付けてTLEしてしまい定数倍高速化に苦労した人をTLで観測しました。BITを採用したのはかなり良い判断だったようです。

今日はDでBIT、HでSCC、Cで最小費用流を写経してもらいましたが、解説スライドを読むとどの問題もそれらを使わない解法があるようでした。解けて満足するのではなく、フルスクラッチしやすい方針も考えてみるべきでしょう。

この辺りはICPCのオンライン開催が続いて全く意識しなくなってしまった部分です。C問題の実装が自分が思っていたより難航しているのに焦れてしまったのは反省すべき点でした。

今日はホスフィンさんが3問、haさんが2問、僕が1問実装しました。いつも一人だけ実装してばかりなので、これを他の人に割り振れたのは良かったのではないかと思います。

自分が考察を止めて実装に参加するべきタイミングがいつなのかはわかりませんでした。US配列を使い慣れておらず、他の二人とそれほど実装速度に差があるとも思えないため、今日くらい遅くてもいいのかもしれません。とりあえず写経は~~押し付けて~~任せてしまいたい気持ちがあります。