ARC 098 E - Range Minimum Queries

• 問題
• AC

数列$A_1, A_2,...$を昇順に並べ替えたものを$A'_1 \le A'_2 \le ...$とする。最大値-最小値をすべて試すなら、だいたい次のようになるはずだ。

1. 数列$(A_i)$の小さいほうから$Q$個取り除いて最大値-最小値を求める。
2. $A'_1$を残したままにしつつ$(A_i)$からできるだけ小さい数を取り除いてゆき、$Q$個取り除けたら最大値-最小値を求める。
3. $A'_1, A'_2$を残したままにしつつ$(A_i)$からできるだけ小さい数を取り除いてゆき、$Q$個取り除けたら最大値-最小値を求める。
4. …

これは高々${\mathcal O}(N)$ステップで済むので、ひとつひとつのステップが${\mathcal O}(N)$か${\mathcal O}(N \log N)$くらいで実行できればよい。

小さい数を取り除いていく具体的な手順を与えるために、上のステップ3について考えてみる。$A'_1 = A_p, A'_2 = A_q$とする。

$A_1, A_2, ..., A_{p-1} \ | \ A_{p+1}, A_{p+2}, ..., A_{q-1} \ | \ A_{q+1}, A_{q+2},..., A_N$

$A_p$, $A_q$を残したまま数を取り除いていくというのは、上の数列の縦線をまたがないように連続した$K$個を選んで、その最小値を除いていくということにほかならない。なぜなら$A_p, A_q$はほかの数より小さいので、縦線をまたぐと$A_p, A_q$が取り除かれてしまうからだ。つまり、$(A_i)$を複数の独立した数列に分割してそれぞれの最小値を見ればよさそうだ。

さて、「複数の独立した数列」をどう管理すればよいかが問題である。上の３つの部分列を${\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}$とする。これらの数列から小さい数を除いていくとき、数列の最小値と長さにしか興味がないので、${\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}$はそれぞれ（昇順の）優先度付きキューで表すことができる。さらに、${\mathcal A_1}, {\mathcal A_2}, {\mathcal A_3}$自身も優先度付きキュー${\mathcal Q}$にいれることにし、${\mathcal Q}$の順序は${\mathcal A} \le {\mathcal A}' : \Leftrightarrow$ ${\mathcal A}$の最小値$\le$${\mathcal A}'$の最小値 とする。

一般に、$l$個の部分列から$Q$個の数を取り除く操作を書き下すと、次のようになる。

• ${\mathcal A_1}, {\mathcal A_2}, ..., {\mathcal A_l}$の中で長さが$K$以上であるものだけ${\mathcal Q}$に入れて、残りは捨てる。
• 次のステップを最大$Q$回繰り返す。
  1. ${\mathcal Q}$の先頭から数列${\mathcal A}$を取り出す。
  2. ${\mathcal A}$の最小値を取り出す。
  3. ${\mathcal A}$の長さがまだ$K$以上なら${\mathcal Q}$に戻し、$K$未満なら捨てる。
• ${\mathcal Q}$が空になる前に$Q$個の数を取り出せたなら、その最大値-最小値を求める。

以上で答えが求まる。全体の計算量は${\mathcal O}(N^2 \log N)$。

---

問題を読んだときは$N$が小さいので何をやってもできそうな気がしたけど、具体的な手順を与えるのに膨大な時間をかけてしまった。

JAG Summer Camp 2015 Day 2 F - ほぼ周期文字列

• 問題
• AC

ローリングハッシュを使う。

文字列$s$とインデックス$x, y$が与えられたとき、$s$の接尾辞$s[x..]$と$s[y..]$のLCP（最長共通接頭辞）の長さを$\operatorname{LCP}(x, y)$とする。$s$の区間$[l, r)$が周期$t$の文字列であることは、$\operatorname{LCP}(l, l+t) \ge r-(l+t)$であることと同値である。まず、これが成り立てばYesを返してよい。

$\operatorname{LCP}(l, l+t) < r-(l+t)$の場合、文字$s[l+\operatorname{LCP}(l, l+t)]$と$s[l+t+\operatorname{LCP}(l, l+t)]$が異なっている。一方の文字をもう一方の文字に変更すれば周期$t$の文字列になる可能性がある。

これを確かめるためには、連続部分列$s[l .. r-t]$と$s[l+t .. r]$について、$s[l+\operatorname{LCP}(l, l+t)]$を$s[l+t+\operatorname{LCP}(l, l+t)]$に変えたもの（あるいはその逆）のハッシュ値が等しいか調べればよい。

---

ローリングハッシュを初めて使った。例題と聞いて手をつけたのでLCPを使う方針はすぐに浮かんだが、正しい実装に時間がかかった。以下はメモ。

• ローリングハッシュに偽陽性（異なる文字列に対して同じハッシュ値を返す）はあるが偽陰性（一致する文字列に対して異なるハッシュ値を返す）はないので、2つの文字列を複数modで比較してひとつでもハッシュ値が異なれば異なる文字列である。
• LCPの場合、偽陽性は真の値より長い区間をLCPと判定するという形で現れるので、複数modによる最小値をLCPの長さとして採用すればよい。

ARC 038 D - 有向グラフと数

• 問題
• AC

与えられたゲームと同じルールで、$X$点以上なら先手が勝ち$X$点未満なら後手が勝つゲームを$G(X)$とする。$G(X)$の勝敗が判定できれば、二分探索で答えが求まることになり、判定は後退解析で可能である。後退解析についてはdrkenさんの記事がわかりやすかった。

以下、メモ。

• ゲーム$G(X)$で勝負がつかない間、先手は常に$X$点未満の頂点を踏み、後手は常に$X$点以上の頂点を踏むため、偶数回で強制終了するなら後手勝ち、奇数回なら先手勝ちとなる。
• 後退解析は最初にキューにいれる頂点が重複すると正しく動かないので注意。

TDPC H - ナップザック

• 問題
• AC

0-basedで考える。また、$(w_i, v_i, c_i)$があらかじめ色の昇順にソートされているとする。$f(x, y, z)$を、物 $0, 1, ..., x-1$から$y$色以下、重さ$z$以下になるように選んで達成できる最大価値とすると、答えは$f(N, C, W)$である。

$f$の漸化式を考える。物$x$が色の先頭にない場合は普通のナップサック問題と同じように遷移する:

$f(0, y, z) = 0$ $f(x, y, z) = \max \begin{cases} f(x-1, y, z) & (\text{物$x-1$を入れない})\\ f(x-1, y, z-w_{x-1})+v_{x-1} & (\text{物$x-1$を入れる}) \\ \end{cases}$

物$x$がその色の先頭にある時は$x-1$から色が変わるため、新しい色を使う場合と使わない場合を比較しなければならない。$p(x)$を物$x$のひとつ前の色を持つ品物の先頭とすると、次のように書ける:

$f(x, y, z) = \max \begin{cases} f(x-1, y-1, z) & (\text{物$x-1$の色を使うが$x-1$は入れない})\\ f(x-1, y-1, z-w_{x-1})+v_{x-1} & (\text{物$x-1$の色を使い、$x-1$を入れる}) \\ f(p(x), y, z) & (\text{物$p(x)$, ..., $x-1$の色を飛ばす}) \end{cases}$

ただし、$y=0$のときはもう新しい色を使えないので$f(x,0,z) = f(p(x), 0, z)$である。計算量は${\mathcal O}(NWC)$。

---

以前に見たときは何がなんだかわからなかったが、今見たらあっさり解けた。ソートしてナップサックは典型らしい。