AtCoder Regular Contest 181 B,C,D問題メモ

AtCoder Regular Contest 181

B - Annoying String Problem

• 英小文字からなる文字列 $S,T$ および 0, 1 からなる文字列 $X$ に対し、英小文字からなる文字列 $f(S,T,X)$ を以下のように定めます。
  • 空文字列に対し、 $i=1,2,\dots,|X|$ の順に、$X$ の $i$ 文字目が 0 なら $S$ を、 1 なら $T$ を末尾に結合することで得られる文字列
• 英小文字からなる文字列 $S$ および 0, 1 からなる文字列 $X,Y$ が与えられます。
• 英小文字からなる文字列 $T$ （空文字列でもよい）であって、 $f(S,T,X)=f(S,T,Y)$ が成り立つようなものが存在するか判定してください。
• $t$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

• $1 \leq t \leq 5 \times 10^5$
• $1 \leq |S| \leq 5\times 10^5$
• $1 \leq |X|,|Y| \leq 5\times 10^5$
• $S$ は英小文字からなる文字列
• $X,Y$ は 0, 1 からなる文字列
• $1$ つの入力に含まれるテストケースについて、 $|S|$ の総和は $5 \times 10^5$ 以下
• $1$ つの入力に含まれるテストケースについて、 $|X|$ の総和は $5 \times 10^5$ 以下
• $1$ つの入力に含まれるテストケースについて、 $|Y|$ の総和は $5 \times 10^5$ 以下

$X$ と $Y$ に出てくる0,1の個数を $C_{XS},C_{XT},C_{YS},C_{YT}$ とする。

$C_{XS}=C_{YS}$ の時は、$T$ を空文字列にすればよいので、存在すると即座に分かる。

$f(S,T,X)=f(S,T,Y)$ なら当然長さも等しくなることから、$|T|$ が一意に決まる。
$|S|C_{XS} + |T|C_{XT}=|S|C_{YS} + |T|C_{YT}$ が成り立ち、方程式を解くことで $|T|$ が求められる。
これが整数でなかったり、負になったりするとアウト。存在しないと即座に分かる。

以下、$|T|$ が整数で求まったとする。

次に $T$ の具体的な値を求めて一致を確認したい。
ただし、$|T|$ は最大 $|S| \times |X|$ になり得るため、愚直には求められない。

ひとまず、先頭から $X,Y$ の0,1が初めて異なるところを探し、そこの $T$ が満たすべき条件を考える。

[  S  ][  S  ][    ...
[       T       ][ ...
または
[       S       ][ ...
[  T  ][        S  ...

のようになっている。これが一致するので、長い方の先頭は短い方と一致している必要がある。

$T = S + T'$ として再帰的に考察していくと、 $T$ は「$S$ の $\lfloor \frac{|T|}{|S|} \rfloor$ 回の繰り返し + $S$ の先頭何文字か」 と表されなければならないことがわかる。

ローリングハッシュを使って $S,T$ のハッシュ値を求め、それを元に $f(S,T,X),f(S,T,Y)$ のハッシュ値を計算し、一致判定を行う。

$T$ のハッシュを求める際、$|T|$ が大きい場合は1文字ずつ計算してたらTLEとなるが、 その場合 $S$ の繰り返しであることが分かっているので、 先に $S$ のハッシュを求めておいて、一気に $|S|$ 文字分をずらしながら計算すれば、計算回数は $O(|X|+|Y|)$ で抑えられる。

その後、$hash(S),hash(T),X,Y$ を使って $f(S,T,X)$ と $f(S,T,Y)$ のハッシュを計算し、一致を確認すれば良い。

Python3

公式解説の方法。$|T|$ を求めるところまでは一緒。

ローリングハッシュを求めずとも、$S$ が $gcd(|S|,|T|)$ 文字単位の繰り返しであるかをチェックすれば良い。

ユークリッド互除法のように長い方を短い方でカットしていくと、最終的に $gcd(|S|,|T|)$ 文字が残る。
これが同じになる必要がある。

互除法を逆に辿って元の $S,T$ を復元すると、$S$ も $T$ も、共通する長さ $gcd(|S|,|T|)$ の文字列の繰り返しであることが必要十分とわかる。

C - Row and Column Order

• $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N), Q=(Q_1,Q_2,\dots,Q_N)$ が与えられます。
• $N$ 行 $N$ 列からなるマス目の各マスに文字 0, 1 のいずれかを書き込み、以下の条件がすべて成り立つようにしてください。
  • $i$ 行目のマスに書かれている文字を、 $1,2,\dots,N$ 列目の順につなげて得られる文字列を $S_i$ としたとき、辞書順で $S_{P_1} \lt S_{P_2} \lt \dots \lt S_{P_N}$ が成り立つ
  • $i$ 列目のマスに書かれている文字を、 $1,2,\dots,N$ 行目の順につなげて得られる文字列を $T_i$ としたとき、辞書順で $T_{Q_1} \lt T_{Q_2} \lt \dots \lt T_{Q_N}$ が成り立つ
• なお、どのような $P,Q$ に対しても、条件をすべて満たす書き込み方が $1$ つ以上あることが証明できます。

• $2 \leq N \leq 500$
• $P,Q$ は $(1,2,\dots,N)$ の順列
• 入力はすべて整数

思いつけば「確かに」なんだけど、、、本番中に思いつけなかったなあ。

まず、一番小さい行・列に、0 を埋める。

N = 5
P = ([3], 5, 1, 4, 2)
Q = ([4], 1, 2, 5, 3)

  1 2 3 4 5
1       0
2       0
3 0 0 0 0 0
4       0
5       0

すると、埋めた3行目・4列目を除いて残る部分をガッチャンコすれば、 サイズが1つ小さくなった同じ問題に置き換えられる……？

それはダメで、残る行・列はいずれも「全て0」ではいけないため、完全に同じ問題ではない。

  1 2 3 4 5
1       0
2       0
3 0 0 0 0 0  ←  S3 < S5 では
4       0        なくなってしまう
5 0 0 0 0 0  ←

各行・列には少なくとも1つずつ 1 がないといけないという条件が付く。
逆に 1 があれば、少なくとも 3行目、4列目は他より確実に小さいことが保証される。

ここで少し発想を転換させ、1つサイズの小さい問題では「大きいものから1を埋める」をすればよい。

P = (3, 5, 1, 4, [2])
Q = (4, 1, 2, 5, [3])

  1 2 3 4 5
1     1 0
2 1 1 1 0 1  <
3 0 0 0 0 0
4     1 0
5     1 0
      ^

これで、3行目・4列目以外の全ての行・列に確実に 1 が入るため条件を満たし、 実質的に1つサイズの小さい同じ問題になったと見なせる。

次に残った各行・各列には、先ほどの議論を反転して、どこかに 0 が入っていないといけない。
よって、今度はまた小さい方から 0 を埋めればよい。

P = (3, [5], 1, 4, 2)
Q = (4, [1], 2, 5, 3)

  1 2 3 4 5
1 0   1 0
2 1 1 1 0 1
3 0 0 0 0 0
4 0   1 0
5 0 0 1 0 0  <
  ^

交互に 小に0 → 大に1 → 小に0 → … を繰り返していけば、答えとなる。

Python3

D - Prefix Bubble Sort

• $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ が与えられます。
• この順列に対して以下のような操作 $k\ (k=2,3,\dots,N)$ を考えます。
  • 操作 $k$ : $i=1,2,\dots,k-1$ の順に「 $P_i \gt P_{i+1}$ ならば $P$ の $i,i+1$ 項目の値を入れ替える」を行う。

• 長さ $M$ の広義単調増加数列 $A=(A_1,A_2\dots,A_M)\ (2 \leq A_i \leq N)$ が与えられます。
• 各 $i=1,2,\dots,M$ について、$P$ に対し操作 $A_1,A_2,\dots,A_i$ をこの順に適用した後の $P$ の転倒数を求めてください。

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $2 \leq A_i \leq N$
• $P$ は $(1,2,\dots,N)$ の順列
• $i=1,2,\dots,M-1$ に対して $A_i \leq A_{i+1}$ が成り立つ
• 入力される値はすべて整数

BやCより簡単に感じたな。

転倒数を、各要素に対する「(☆)自身より左にある、自身より大きな数の個数」の総和として捉える。

最初に位置 $i$ にあった要素のことを $Q_i$ とする。
（$P_i$ と書いてしまうと操作により入れ替わって中身が変わってしまうので）

$Q_i$ の(☆)は、存在する限り、$Q_i$ が操作対象となれば必ず1減る。

$A_j$ は単調増加で、$Q_i$ は自身の(☆)が存在する限り必ず左にしか行かないので、 最初に $A_j \ge i$ となる操作 $j$ で $Q_i$ が操作対象となれば $j$ 以降は必ず操作対象となる。

よって、$Q_i$ の(☆)は、「初めて操作対象になってから、$\min(Q_i の初期状態の(☆), 残り操作回数)$ 回の操作にかけて、1ずつ減り続ける」ことになる。

i          1  2  3  4  5  6
P          6  3  4  2  5  1       A:(2, 4, 5, 6, 6)

初期(☆)   0  1  1  3  1  5  →   計 11

転倒数
減少回数                          計  累積
↓操作 1      1]             →    1     1
       2         1  1]       →    2     3
       3            1  1]    →    2     5
       4            1     1] →    2     7
       5                  1  →    1     8

例えば $i=4$ の場合、2回目の操作から操作対象となり、3回（=初期の(☆)）にかけて転倒数が1ずつ減少する。
$i=6$ の場合、4回目の操作から操作対象となる。初期(☆)は5だが、残り操作回数が2回なので、2回にかけて転倒数が1ずつ減少する。

操作回数 $M$ の長さの配列に対し、各 $Q_i$ について「$Q_i$ の (☆) は、何回目の操作から何回目の操作まで1ずつ減少する」という情報を区間加算すれば、各操作において減少する転倒数を求められる。
この情報はimos法で管理できる。

初期の転倒数（＝全ての要素の(☆)の総和、上例の場合は11）から、各操作後の累積減少回数を引けば答えとなる。

転倒数を求める段階でFenwickTree等を使えば、$O(N \log{N}+M)$ や $O(N (\log{N}+\log{M}))$ などで求めることができる。

Python3