ABC165 参加メモ - tinumu's reminder

発想自体は思いつきやすいが、そこからちゃんと詰めて書けるのかというところを頑張るべきだった。躓きすぎて5ペナABCDE5完(91:40+25:00)
1974->1945(-29, Perf = 1642, 859th) 調子悪いにしたら激冷えにはならなかったなと思っている

A

そうだよなあ…b/k*bで位置が出てくるわけだからそれがA以上なら包含してるんだよなあ
条件ミスって1WA

B

val += val / 100ですね
なんか思いつけなかった

C

こういう組み合わせは仕切ると出てくる。
すると最大でも $\binom{19}{10} = 92378$ くらいになるみたい
つまり全列挙してそれぞれポイントを計算すると $\mathrm{O}((N+M)_{N+M-1}\mathrm{C}_{N})$ くらい出てくる

D

とりあえず $B-1 \leq N$ のときだけ考える
見た感じ、 $x$ は $nB-1$ とかにしておくと良さそう(それ以外は $nB-1$ まで数を上げると $\lfloor Ax/B \rfloor$ だけ無条件に値が上昇するので最適解は $nB-1$ の中にあることが分かる)

もう実は $n$ の上限は小さいので十分間に合うけど、実は答えは $x=B-1$ のときになっている。
理由は $x=nB-1$ の解が $x=B-1$ のときと一致するからである。

あと言ってなかった $N \lt B-1$ のときは、 $x=N$ のときが一番大きいので、まとめると、
$x=\min(B-1, N)$ のときが答えである。

E

ダメな条件を列挙してみる $a_i \lt b_i$ とすると

$b_i-a_i=b_j-a_j$
$(a_i+N)-b_i=(a_j+N)-b_j$

さえ大丈夫ならいいっぽい
もし $b_i-a_i = d$ だったら、 $(a_i+N)-b_i = N-d$ になっているので、 $d \lt N/2$ みたいになるようにやっていけばかぶらないで済みそう
実際、 $M \times 2 + 1 \leq N$ という制約があるので頑張れば見つかりそう

差が奇数同士のものを集めると、例えば

みたいに入れ子にする発想が出る。
同じように偶数もこの入れ子の隣とかに

7 11

8 10

みたいにおいておくと、今の問題なら $M=5, N \geq 11$ について解くことができた。

これをちゃんと一般化して解けば終わり

F

LISを１段階戻す操作が適切にできれば解ける。
木が分岐しているときはある一方を深さで進めて処理したときにもう一方をやるにはLISの状態をもとに戻してからやらなきゃいけない。
もとに戻すにはLISの挿入操作をする前に　挿入するところのもとのデータと位置さえ持っておいて、戻すときにそのデータに戻せば $\mathrm{O}(1)$ でできる。
適切に潜ったり戻ったりして、その際に操作を行えば、すべての $k$ についてサイズは求まるので $\mathrm{O}(N)$ で解けました。