精進メモ 2021/08/16~ - ツバサの備忘録

ABC215

久々に2桁順位を取った気がします。

D - Coprime 2

ひたすら素因数分解すれば良いです。
全ての $A_{i}$ に含まれる素因数の倍数を除くと答えになるので、愚直に計算していきます。調和級数で計算量が収まるタイプです。

E - Chain Contestant

既に行ったコンテストの種類をbitでもって、最後に何が開催されているかと合わせて添え字にするタイプのDPです。

F - Dist Max 2

最小値の最大化は二分探索です。
二次元座標はどちらか片方でソートすると嬉しいことが多いのでそれを考えると、判定部分で尺取りができることがわかります。

G - Colorful Candies 2

まず、キャンディの種類ごとにまとめて計算できることがわかります。なので、それぞれの種類に対して個数を求めておきます。
種類数が $\sqrt{N}$ 以下のとき、期待値の線形性を利用して $O(N\sqrt{N})$ で計算できます。
そうでないとき、登場する個数の種類が $\sqrt{N}$ に収まっているはずです。個数ごとに計算する値は同じなので、そこをまとめることで、結局どちらの場合も同じ計算量で解くことができます。
頻度の種類が $\sqrt{N}$ で収まる問題、苦手でしたがついに自力で解けました。

ARC125

途中でパフォを見てぬか喜びしました。難しい問題を先に解いていたのでそれはそうでした…
やっぱり構築が苦手ですね。あと再帰的に綺麗に解けます、みたいなタイプも苦手なのかもしれません。

A - Dial Up

$A$ の末尾に追加すると誤読していました。
01の切り替わりタイミングまで移動したら、あとはコスト2以下でどちらも追加できます。そこだけ調べてあとは愚直シミュレートです。

B - Squares

$x^{2} - y = z^{2}$ とすると、式変形して $(x + z)(x - z) = y$ となります。
$x,y,z$ は非負なので、 $x + z \gt x - z$ です。
よって、 $x - z \lt \sqrt{N}$ であることがわかります。
$x-z$ を $p$ と固定したとき、条件を満たす $q = x + z$ がいくつあるかを求めればよいです。
$pq \leq N$ なので、 $q$ の個数はだいたい $N / p$ の半分くらいになります。
あとはこれを足し合わせていけば答えです。

D - Unique Subsequence

$A_{i}$ を選んで問題の条件を満たすには、その前後で選ぶ箇所が $A_{j}, A_{k}$ としたとき、区間 $(j,i)$ および $(i,k)$ に $A_{i}$ が存在してはいけません。
逆に、この条件を満たせば、問題の条件を満たします。
$dp[i] = i$ 番目を最後に選んで、問題の条件を満たしているような数列の個数
とすると、セグ木を使って区間和を計算しながら更新ができます。
数列の先頭と末尾に0があると仮定して計算していくと計算がしやすかったです。