第五回 アルゴリズム実技検定

• アーカイブ
• 提出

リアルタイム受験した。4時間15分で全完。

J - 長い長い文字列

各操作で文字列の長さがどうなるかは先頭からシミュレーションすればわかるので、事前に求めておく。（大きな数になりえるので、適当に上限を決めて$\min$を取る。）

$i$番目の操作で長さが$L_i$になるとする。列$(L_i)$で$X$以上である最小の位置$i$を求めて、その位置にアルファベットがあればそれが答えである。数字の場合は、この操作を行う前の長さを$l$とするとき、$X$文字目は$(X-1) \% l$文字目と一致しているはずである。したがって、$X := (X-1) \% l$として同じことを繰り返せばよい。ただし、$0$文字目は$l$文字目と考える。

L - T消し

TDPCのiwiを思い出して見に行ったらそのものだった。

M - 棒の出荷

最小値を決め打って判定問題を解く。$\operatorname{dp}[x] :=$位置$x$で区切れるならtrue、不可能ならfalseというDPを考えると、適当な区間$[l(x), r(x))$について$\operatorname{dp}[x] = \operatorname{dp}[l(x)] \lor \operatorname{dp}[l(x)+1] \lor ... \lor \operatorname{dp}[r(x)-1]$という遷移になる。コンテスト中はすぐにセグ木を貼ったが、累積和上でDPするとか、（$[l[x], r[x])$は$x$について単調なので）スライドさせながらDPするとか、なんでもできそう。

O - 通知

愚直に処理すると、次数の大きい頂点が何回も更新されるときに困るが、次数の大きい頂点はそんなに多くなりえないことに注目する。閾値$D$を決めてそれより次数の大きい頂点とそうでない頂点をわけて処理してみる。以下、次数が$D$より大きい頂点をlarge node、小さい頂点をsmall nodeと呼ぶことにする。

通知クエリを処理するとき、small nodeからは周囲に愚直に通知を送り（small nodeなので送るべき頂点は多くない）、large nodeからは送らずに自身にためておいて、消化クエリが来た時に受け取る側から読みに行きたい（large nodeは多くないので毎回全部調べてもよい）。そこで、3つの配列を管理する:

• $\operatorname{unread}[x] :=$ small nodeから$x$に送られた通知で未読のものの総数
• $\operatorname{send}[x] :=$ large nodeである$x$が周囲に送った通知の総数
• $\operatorname{read}[x][y] :=$ 頂点$x$ がlarge node $y$から受け取った通知で既読のものの総数。

具体的な処理は次のようになる:

• $x$に対する通知クエリ
  • $x$がsmall nodeなら、$x$に接続しているすべての頂点$y$について、$\operatorname{unread}[y] \mathrm{+}{=} 1$する。
  • $x$がlarge nodeなら、$\operatorname{send}[x] \mathrm{+}{=} 1$する。
• $x$に対する消化クエリ
  • small nodeからの通知の総数を得る: $\operatorname{unread}[x]$を読んだあと、$0$にリセットする
  • large nodeからの通知の総数を得る: $x$に接続しているすべてのlarge node $y$について、$\operatorname{send}[y]$から既読の通知の総数$\operatorname{read}[x][y]$を引いたものの総和を取る。$\operatorname{read}[x][y] := \operatorname{send}[y]$として、既読を更新しておくこと。

計算量について考える。辺が1つ増えると全体の次数が2増えるので、次数の総和は$2M$である。したがって、次数$B$以上の頂点、つまりlarge nodeは、高々$2M/B$個しかない。クエリあたりの計算量は以下のように評価できる:

• $v$に対する通知クエリ
  • $v$がsmall nodeなら$O(D)$
  • $v$がlarge nodeなら$O(1)$
• $v$に対する消化クエリ
  • small nodeからの通知の合計を得るのは${O}(1)$
  • large nodeからの通知の合計を得るのは${O}(M/D)$

結局、全体の計算量は${O}(N+M+Q(D+M/D))$と書けて、$D= \sqrt M$なら${O}(N+M+Q\sqrt M$)。

解説の実装は$\operatorname{read}[x][y]$を頂点$x$がlarge nodeから今までに受け取った通知の数の合計として一次元配列にまとめていた。確かにそれでよかった。

CodeChef - Counting Strings

• 問題
• FFT
• 累積和

問題: 与えられた文字列$s$について、左から比較しても右から比較しても辞書順で大きい文字列$t$を数える。

$t$の構成を考えると、2つの位置$i, j (i \le j)$を境界にして、以下のように左から順に5つの部分に分解できる。（2番目と4番目は1文字）

• $s$と完全一致
• $s[i] < t[i]$
• 文字自由
• $s[j] < t[j]$
• $s$と完全一致

$N := |s|$とし、0-basedで考える。$f(i) :=$ 文字$s[i]$より大きい文字の数（$s[i] = \operatorname{a}$なら$f(i)=25$）とすると、$i, j$が異なる場合の数え上げは$\sum_{i < j} f(i)f(j)26^{j-i-1}$である。あとは$i, j$が一致する場合、つまり$s$と$t$がちょうど1字異なる場合を別に数えて$f(0)+...+f(N-1)$を足す。

上の式を見ると、畳み込める形になっている。$g(x) = f(N-x-1)$として一方の添え字を逆順にすると、$26^{N-2}\sum_{i+j \le N-2} f(i)g(j) (1/26)^{i+j}$と変形できて、$f$と$g$をFFTで畳み込んだ後で$1/26$を掛けながら加算すればよい。$\bmod$は$10^9+7$だが、登場する数が十分に小さい（高々$25^2 \cdot 10^5$）ので$998244353$でやっても問題ない。

---

よく見ると、変形して累積和を取るだけだった。

$$ \sum_{i < j} f(i)f(j)26^{j-i-1} = \frac{1}{26}\sum_{i=0}^{N-1} \biggl( \frac {f(i)}{26^i} \sum_{j = i+1}^{N-1}{f(j)}26^j \biggr ) $$

形を見て畳み込みできそうと思えるのは悪くないとしても、変数を分離できないかまず考えるほうがさすがによい気がする。

CodeChef - Two Closest

• 問題
• AC

問題: 無向グラフ$G=(V, E)$と$V$の部分集合$S$ (special node)が与えられる。$S$上の任意の2点間の距離で最短のものを求めよ。

方針: すべてのspecial nodeから各点への最短距離を調べるために$K$回ダイクストラする。この際、距離のテーブルは毎回使いまわしてよくて、枝刈りができる。また、special nodeを調べる順番をシャッフルすれば期待計算量が保証できる。

正当性について。今、special node $A_1, ..., A_{i-1}$について二頂点間の最短距離の最小値が求まっているとし、距離のテーブル$d$が$d[v] := v$と$A_1, ..., A_{i-1}$との最短距離の最小値、という状態になっているとする。ここからさらにspecial node $A_i$を始点にダイクストラするとする。この際、頂点$u$から$v$を更新しようとした時に$d[u] + w(u, v) \ge d[v]$であれば、$v$は無視してよい。なぜなら$A_i$から任意の頂点$x$に到達する際の最短経路が$v$を通るとしても、それ以下の距離で$A_1, ..., A_{i-1}$のいずれかから$x$に到達できることになるからだ。

計算量について。$K$回ダイクストラをしている間に頂点$v$がキューからポップされる回数の期待値を考える。$v$がキューからポップされるのは、今調べているspecial nodeと$v$の最短距離が以前調べたすべてのspecial nodeと$v$の最短距離より小さい場合である。したがって、この期待値は$K$個のspecial nodeと$v$との最短距離を$d_1, ..., d_K$とした時、$(d_i)$をシャッフルした列のLDSの長さの期待値に等しく、${O}(\sqrt K)$らしい^[1]。したがって、ポップに関する期待計算量は${O}(\sqrt KN \log N)$となる。また、ポップした頂点の隣接頂点を調べてdecrease keyする操作の期待計算量は、二分ヒープなら${O}(\sqrt KM \log N)$となる。 したがって、全体の期待計算量は${O}(\sqrt K (M+N)\log N)$ということになる。

waterfallsさんの別の乱択の方針も面白かった。special nodeをランダムに2分割して、一方を始点としたダイクストラをすると、最短距離を与える二頂点が異なるグループに属している時に正しい答えが出る。そうなる確率は1/2なので、何回もやって最小値を取ればよい。このテクニックは無向グラフの最短閉路アルゴリズムで見たことがある: http://research.haifa.ac.il/~raphy/papers/all-cycles.pdf

---

1. この評価については https://www.math.ucdavis.edu/~romik/book/ のp.9に簡潔な証明が載っている。ランダム順列のLISの長さの期待値に関する研究はJ. M. Hammersley, A few seedlings of researchが初出らしい。（後者は読んでいない） ↩︎

JOI2019 本選 C - たのしいたのしいたのしい家庭菜園

• 問題
• AC

左から列を作っていくとして、次にR, G, Yを隣に置くためにはまだ使っていないものの中で一番近いものを持ってくればよい。今までにR, G, Yをそれぞれ何個使ったか保持していれば一番近いR, G, Yがどこにあるかは決まるので、$\operatorname{dp}[x][y][z][c] :=$Rを$x$個、Gを$y$個、Yを$z$個使っていて直前に置いた色が$c$である場合の最小コスト、というDPが${O}(N^3)$でできるはず……だが、それ以降のほうが難しかった。

例えば$\operatorname{dp}[x][y][z][c]$から次にGを隣に持ってきて$\operatorname{dp}[x][y+1][z][G]$に遷移するとき、何回スワップが必要か数える必要があるのだが、どうやって数えるかでしばらく悩んでいた。結論から言えば

1. $\max(0, 次のGの位置以前にあるRの総数 - x)$
2. $\max(0, 次のGの位置以前にあるYの総数-z)$

の和が間にあるG, Yの総数に等しく、これが必要なスワップの総数に等しい。

HTTF2021 決勝 - マイニング

• 問題
• 提出

入力の作り方を見る限り、鉱脈はある程度まとまっているので、鉱脈を連結成分として表現して、連結成分とその間のパスを効率よく取っていくとよさそう……だが言うは易しという感じの方針なので具体的にどう実装するかで悩み続けた。

• 鉱脈を構成する点を判別していくつかの連結成分にわける
  • 定数$\alpha$を決めて、$p_{ij}-C/\alpha \ge 0$である点$(i, j)$を鉱脈を構成する点と考える。鉱脈を構成する二点で隣接しているものをUnionFindでつなぐ。コスト$C/2$で取れる点がある程度あることを考慮に入れようとして$\alpha = 1.5$くらいで始めたが、最終的には$1.05$になった。後から考えると、これは$1$で問題なかったと思う。
  • 連結成分はだいたい100個前後になる。
• 2つの連結成分間の距離を求めておく
  • ある連結成分を始点とした場合の、グリッド上の各点への最短距離はダイクストラで求まるので、全連結成分間の距離をあらかじめ求めておく。連結成分は100個程度なので、100回程度ダイクストラすればよい。
  • 「グリッドの外周」もひとつの連結成分とみなして最短距離を求めておく。
  • ダイクストラをする際、鉱脈を構成する点は通れないことにしておく。こうしないと鉱脈を突っ切って別に鉱脈に行ったほうが得という場合にコストの推定を間違えてしまうし、そもそも負辺を含んでいることになるのでダイクストラできない。通れないことにしたせいで連結成分$A$から$C$への移動が連結成分$B$に阻まれても別に問題ない。（次のパートで、必要なら$A$から$B$、$B$から$C$みたいな経路ができるはずなので。）
• MST+ 焼きなまし
  • 使う連結成分が決まっているとき、推定スコアは、連結成分中の$p_{ij} - C/\alpha$の総和から連結成分を頂点とする無向グラフ上のMSTの総コストを引いたものと考えられる。
  • 連結成分を使う/使わないで焼きなます。毎回クラスカルした。最初は単純に山登りしたが、焼きなましで多少スコアが上がった。
• 基本の採掘経路を求める
  • 使う連結成分が決まったので、「グリッドの外周」を表す連結成分を根としてMST上をDFSしながら採掘していく。隣接する連結成分へ移動するための具体的な経路は、上と同じようにダイクストラして復元すれば得られる。
    • 頂点を取る順番もスコアに関係しそうだと思ったけれど、つめられず。
• 貪欲で仕上げ
  • 既に採掘した点の隣接点でスコアが上がるものがあれば取る。
  • 既に採掘した点の隣接点とさらにその隣接点の2点を取ってスコアが上がるなら取る。
  • 以下、同様の貪欲を深さ4までやる。

267万点だった。

---

太字の部分に気づいて方針が決まるのに4時間、最初の提出までに6時間半かけてしまった。2～4時間のコンテストだと何もできずに終わってそう。

CS Academy Round #66 - Flipping Matrix

• 問題
• AC

操作を逆順に見る。単位行列の行や列を入れ換えていくと、次のことがわかる:

• 行と列の間に$1$による一対一対応があるという性質は交換で保たれる。（→ 置換行列）
• 任意の二行の交換はある二列の交換と同一操作であり、任意の二列の交換はある二行の交換と同一操作である。

逆に、初期配置から$1$を共通に含む行と列を1対1に対応させることができれば、この対応を1つの置換と考えることができ、互換を繰り返すことによって単位置換（＝単位行列）に戻せる。また、あらゆる置換は高々$N-1$個の互換の積で表せるので、$N$回以下という制限は問題にならない。結局、やることは次のようにまとまる:

1. $N \times N$の二部グラフ$G$をつくり、$A_{ij}=1$なら行に対応する頂点$i$から列に対応する頂点$j$に辺を張る。
2. $G$の最大二部マッチング$M$を求める。$M$が完全マッチングでなければ実行不能である。
3. $M$を一つの置換とみなして巡回置換に分解し、さらに互換に分解する。互換に従って行の交換を行う。

JOI2009 春合宿 - stamps

• 問題
• AC

とりあえず最短作業時間は単純なDPで求まりそう。$\operatorname{dp}[x][y] := S$を左から$x$文字作り済みで、次に使える文字がOである（$y=0$）あるいはIである（$y=1$）場合の最小操作数、として$\operatorname{dp}[N][0]$が求める値である。使える文字と次に作りたい文字が一致していればコスト0で次に遷移できるし、一致していなければ文字を変更または挿入してコスト1で遷移できる。

また、元のIOI文字列をできるだけ短くするためには挿入の回数を最大化すればよくて、これも同様のDPができるが、最短作業時間のほうが優先なので上のDPと同時にやる必要がある。

形式的には、1つのDPと捉えて、DP配列に入っている値を$(最短作業時間, 挿入回数)$として辞書式の大小関係を与えると考えると、わかりやすいかもしれない。