AtCoder Beginner Contest 483 E,F問題メモ
E - Typo Pairs
問題文
- 英小文字のみからなる長さ $M$ の文字列が $N$ 個あります。$i$ 個目 $(1\leq i\leq N)$ の文字列は $S_i$ です。
- 以下をみたす整数の組 $(i,j)$ $(1\leq i \lt j \leq N)$ の個数を求めてください。
- $S_i$ と $S_j$ のハミング距離が $2$ 以下である。
制約
- $2 \leq N \leq 2\times 10^5$
- $2 \leq M \leq 6$
- $N,M$ は整数
- $S_i$ は英小文字のみからなる長さ $M$ の文字列
解法
$M=2$ の場合は全てのペアが該当し、$\frac{N(N-1)}{2}$ が答え。以下、$M \ge 3$ とする。
以下を数える。
- $M$ 文字のうち $M-2$ 文字を固定し、それらが一致している(ペア×固定方法)の個数 $a$
- $M$ 文字のうち $M-1$ 文字を固定し、それらが一致している(ペア×固定方法)の個数 $b$
- $M$ 文字全てが一致しているペアの個数 $c$
たとえば (aaaa, aaba) というペアは、$a$ には $3$ 回数えられる。
$(1,2),(1,4),(2,4)$ 文字目を固定した時に、それぞれ合致していると判定されるためである。
以下の文字列ペアがそれぞれ、$a,b,c$ に何回数えられるか?を考える。
- ②$M-2$ 文字一致してるペア
- $a$ に $1$ 回
- $b,c$ には数えられない。
- ①$M-1$ 文字一致してるペア
- $a$ には「実際に異なっている1文字と、その他 $M-1$ 文字から選ばれた1文字」以外を固定した場合に数えられる。
- →$M-1$ 回
- $b$ には $1$ 回
- $c$ には $0$ 回
- ⓪$M$ 文字一致してるペア
- $a$ に ${}_M \mathrm{C}_{2}$ 回数えられる
- $b$ に $M$ 回
- $c$ に $1$ 回
$②+①+⓪$ を求めたい(丸数字を、それが表すペアの個数として扱うとする)。
$c$ は⓪の個数として確定する。
$b$ は「$b=①+M \times ⓪$」が成り立つので、$①=b-M \times ⓪$ である。
$a$ は「$a=②+(M-1) \times ① + {}_M \mathrm{C}_2 \times ②$」なので、代入したら②が求められる。
F - Sum of Mod of Linear
問題文
- 整数 $N,Q$ と長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N)$ が与えられます。
- $Q$ 個のクエリが与えられるのでそれぞれについて答えてください。
- 各クエリでは整数 $x$ が与えられるので、$\displaystyle \sum_{i=1}^N ((x+A_i) \bmod B_i)$ の値を求めてください。
制約
- $1\le N\le 5\times 10^5$
- $0\le A_i \lt B_i \le 5\times 10^5$
- $1\le Q\le 2\times 10^5$
- $0\le x\le 5\times 10^5$
- 入力される値は全て整数
解法
$M=(x$ の取り得る最大値$)=5 \times 10^5$ とする。
制約から、$M$ は $10^9$ とかではなく、$5 \times 10^5$ 程度である。
全ての $x=0~M$ について答えを求められれば、当然全てのクエリにも答えられる。
$x=0$ の時、答えは $\sum_{i}A_i$ である。
$x$ を $1$ 増やした時に何が起きるかというと、
- 全ての $(x+A_i)$ が $1$ ずつ増える。全体では $N$ 増える
- ただし、$(x+A_i)$ が $B_i$ の倍数になった $i$ については、$-B_i$ される
と考えられる。
ある $i$ に対して $-B_i$ が発生する $x$ は $B_i$ ごとに発生し、その位置も決まっている。
(A,B) x 0 1 2 3 4 5 6 7 ... ----- +N +N +N +N +N +N +N +N ┐ (3,5) -5 -5 ├ x=0 の答えからはじめて、 (2,3) -3 -3 -3 │ これらの累積和をとれば答え (0,1) -1 -1 -1 -1 -1 -1 -1 -1 ┘
実は、これを愚直にやればACできる。ただし、全く同じ $(A_i,B_i)$ が複数出てくる場合には処理をまとめる。
$N$ 個が全て異なる場合に最大の時間がかかりそうだが、その場合でも、
- $B$ が同じで $A$ のみ異なるのは最大 $B$ 個ある。
- $0~M$ にかけて各ペアの減算位置を決めるのに $B$ 個全体で $O(M)$
- $B$ は小さいほど計算量がかかる。
よって $B=1$ のペアが $1$ 個、$B=2$ のペアが $2$ 個、、、という場合に多くなりそうだが、 これに出てくる $B$ の種類数は $O(\sqrt{N})$ なので、全体 $O(M\sqrt{N})$ で求められる。

