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

• アーカイブ
• 提出

リアルタイム受験した。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から今までに受け取った通知の数の合計として一次元配列にまとめていた。確かにそれでよかった。