AtCoder Beginner Contest 234

　Gを除く七完。Hは嘘かと思いつつ投げたが、実際は正しい解法だったよう。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 234 Gを除く七完。
C 二進数っぽく
D heapq
E 全部列挙しても少ない
F 二項係数を使って二乗DP
G 二乗DPはすぐ分かって、maxとminに分割できることも気付いた。その後の高速化ができず。
Ex kd木とか使いそうけど持ってない。とりあえず平面を距離Kずつに分割してみる→AC

— titia (@titia_til) January 8, 2022

G - Divide a Sequence

　解説AC。

　二乗のDPにはでき、式を書いてみると、maxとminは分割できることには気付けた。あとはなんらかの方法で高速化するのだろう、とは思ったが、stackを使った高速化は思いつかなかった。

　もらうDPで書いたとき、DP[i]の更新で必要なのは、各jについて、j～iについての最大値とDP[j]の値。

　この「j～iについての最大値」という配列は、jについて単調減少になっているため、そこに一つ要素xを付け加えたとき、変更されるのは後ろいくつかがxになる、というだけである。

　なので、[最大値, 最大値*DP[i]]というのをstackに突っ込んで置き、そこに新たに加わる要素xがstackの最後の要素より小さければただ付け加える。大きければ、最大値がxより小さいものたちについてmergeし、差分計算をしていけば良い。

　stackによる高速化は定石の一つなので、思いつかなかったのは反省。