AGC057 参加記

ox----

AGC057 に Rated 参加しました。惨敗しました。

A 問題。部分列の包含関係が DAG になっていることから上からとる貪欲が可能。$L,R$ の桁数が違うときは $R$ より $1$ 桁小さい $R$ の部分列の最大値を考えればよい。

B 問題。答えを $W$ 以下にできるかどうかで二分探索を試みる。$A_i$ の操作による変化先は区間になるので、両端を考える。このとき、片端だけ $+W$ することで「$A$ をすべて同じ値にできるか」を imos 法で管理できる。これによって時間計算量 $\Theta (N\log N\log 10^{18})$ が達成できるが TLE する。改善案も思いつかずそのまま終了。

C 問題以降。ほぼ見ていません。自分ではとてもかなわないと思った。ただ、C 問題で $\oplus$ と $+$ について似た処理が可能であるという知見を得たので、あとで考察したい。