2023/03/08-2023/03/15に開催されたHello Muscat 2023という競プロのキャンプにオンライン参加した。チームは自分、かっつさん（_KKT89）、ぷらさん（Pura_prime）。以下は言及禁止のため日記に書けなかった分である。

不参加の日や回避した日は日本から出ていた他の2チームとCFのgymで別の5hを走っていた。そちらについては日記に書いてある。また03/11は中休みだった。

Day 1: JAGain in Petrozavodsk（03/08）

2021年のICPC模擬地区予選にOUPC2022Hが足されたセットだった。不参加。

Day 2: GP of ainta（03/09）

今日はかっつさんと二人で、さらに午後6時半からCF div.1があったため最初3時間半のみの参加となった。

結果はAGJBEIの6完。自分はAJBEを解いた。

Aはパッと見難しそうでいったん飛ばしたが、FAが速かったのを見て慌てて戻ってきた。異なる色のマスが隣り合っていればどちらも操作されたことがないとわかる。逆にそうでないマスは最初白黒どちらでもよいため、1マスにつき自由度2がある。その積が答え。

Gはかっつさんがササッと通していた。

Jはほぼエスパー。同じクラスの生徒を両端から組み合わせることでペアを作り、左から順に取り除くのをシミュレートしたら通った。

Bは $A\rightarrow B$ という辺を張って強連結成分分解した。入次数が0でない強連結成分については辺が入ってきた頂点から適当にDFS木を取るなりすれば構築可能なのでOK。よって入次数が0である強連結成分について考える。先ほどと同様の理由で、この中で長さ3以上のサイクルが作れればよい。

今見ているのは強連結成分だから、逆辺がない辺が存在すれば直ちに作れるとわかる。すべての辺が逆辺を持つなら辺と逆辺のペアを一つの無向辺に圧縮した上でループが存在すればよい。これは単に辺の数が頂点の数以上か見るだけでわかる。

ここからしばらく停滞。Iは2点連結成分が重要で、Block Cut Treeを構築してガチャガチャするとできることが判明した。実装したくなくてかっつさんのご機嫌を伺ったところなんと乗り気だったので、押し付けて別の問題に進んだ。するとEが解けた。

文字列が回文ならそれでよい。そうでない場合に、あらかじめ両端から一致している文字を削除して考える。削除した文字に対する答えはその隣の答えから計算できる。この操作で両端の文字が異なるようにできたので、左端または右端に必ず行く必要がある。reverseしつつ左端に行く場合を2回解くことで両方試す。

移動した区間の右端に着目し、それをインデックスとして遅延セグ木にコストを乗せることを考える。 $s$ の降順に計算し、毎回遅延セグ木の各値が $s$ スタートとしたときのコストになっていることを目標にする。

まず右端が $s$ の場合のコスト（これは簡単に求まる）をセグ木に乗せる。次に、右端が $s+1$ 以上の場合のコストが $s+1$ スタートになっているので、 $s$ スタートに更新する。差分は $+C,\pm 0,-C$ のどれかで、それぞれ区間になっているので区間ADDで処理できる。

最後に区間MINで $s$ に対する答えを求める。削除した文字に対する答えを求めるときに移動コストの係数 $C$ を忘れて1WA。

Eが通った20分くらい後にIも一発で通った。残り時間はDを謎の貪欲で解こうとしてWAを出し続けていた。

感想戦は行わなかったので考察メモから、Gについて。とりあえず全部操作2を行って黒くなったマスに対しては操作2の代わりに3を行ったことにすればよかったらしい。

Day 3: 2023 ICPC Asia Hong Kong Regional（03/10）

02/04のUniversal Cup 2回目、Hong Kongセットと同じだった。不参加。

Day 4: KAIST+KOI Contest, Grand Prix of Korea（03/12）

今日はぷらさんと自分の二人だった。結果はBDHJGMFの7完。自分はBDHGMを解いた。

Bは一つのクエリに対してはUFで答えられるので、必要な部分だけ毎回初期化しなおせばよい。ただし次数の大きな頂点ばかり指定されると使う辺の列挙が難しい……と考えていた。しかしここに気を遣うべきなのはグラフが一般の場合で、今は木なので簡単。例えば適当に根を取り親との辺だけ見れば十分。

BとDの間にぷらさんがMを提出していたがTLEだった。

Dはビル $L$ より左はどうにでもなるので右について考える。ビルの高さを降順に見ながら、右から遷移してくる貰うdpを書いた。dpの値に「遷移元と遷移先の間にあるこれまでに見たビルの数」を足したもの、の最小値が欲しい。

実はこれはセグ木に乗る。ノードに対し、そこにあるビルの数と、左端が遷移先だとしたときの最小値を持たせればよい。 $O(N\log N)$ の遷移を $K$ 回行うだけなので十分高速。

Hは手で試した感じ残り5個ほど空いていれば必ず埋められそうだったので、念のため7個空けることにして、そこまで貪欲、残りは全探索を行った。 $a$ が全部決まっているケースで壊れるのを見落とし1WA。後から5個空けるだけでちゃんと通ることも確認した。証明はしていない。

Jはリスの間隔から作った数列の上で操作を言い換えるまでがぷらさん、そこから添え字 $\bmod K$ で分解できること、分解した後のゲームが蟻本に載っていることを指摘したのが自分で、実装はぷらさんにお願いした。ちなみに蟻本第2版の278ページである。

Gは2時間くらいかかった。できるだけ長いパスを作るような木dpをする。管理するのは①根からのパス・②根からとは限らないパス・③端点の片方が決まっていないパス。これを二つマージする9通りのうち考えるべきなのが①①→②・①③→①・②③→②・③③→③とその左右逆の合わせて6通りだった。端点の両方が決まっていないパスを考えなくてよいのは、この三種類からは作れないため、ということのはず。

これらのパスを操作回数に対して管理する。マージは普通にやっても2乗の木dpになっている。しかしコンテスト中は気づかず、列が上に凸であることを信じてMax-Plus畳み込みを貼っていた。

Concave Max Plus Convolution | Library

時間がかかった原因はこれではなく、③を見落としていたから。以下のライブラリを使ってランダムな木を作り、木dpを行う際の根を全頂点で試して答えが一致するかチェックすることでHackケースを見つけ、手で計算して遷移が不十分だったことに気づいた。

GitHub - ouuan/Tree-Generator: Help competitive programming problem setters to generate different kinds of trees :evergreen_tree:

solved数を見てFに進んだら、二人とも書いた覚えのない問題概要がすでに書かれていた。どうやら用事の合間を縫ってかっつさんが書いてくださったものらしい。ぷらさんと二人であれこれ言っているうちに解けて、実装を任せた。バグり散らかしていて大変そうだった。自分も少しデバッグに参戦し、明らかにおかしい点を指摘していたが、コードの細部まで理解できていたわけではなかった。

Fが詰まっている合間に序盤でTLEしたきりのMに再挑戦した。問題は簡単に最小費用流で書き直せる。最初の提出では超頂点を結構な数用意してその分辺もたくさん使っていたので、いくらか削減した。結果的には部屋と辺に一つずつ頂点を置いてだいたい $3NM$ 個、辺は $9NM$ 本くらいになったはず。ACLを使ったら余裕を持って通った。実は最初の提出でもACLを使っていればギリギリ間に合ったらしい。

コンテスト終了間際にFのサンプルが合い、そのまま一発で通った。

感想戦。MとF以外は上に書いた。Mは最小費用流が間に合うことさえ信じられれば自明なのに全然通されなかったのがなんとも順位表マジックという感じ。実は今回は設定ミスか何かでゴーストが表示されず、このキャンプで走ったチームしか順位表にいなかったのだ。

Fの解法を説明する。桁のindexを上位にあるほど小さい番号が振られるものとする。まず $X$ と $Y$ で出現する数字が等しければ $Z=Y$ とできる。そうでない場合の $Z$ を考えると、どこかの桁 $i$ で $Z_i\gt Y_i$ となり、それより前では $Y$ と完全一致、それより後では残っている数字を昇順に並べたものとなる。よってこの $i$ の最大値と対応する $Z_i$ が求まればよい。

$Z_i$ を固定すると $i$ の上限が求まる。 $X$ に存在する数字 $d$ の個数を $c_d$ と置くと、 $Y$ における $c_d+[d\ne Z_i]$ 個目の $d$ の位置をBIT上の二分探索で求めることができる。そのような位置の最小値が上限である。 $Y$ でそこ以前にある $Z_i$ 未満の数字のうち最大の桁にあるものをset上またはBIT上の二分探索で見つけてくることができ、これが $i$ である。

Day 5: Gennady Korotkevich Contest 7（03/13）

Universal Cupで将来的に使われるらしい。回避。

Day 6: Harbour.Space + Um_nik Contest（03/14）

04/22のUniversal Cup 13回目、Iberiaセットで使われるらしい。回避。

Day 7: SPb SU LOUD Enough Contest 2（03/15）

今日は後半ぷらさんに用事があって二人だった。順位表にバグがあってコンテスト開始からしばらく5完と表示されていた。

結果はBの1完。とんでもない難易度のコンテストだった。Bの考察と実装はかっつさん。かなりやりたくない見た目をしているのに、これが唯一の人間向け枠だと見抜きいち早く取り組んでくれたことに感謝。

Bの問題文にはいろいろ複雑なことが書かれていたが、最適解に関するそれらしい条件を見つけるとかなり見通しが良くなったようだ。攻撃するときは座標 $\max(l-6,0)$ から立て続けに行うというもの。そうでない場合いかにも損しそうなのですぐ納得できる。

二分探索をしてはどうか？と呟いてみたところ見事に解けた。各攻撃地点についてそこまで行った後何発攻撃する余裕があるか求まって、地点の降順に何機必要になるかが計算できる。そこそこすんなり通っていた。

自分とぷらさんはJやDを考えていたがまったくわからなかった。ぷらさんが用事で離脱してからはEを考え、計算量的に怪しい解法が出せたので実装するもWAを取る時間すらなかった。

その後Eのupsolveをした。優勝させたい人を決め打ったらどのレースで誰を敗退させるかという完全マッチングの問題になる。ただし同時に指定できない組もある。ところがこの条件を無視して完全マッチングを見つけてしまいさえすれば、適切に組み替えることで必ず条件を満たすものを作れると分かった。

例えば、各レースについて「敗退させることになっている人」から「そのレースで一番遅い人」に向かって辺を張ってみる。もしループができてしまったらそのようなマッチングは条件を満たさないのだが、この場合ループに含まれる各レースの「敗退させることになっている人」を「そのレースで一番遅い人」に同時に置き換えることで、完全マッチングであることを保ったままループを解消できるのだ。

さらにこの部分では条件を満たすため、今のループに含まれるレースとそのマッチ先は確定させて良い。同様のことを二番目に遅い人、三番目に遅い人……と行っていくと、いずれ必ず全レースのマッチングが確定し、それが条件を満たす解となっている。

コンテスト中はこの時点で確定順に出力していたが、ランダムケースを試しているとそれではダメだということに気づいた。改めてトポロジカルソートする必要があるようだ。これを実装するとかなりのテストケースが通って、今度はTLEに悩まされるようになった。

TLE解消のメインアイディアは完全マッチングを流用すること。優勝させたい人を新しく決め打った際、マッチングを全部消して再計算するのではなく辺としてvalidなものは残しておくことでそこそこ高速になった。

加えて入出力高速化、memsetによる配列の初期化、vectorを一切使わずすべて生配列にすること、pragmaによる最適化などありとあらゆる高速化を詰め込んだら何とかTLの0.7secに収まった。いくつかはいらないと思うが、具体的にどれが効果がなかったかまで確かめるのは面倒。

kotatsugameの日記

Hello Muscat 2023 参加記