AtCoder Grand Contest 062

　A一完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Grand Contest 062 Aを置いた後BCを行ったり来たりしていたがどちらも分からず。
A 実験したら、A*n+B*m(m>0)のときだけBだった。

— titia (@titia_til) May 21, 2023

B - Split and Insert

　解説AC。公式解説は理解できず、こたつがめさんの実況放送の振り返りで理解した。区間に分割していけば良いというのはなるほどです。

　また、類題（もしくは、この問題の簡単なバージョン）も解いたが、確かに類題ではあるものの、今回のAGCの問題には結構なギャップがある気がした。

　いや、今回のコンテスト中に、最小回数だけならlog2の何か（具体的には分からなかった）になるとか、マージソートっぽく再帰していく感じだな……とは思っており、最小回数を求める問題（つまり、この類題）であったなら後一歩のところまで来ていたと思う。

　だが、最小回数の導出方法が分かってもコスト計算をどうすれば良いかは見当も付かず、解説などを見てようやく理解できた……という感じだった。

C - Mex of Subset Sum

　区間で管理すれば通るという情報を得てAC。

　計算量の証明はよく分かっていないけれど、区間で管理するというのは思いつきたかった。コンテスト中、部分和問題だからDPしかないと思い、それを高速化する方法を考えていたのだから、ねぇ。