ICPC模擬地区予選 2021 参加記

2022/03/06に開催された模擬地区予選にチームAobayama_dropoutで参加しました。メンバーはゆきのんさん・ha15さん・僕です。

使用するユーザ名とパスワードが各チーム3組ずつ配布されましたが、これの割り当てについてはメールが届いた時点で決めていました。

うっかりコンテスト開始時間に起きてしまい、また考察共有用のHackMDを作るのにも手間取って10分くらい遅れて問題を読み始めました。

https://yokohama2021.jag-icpc.org/public

C問題

2人がA問題とB問題を読んでいるようだったので、C問題を読みました。置換してハミング距離の最小化ということで、i\rightarrow jという置換が選ばれたとき得点\#\{k\mid 1\le k\le N,\;A_k=i,\;B_k=j\}が得られると言い換えると、最大重み完全マッチングになります。これは負辺ありの最小費用流で解けます。負辺ありで負閉路なしということで、最初のポテンシャル計算を手動で行えばあとは普通の最小費用流で解け、計算量はO(M^3\log M)になります。先頭要素から順番に固定していくとこの計算をO(M^2)回行うことになりますが、定数倍としてちょっと減ることもあり通ると思えました。実装してAC、29分でした。

H問題

僕がC問題を通すちょっと前に立て続けにA問題とB問題が通っていて、その後2人はそれぞれG問題とI問題に移ったようでした。自分も順位表を見てH問題に行きました。Short codeという単語が見えて興奮しましたが問題自体はほぼ自明で、入次数が0の頂点を全部選べば十分に見えます。ただ書いているうちにループが存在しうることに気づいたので、いったんSCCを計算して、その上で入次数を見るコードを書きました。36分時点で通りました。

J問題

グラフの同型性判定まで読んだところで検索すると、WikipediaにPであるかわかっていない問題と書いてあって絶望しました。しかし問題文をよく読むとグラフがN頂点N辺の連結グラフ、いわゆるなもりグラフだったので、とりあえずループが確定することがわかりました。ループの各頂点からは木が生えていて、ループを適当に回したり反転したりして、これらの木を全部一致させられれば答えがYesになります。

まず（根つき）木の同型性判定ですが、これは括弧列にしたりハッシュ値を計算したりする方法があります。括弧列は下手な実装をすると文字列長の総和がO(N^2)になりそうなので敬遠して、ハッシュ値を求めることにしました。念のため法を2つ用意してハッシュを計算するクラスを作りました。

snuke.hatenablog.com

さて、あとはこのハッシュ値の列を一致させる問題です。ループを反転しなければならないケースは実際に反転して考えればよいので、ループを回して一致させられるかのみチェックすればよいことになります。ハッシュ値が同じインデックスをmapで集めて云々というコードを書いていましたが、しばらくして正気に戻って、片方を2倍してZ-algorithmを適用するコードを書きました。これも1発で通って、時間は72分でした。

D問題（とI問題）

Iが詰まっていたので問題を読み、Hの昇順に見るとSN状態のdpで解けることを指摘しました。順位表を見て、より多く解かれていたD問題に進みました。

クイズが人aに回答され、pポイント付与されたタイミングでのコインの枚数の変動を観察します。回答前、人iがポイントP_iを持っていたとすると、p\ge 0のときP_a\le P_i\lt P_a+pを満たす人i（i\ne a）の持つコインが1枚増えます。p\lt 0の場合もほぼ同じです。それらと人aを除けば、ほかにコインの枚数が変動する人はいないようですから、人を持っているポイントでソートできればコインの枚数の変動は区間加算（・1点更新）で管理できます。

これは可能です。具体的には、(P_i,i)という組を各クイズのタイミングで考えると、全体でも高々N+Q種類しかありえませんから、全部列挙してセグメント木のインデックスとして使うことができます。先ほども述べたように、区間加算と1点更新、1点取得が行えるセグメント木を用意して、ポイントの変動によって人の位置を動かしつつ処理します。クイズの回答者については、ポイントごとの人数を管理するBITがあればコインの枚数の変動が求まります。

実装は微妙に大変で、118分時点でACしました。

K問題

順位表ではK問題が解かれていて、考察もすでにG問題とI問題を通した他の2人がしてくれていました。人のペアを全部試すことができて、選んだ2人が距離D以内にいる時間というのは高々1つの区間で表せるようです。この区間の計算には2次方程式の解を求める必要があって、よく桁落ち誤差を問う問題で出題される七面倒な場合分けになります。HackMD上でその場合分けを詰めた後、実装すると一方的に宣言して書き始めました。区間さえわかってしまえば感染拡大の様子のシミュレートはdijkstraで行えます。144分時点でACしました。

F問題（解けず）

残りはE問題とF問題です。E問題が全完阻止幾何に見えてしまったので、F問題を考えることにしました。

とりあえず更新がない場合を考えます。よく見ると文字列の先頭に)を追加したり末尾に(を追加したり、とにかくこの2種類の操作は直感的に嬉しくないので、どうせ必要最低限しか行わないだろうと思いました。実際この2つの操作を余計に行ったとき)...(という文字列になりますが、両端の文字を移動させて...)...(...の状態にするくらいならしないほうがマシですし、...(...)...まで持っていくとしたらその間の)(をすべてswapするほうが安上がりです。

あとは、)(を()にswapするのが何回必要かを数えればよいです。いくつか方法を考えましたが、どれも括弧を\pm 1に変換したときの累積和の値があるボーダーラインより下になっている位置しか計算に含めないという場合分けを行う必要があり、セグメント木の区間更新には対応できませんでした。ところが、平方分割なら対応できることに気づきました。累積和の値に応じて集めておいたデータのマージが難しい一方で、結局計算に必要なのは集めてきたデータのうちただ一点であるからです。

より具体的な方法を述べます。(と)の数が一致している文字列を考えます。(という括弧は+1に変換されますが、この直前の累積和の値をsとしたとき、答えに\max(-s,0)だけ足すという計算で正しい値が求まるらしいことが実験からわかりました。実際には(と)の数には差があるため、それを均すために追加する括弧の分や、また平方分割している以上それまでのブロックのぶんも考慮する必要があるので、累積和の値は全体的に増減します。ここでtだけ減るとした場合、\max(t-s,0)の和を求めることになりますが、前計算でs\le tなる位置におけるsの和S_tとその個数c_tを求めておけば、c_tt-S_tとして計算することができます。全体をflipした場合の値も同様に前計算しておけば十分です。

これを実装しました。まずmapを用いて、出現した各sに対してS_sとc_sを求め、取得には二分探索を用いましたが、TLEしました。手元で作ったランダムケースでは5秒弱かかっていました。次に、mapの代わりにソートしたvectorを使って、取得は同様に二分探索で行うようにしました。さらに入出力高速化などを行い、平方分割のバケットサイズBについてもいろいろ弄ってみて、B=100にするのが最も高速になったのでそれを採用しました。これらの高速化によって、同じランダムケースで1秒となかなか高速に計算できるようになりましたが、同じくTLEしてしまいました。都合5回提出したもののすべてTLEとなり、そのままコンテストが終了しました。

コンテスト後

9完8位でした。9完内では2位ですが、それは上位陣が10完以上していったからで、9完までのペナルティ的にもかなり負けてしまいました。少なくとも自分が担当した問題では詰まった感触がなく、なぜこうも速度で負けているのか一瞬不思議に思いましたが、どう考えても最初10分くらいのんびりしていたからで、この時点でのタイムロスが全体に響くことを強く実感しました。

F問題の平方分割は方針として合っていたようです。足りなかった考察はsの取りうる値についてで、sはブロック内における累積和の値なので、必ず-B\le s\le Bを満たします。つまり、mapやvectorを用いずとも長さ2B+1の配列で値を保持することができ、この場合取得に二分探索が必要なくなります。更新時も含めて計算量から\logが消え、実装してみたところランダムケースの計算が0.5秒で終了しました。まだ提出できていないので、そもそもコードの正当性も確かめられていませんが、なかなか惜しかったと感じています。こういう崖の先の一問を解けるようにならない限り、世界大会はないでしょう。