ARC080-E Young Maids
解法
先頭に追加していって辞書順最小を目指すので、操作を後ろから考える。
数列のうち、使っていない数でできた連続区間の長さがすべて偶数となるように、同じ連続区間からふたつの数を取っていけばよいということがわかる。
問題は、1個目に取れる数のうち最も小さいものを検出する作業だが、std::set
に区間ごとの最小値を入れておいて逐次更新すれば良い。
ある区間の最小値を求めるのは、SegTree を使ってもいいし、Sparse Table でもよい。
区間を扱う系の実装は結構重めになりがちだが、今回は割と簡潔に書けたと思う。(提出リンク)
感想
貪欲に気づいてから具体的な解法に至るまで時間がかかったので、したい操作からデータ構造をさっと引き出せるようになりたい(JOIもあるので)