https://atcoder.jp/contests/abc162

ABC162に参加したのでメモ。

A	B	C	D	E	F
o	o	o	o	x	x

A~Dは問題なく解けた。

D

$1\le N \le 4000$なので、$(i, j, k)$を全探索する方法は間に合わない。$(i, j)$を全探索して条件を満たす$k$の個数を効率よく計算する方針で解く。$(i,j)$が与えられているとする。$(S_i, S_j) = (R, G)$のとき、$j < k \le N$かつ$k \ne 2j - i$を満たす$k$で$S_k = B$となっているものを数えればいい。事前に累積和を求めておくことで、$[j, 2j - i)$、$[2j - i + 1, N + 1)$に含まれるBの個数は$O(1)$で求められる。同様にして、$(S_i, S_j) \in \{ (c1, c2) \mid c1, c2 \in \{R, G, B\} \text{かつ} c1 \ne c2 \}$の場合も$O(1)$で計算できる。したがって、全体としては$O(N^2)$で答えが求まる。

E

数列$\{A_1, \cdots, A_N\}$をうまく列挙して(代表的な要素を選ぶとかして)数えるという方針、つまり、$\{A_1, \cdots, A_N\} \rightarrow gcd(\{A_1, \cdots, A_N\})$という方向で考えていた。例えば、$A_1, \cdots, A_N$がすべて素数であるとき、互いに素であることは明らかなので、$gcd(\cdots) = 1$となる。素数がK以下にたくさんあれば、それ以外については全探索するとかして計算量を減らせるが、合成数より多いなんてことはないので、うまくいかない。時間ギリギリくらいで、$\{A_1, \cdots, A_N\} \leftarrow gcd(\{A_1, \cdots, A_N\})$の方向で考えると筋が良さそうということに気づいた。

$gcd(\cdots) = g$のとき、これを満たすような数列は、$g, 2g, 3g\cdots$からgを必ず含むようにして要素を選べばいいのだが、約数系包除に慣れておらず、うまく数え上げられなかった。

• $A -> B$という方針で問題を考えている場合は、$B -> A$という方針も検討する