AtCoder Beginner Contest 150 D～F問題メモ

AtCoder Beginner Contest 150

• 解説放送: AtCoder Beginner Contest 150 - YouTube

D - Semi Common Multiple

• 長さ $N$ の偶数列 $a_1,a_2,...,a_N$
• ある非負整数 $X$ が以下の条件を満たす時、$X$ を「半公倍数」と呼ぶ
  • 全ての $k \ (1 \le k \le N)$ に対して、$X=a_k \times (p+0.5)$ となる整数 $p$ が存在する（$p$ は $k$ ごとに別々でよい）
• 整数 $M$ が与えられるので、1以上 $M$ 以下の半公倍数の個数を求めよ
• $1 \le N \le 10^5$

小数が出てくるとややこしいが、$b_i=\frac{a_i}{2}$ として、$X=b_i \times (2p+1)$ としてしまえばいい。

これで、以下の2つを満たせばよいことがわかりやすくなる。

• $X$ は全ての $b_i$ の公倍数
• $X$ を $b_i$ で割った商は全て奇数

なので、とりあえず全ての $b_i$ の最小公倍数を求めて、それが $b_i$ で割ると全て奇数となるか確認する。

1つでも偶数となるものがあれば、達成不可能。

全て奇数なら、最小公倍数の奇数倍が全て条件を満たす。

2数 $n,m$ の最小公倍数は、最大公約数を $g$ として $\frac{nm}{g}$ で求められる。3数以上なら、これを繰り返し適用しつづければよい。

ただし $b_i$ が互いに素だと、最小公倍数は繰り返している内にとてつもなく大きくなってしまう。途中で $M$ 以上になった時点で $M$ 以下の半公倍数は不可能なので、0を出力して即終了する。

E - Change a Little Bit

• 長さ $N$ の数列 $C_1,C_2,...,C_N$ が与えられる
• 0と1からなる2つの異なる数列 $S,T$ を考える
• $S$ の先頭から $i$ 番目の要素を、0から1、または1から0に変更するには、操作直前に $S$ と $T$ が異なっている個数を $D$ として、コスト $C_i \times D$ かかる
• $f(S,T)$ を、$S$ を $T$ に一致させるのに必要なコストの最小値とする
• さて、$(S,T)$ の組み合わせは、$2^N \times (2^N-1)$ 通りある
• 全ての $(S,T)$ の組について $f(S,T)$ を求め、その総和を求めよ
• $1 \le N \le 2 \times 10^5$

最初から異なっている要素数が $k$ 個の時、異なっている箇所にある $C_i$ のうち、

• $C_{i1}$ を選び $C_{i1} \times k$ のコストをかけて、異なっている要素を $k-1$ 個にする
• $C_{i2}$ を選び $C_{i2} \times (k - 1)$ のコストをかけて、異なっている要素を $k-2$ 個にする
• …
• $C_{ik}$ を選び $C_{ik} \times 1$ のコストをかけて、異なっている要素が0になる

という操作を経て、$S$ と $T$ が一致する。 なので、$C_i$ の小さい方から処理するのが最適である。

とりあえず $C_i$ を昇順にソートし、indexを0から振り直す。

i   0   1   2   3   4
C  25  52  67  72  79

（注: 解説pdfとは逆順で考えを進めている）

1つずつ $f(S,T)$ を求めるという視点から、各 $C_i$ が何回足されるかという視点に転換する。

$C_i$ について考える時、$C_i$ より小さい要素、$C_i$、$C_i$ より大きい要素に分けてそれぞれのパターン数を考える。

まず、$C_i$ より小さい要素は $i$ 個あるが、$S_i,T_i$ が0,1のそれぞれどちらを取るかで1つあたり4通り、計 $4^i$ 通りある。 この部分は、最初に異なっていようと、$i$ 番目を変更する頃には先に操作されて同じになっているので、初期状態を気にしなくてよい。

$C_i$ が足される場合、要素 $i$ は異なっていることは確定。(0,1)(1,0)の2通りある。

$C_i$ より大きい要素は全部で $N-i-1$ 個あるが、コストに関わってくるので初期状態で異なっている箇所の数 $k$ を気にする必要がある。

$k$ を固定すると、パターン数は $N-i-1$ 個から $k$ 個を選ぶので、${}_{N-i-1}C_k$、 各要素に付き、同じ要素は(0,0)(1,1)、違う要素は(0,1)(1,0)でそれぞれ2パターンずつあるので $2^{N-i-1}$。

コストは1パターンあたり $C_i(k+1)$。（$k$ のカウントに $i$ 番目は入っていないため、1足す）

これを $k=0～N-i-1$ までの総和を取るので、コスト総計は $\displaystyle 4^i \times 2 \times 2^{N-i-1} \times \sum_{k=0}^{N-i-1}{{}_{N-i-1}C_k \times C_i \times (k+1)}$ となる。

しかし、このままでは1つの $i$ を求める内部でさらに $\sum$ のループがあるため $O(N^2)$ となってしまう。

ここで、二項係数の総和の公式より、$\displaystyle \sum_{r=0}^{n}{{}_nC_r(r+1)}=2^{n-1}(n+2)$ となることを利用できる。

• sum ncr(n, k) * (k+1), k=0 to n - Wolfram|Alpha

式変形による証明

よって上の式は、$\displaystyle 4^i \times 2 \times 2^{N-i-1} \times 2^{N-i-2} \times (N-i+1) \times C_i$ となり、 2の冪をまとめると上手い具合に合成されて $4^{N-1} \times (N-i+1) \times C_i$ となる。

よって、これを $i=0～N-1$ まで合計すれば、答えとなる。

F - Xor Shift

• 長さ $N$ の2つの非負整数列 $A=\{a_0,...,a_{N-1}\}$ と $B=\{b_0,...,b_{N-1}\}$ が与えられる
• 次の条件を満たす整数の組 $(k, X)$ を全て列挙せよ
  • $A$ を $k$ 個左に回転させ、全要素に $X$ をXORすると、$B$ に一致する
• $1 \le N \le 2 \times 10^5$
• $0 \le a_i,b_i \lt 2^{30}$

A  0  2  1
B  1  2  3

(k, X) = (1, 3) のとき、
A  2  1  0    左に1個回転
A' 1  2  3    X=3をXOR でBに一致させることができる

共通の数 $X$ をXORしても、隣り合う要素とのXORは変わらないことがとっかかりとなる。

つまり、$C=\{a_0 \oplus a_1,a_1 \oplus a_2,...,a_{N-1} \oplus a_0\}$ とすると、$A$ にどんな数をXORしても $C$ は不変となる。

よって、$A→C$ と同様に $B→D$ も作ると、「$C$ をいくつずらすと $D$ に一致させることができるか？」と$X$ を除外して $k$ のみに限定して考えることができる。

これは、$D$ を繰り返して2倍の長さにしたものを $D'$ として、$D'$ から $C$ を探す処理に言い換えられる。

数列の各要素を文字と見なして、文字列検索アルゴリズムのローリングハッシュやKMP法を用いることができる。

一致するindex $k$ が見つかれば、$A_k$ と $B_0$ を一致させればよいので、$A_k \oplus X = B_0 → X = A_k \oplus B_0$ より、その $k$ に対しての $X$ を求められる。