ACPCVC20200525 復習メモ - tinumu's reminder

https://kenkoooo.com/atcoder/#/contest/show/25688e6e-acd2-4910-857a-253f76e494b6
この難易度帯はちゃんと確実に解けるようになりたいな

A - Ears

すぬけくんの散歩で入れられる石の区間は $5$ 種類に区別できる。
$x$ の小さい順から、

状態 $0$ : 石を入れられない( $0$ 個)
状態 $1$ : 石を $2$ 以上の偶数個入れられる
状態 $2$ : 石を奇数個入れられる(始点と終点の間)
状態 $3$ : 石を $2$ 以上の偶数個入れられる
状態 $4$ : 石を入れられない( $0$ 個)

というようになっている。これは紙とかに書いてみるとそんな感じに出来ることが分かると思う。

上のことがわかったので、どのタイミングで状態遷移をするかという事を選択するDPを行う事で最小の回数が求まる。
$dp_{i, j}$ : $i$ 番目まで見ていて、現在の状態番号が $j$ であるときの石を入れる必要のある最小の数
この状態があれば問題なくまとめられるのであとはそれぞれの状態で最小になるようにすぬけ君が石を置いていけば、問題なし。

すぬけ君の最適な石の置き方によって生じるコスト

状態 $0$ : $A_i$ を足す
状態 $1$ : $A_i = 0$ のときは $2$ , そうでないときは $A_i \mod 2$ を足す
状態 $2$ : $1-(A_i \mod 2)$ を足す
状態 $3$ : 状態 $1$ と同様
状態 $4$ : 状態 $0$ と同様

耳DPって何を以ってどうなんだろう

B - Engines

それぞれのエンジンをベクトルと考える。
$2$ つのベクトルがあって、それらを使うとする。
このとき、 $2$ つのベクトルのなす角の内部にあるベクトルたちは明らかに使ったほうが距離を伸ばせる。
そのため、実は $2$ つベクトルが決まりさえすれば最適解に含まれるパターンは全て列挙できたことになる。

以上のことから、角度でベクトルをソートしておいて、２つベクトルを決めてその内部のベクトルの和を取って、それの最大値を求めれば良い。
愚直に実装しても $\mathrm{O}(N^3)$ であるので、制約的に普通に間に合う。

ABC139バチャしてた時はなぜ気づかなかったのか

C - Small Products

$dp_{i, x}$ : 最後の整数が $x$ であるような $i$ 個の整数を並べたときの場合の数と置く。
このdpの愚直な実装だと間に合わない。
だが、 $\lfloor \frac{N}{y} \rfloor = \lfloor \frac{N}{x} \rfloor = t$ であるような $x, y$ は $dp_{i,x} = dp_{i,y} = \sum_{z=1}^{t} dp_{i-1, z}$ となり同じ値になるのでそこだけ考えるとまとめられそう。
$\lfloor \frac{N}{x} \rfloor = t$ になる $x$ の範囲といえば $\left( \lfloor \frac{N}{t+1} \rfloor , \lfloor \frac{N}{t} \rfloor \right\rbrack$ となる。
同時に $dp_{i, t} = \sum_{x=1}^{\lfloor \frac{N}{t} \rfloor} dp_{i-1, x}$ というような更新ができる。
つまり、ある位置から区間への更新と、区間からある位置への更新が位置がずれることなく適切に行える。

そう考えると、やはりdpはまとめられることに気づく。
$i \leq \sqrt{N}$ まで通常の位置を用意して、 $i \geq \sqrt{N}$ からは $\lfloor \frac{N}{j} \rfloor (j \leq \sqrt{N})$ 単位で区間を区切っていって圧縮する。
これをうまく処理すると、 $\mathrm{O}(\sqrt{N}K)$ で処理するDPがかける。
更新の際に $\sum$ が出てきていたが、これは累積和を取りながらDPをやると高速に動く。