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 ②$」なので、代入したら②が求められる。

Python3

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})$ で求められる。

Python3

programming_algorithm/contest_history/atcoder/2026/1107_abc483.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0