Codeforces 614 Div. 2 A から F

A

ありうる最も左の点と右の点がわかれば、その間の点はすべてありうるので植木算。自分は気づかなかったが、要素数足す一が答え。

B

連続部分列の和の最大値は動的計画法で求められる。この問題では列全体が答えにならないようにしなければならない。そこで前半 $N - 1$ 個と後半 $N - 1$ 個でそれぞれでわけて解くとよい。

C

$a$ と $b$ が互いに素でないとき $a$ と $b$ を最大公約数で割ったものを選んだほうが得であるため、$a$ と $b$ は互いに素であると仮定してよい。このとき $a$ は $X$ の約数となるはずである。よって $X$ の約数 $d$ であり $d$ と $X/d$ が互いに素になるようなもののなかに答えはある。

D

桁数 $L$ 以下であり、長さ $N$ の列 $A$ が与えられたとき最小値を求める問題 $f(L,A)$ を考える。$X$ を上の桁から決めていくことを考える。$L$ 桁目が $0$ であるものを $A_0$ に、$1$ であるものを $A_1$ に振り分ける。このとき $A_0$ が空ならば $f(L - 1, A_1)$ が答え、$A_1$ が空ならば $f(L - 1, A_0)$ が答え、そうでないならば $f(L - 1, A_0)$ と $f(L - 1,A_1)$ のうち小さい方が答えになる。

E

どの区間も互いに包含関係にならない場合を考える。このとき左端で整列すれば右端も整列される。そのため左から見ていくことで解ける。

包含関係にある場合、ある区間に包含されているような区間を消していくと、どの区間も互いに包含関係にならない区間集合が得られる。この区間集合はどのような消し方をしても同じものが得られる。この過程で消された区間は答えを与えることはないため、得られた区間集合だけを考えればよい。

得られた区間集合を $I_1,\ldots,I_n$ とする。$I_k$ に包含されている区間の集合を $ J_1, \ldots ,J_m $ としたとき、$ I_1, \ldots,I_{k - 1},I_{k+1},\ldots,I_n,J_1,\ldots,J_m $ の和集合の連結成分数を数えられればよい。$ J_1,\ldots,J_m $ を列挙するとき $I_{k - 1}$ や $I_{k+1}$ にも包含されているようなものは列挙する必要がないため、$k$ が $1$ から $n$ を動くとき $ m $ の和は $n$ 以下にできる。また連結成分数の計算は $f(I_1,\ldots,I_{k - 1}) + f(I_{k - 1},J_1,\ldots,J_m,I_{k + 1}) + f(I_{k + 1},\ldots,I_{m}) - 2$ でできる。ただし $I_{k - 1}$ や $I_{k + 1}$ が存在しないときは $2$ の部分を適切に減らす。

F

解説を読んでから解いた。これは賢い。

最大公約数を g に固定する。このとき $g, 2g, 3g, \ldots$ だけを見ればよい。g が 1 から 100000 まで動くとき、見ることになる数は 100000 log 100000 個程度であることに気をつける。

最大公約数が 1 の場合を考える。100000 から 1 へと見ていく数を減らしていき、見終えるたびに見た数をスタックに積んでいく。このときスタックの上の方に小さい値が積まれることに気をつける。いま見ている数と互いに素な数がスタックに含まれている場合、その数より上に積まれている値は取り除いてしまってよい。もしもスタックの中に互いに素な数が含まれているのかが高速に判定できればこの問題を解くことができたことになる。

たとえば 12 と互いに素なものの個数は「1 の倍数の個数」引く「2 の倍数の個数」引く「3 の倍数の個数」足す「6 の倍数の個数」で求められる。「k の倍数の個数」が 1 から 100000 のすべての k に対して計算されていれば、たかだか 12 の約数の個数分の足し引きで互いに素なものの個数が数えられる。

計算量解析においては「k の約数の個数」の二乗を 1 から 100000 まで足したものが現れるが 26324772 であるため間に合う。