CS Academy - Necromancer

• 問題
• AC

複雑な設定だが、考えるべきは各投票者がどの候補者をトップ（一番目）にした可能性があるか、だけである。

与えられた投票者$A$について、$A$の投票した候補者の部分列が$q_1, q_2, ..., q_l$であるとわかっているとする。ネクロマンサーの投票操作を最小で済ませるためには、候補者$1$にとって最善のケースを考えるべきである。$q_1 = 1$なら$A$は候補者$1$をトップにしたと考えれば良いし、$q_1, q_2, ..., q_l$に候補者$1$が含まれていない場合もやはり候補者$1$をトップにしたと考えてよい。その他の場合、つまり部分列の中に$1$が含まれているが最初ではない場合、$A$は$1$以外の候補をトップにしたことになる。$l = K$ならそれは$q_1$だし、$l \neq K$なら$q_2, ..., q_l$以外のいずれかの候補である。

さて、$1$以外に投票したことがわかっている候補者については、投票先を$2, 3, ..., K$にばらけさせて、得票数の最大値ができるだけ小さくなるようにしたい。その最小値がわかれば、ネクロマンサーはそれを超えるように候補者$1$の得票を増やせばよい。これは二分探索とフローで実現できる。つまり、得票数の最大値がある値$D$以下にできるかどうかを最大フローで判定すればよい。

グラフの作り方としては、始点$S$を（投票先が1以外の）各投票者と容量$1$の辺でつなぎ、投票者をありえる投票先に容量$1$の辺でつなぎ、（1以外の）各候補者と終点$T$を容量$D$の辺でつなげばよい。

サンプルのケースでは次のようなグラフになる:

3人の投票者$v_1, v_2, v_3$について、4人の候補者$p_1, p_2, p_3, p_4$の中からありえる投票先につないでいる。何も書かれていない辺の容量は$1$である。候補者$1$は常に無視してよいし、投票者$3$も候補者$1$に投票しているとみなせるので無視してよいが、便宜上、図に書いている。
このグラフに流量$2$（$=S$から出ている辺の容量の合計）のフローが流せれば、得票数の最大値が$D$以下にできることがわかるので、二分探索で境界を探せば良い。

ARC 071 E - TrBBnsformBBtion

• 問題
• AC

まずは操作が可逆かどうか考えてみる。操作1は逆操作が可能である:

• BB → AAB → AAAA → A
• AA → BAA → BBBB → B

操作2は、文字列が空でない限り逆操作が可能である:

• A → BB → AAB → ABBB
• A → BB → BAA → BBBA
• B → AA → BBA → BAAA
• B → AA → ABB → AAAB

したがって、文字列の集合はいくつかの同値類に分割できそうと思える。そこで、それらをもっとも短い文字列で代表させることを考える。

• AB → AAA → 空
• BA → BBB → 空
• AA → B
• BB → A

に従うと、長さ2以上の文字列は必ず短くできる。つまり、任意の文字列は、できるだけ短い文字列に変換するとA, B, 空のいずれかになり、文字列の集合が3つの同値類に分割できるとわかる。¹

3つの同値類をそれぞれ$A, B, O$で表すことにして、文字をつなげる操作を$+$で表すと、演算の性質は以下のようになっている。

$A+B = B+A = O \\ A+A = B \\ B+B =A \\ A + O = O + A = A \\ B + O = O + B = B$

これは${\mathbb Z}/3{\mathbb Z}$と同型なので、$\mod 3$で文字列$S$と$T$の累積和を取っておけば、クエリには${\mathcal O}(1)$で答えられる。²

---

1. 文字列 $a$ → 空 → 文字列 $b$という変換は不可能なのが気になるが、空になる直前は必ずAAAかBBBのどちらかになっていて、AAA → BBBBBB → BBBとその逆の変換が可能なので問題ない。 ↩︎

2. 上では、そもそも文字列A, Bと空の文字列は本当に相互変換できないのか確かめていなかった。しかし、考察をここまで進めると、文字Aを$1$、文字Bを$2$として$\mod 3$で和を見れば、2種類の変換の前後で総和が変化しないことがわかり、それが証明になっている。 ↩︎

ARC 006 D - アルファベット探し

• 問題
• AC

chokudaiさんのツイートより。簡単な方針を思いつけなかった……

「文字を囲む正方形」の一辺の長さが常に$5$の倍数になることを利用する。黒マス$(i, j)$が与えられたとき、$(i, j)$を基点に黒マスだけを8方向にたどるBFSをして、連結成分の上下左右の境界$U, D, L, R$を突き止める。$D-U+1 = 5k$とすると拡大率が$k$倍とわかるので、領域$[U, D] \times [L, R]$を左上$(U, L)$を基準に$1/k$倍に縮小する。

各点に対して上の処理を行うと、図上の文字はすべて等倍になる。あとは、図上のすべての$7\times7$の正方形について、$3$文字$\times 4$方向 $= 12$パターンのいずれかに一致するか調べればよい。これは例えばローリングハッシュなどでできる。¹ 計算量は${\mathcal O}(HW)$。

---

連結成分のサイズだけ見ればよいかもというのは最初に考えたけれど、倍数では文字を1つに絞れないと思ってすぐに捨ててしまった。（実際には、文字を$k$倍に拡大すると連結成分のサイズが$k^2$倍になるので、異なる文字のサイズが重なることはない。）

---

1. プログラミングコンテストチャレンジブック 第2版, pp.333-335より。でも、よく考えると等倍に戻したタイミングで愚直にパターンマッチすれば十分だった。 ↩︎

AGC 033 D - Complexity

• 問題
• AC

$f(y_1, x_1, y_2, x_2) :=$ 矩形$[y_1, y_2) \times [x_1, x_2)$の複雑度

とすれば自明な漸化式が導けるが、時間的にも空間的にも間に合っていない。そこで、次の点に注目する:

• 複雑度は高々$\lceil \log_2(HW) \rceil = 16$と小さい
• $x_2$や$y_2$が増加すると複雑度は単調に増加する

したがって、ナップサックDPのように値と変数を入れ替えたDPができる。具体的には

$f(y_1, x_1, y_2, c) :=$ $[y_1, y_2) \times [x_1, X)$の複雑度が$c$以下になるような最大の$X$
$g(y_1, x_1, x_2, c) :=$ $[y_1, Y) \times [x_1, x_2)$の複雑度が$c$以下になるような最大の$Y$

としてDPする。$f(y_1, x_1, y_2, c)$の漸化式を与える。左右に分割する場合に限った$X$の最大値は、複雑度$c-1$以下の2つの横に並んだ矩形についてできるだけ横幅の合計を大きくすることで達成できるので

$f(y_1, f(y_1, x_1, y_2, c-1), y_2, c-1)$

また、上下に分割する場合の$X$の最大値は、複雑度$c-1$以下の2つの縦に並んだ矩形を、高さの合計が$y_2$以上になるようにするという条件でできるだけ横幅を大きくすることで達成できるので

$\argmax_X \bigl( g(g(y_1, x_1, X, c-1), x_1, X, c-1) \ge y_2\bigr)$

となり、この2つのうちの大きいほうが$f(y_1, x_1, y_2, c)$である。（後者は二分探索で得られる。） 同様に、$g(y_1, x_1, x_2, c)$は

$g(g(y_1, x_1, x_2, c-1), x_1, x_2, c-1))$

$\argmax_Y \bigl( f(y_1, f(y_1, x_1, Y, c-1), Y, c-1) \ge x_2 \bigr)$

の大きいほうに等しい。

$\alpha := \max (H, W)$とするとき、計算量は${\mathcal O}(\alpha^3 \log^2 \alpha)$。かなり厳しそうだが、TLが5秒なのでメモ化で一応通った。想定はボトムアップのDPで尺取り法っぽくやって${\mathcal O}(\alpha^3 \log \alpha)$らしい。

参考:
http://drken1215.hatenablog.com/entry/2019/05/10/215400