ゴールが見えると手を抜いてしまう、人間だもの

Solved By kkktym
Topcoder: 0
Codeforces: 239
AtCoder: 1498
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1809

ARC080E - Young Maids

辞書順最小なので先頭から貪欲に小さい要素をとっていけば良い。末尾から足すことになるのでとることができる要素と取り出し方には制限がつく。先頭に持ってこれるのは偶数 index (0-index) のものだけで、2番目は奇数 index のもの、かつ先頭のものより後ろにあるものだけである。これは偶奇 index それぞれの要素についての区間最小セグ木を持っておけばいける。これらの要素を取り除いたら取り除いた部分を境に区間が分断されることになり、区間ごとに同じような操作をすれば良い。この際、先頭に持ってこれる要素の index の偶奇は区間の下端の偶奇に依存するので注意する。あとは区間DPのノリで、更新順をダイクストラのノリで処理すればいける。優先度付きキューちゃんに、std::pair<std::pair<int,int>, std::vector<std::pair<int,int>>> なんていう重たいものを持たせちゃった...ごめんね...

ARC076E - Connected?

サンプル3 を紙に描いてYESであることを確認するのに時間がかかった。曲線の可能性は無限大！って感じ。結局長方形の周上を時計回りに見ていって2回登場する要素の区間が前後しなければおっけー。実装に手間取った。解説では括弧列とみなして stack で判定、をしていて賢かった。fox のやつと一緒だね。

ARC067E - Grouping

要素をいくつかの集合に分ける通り数を、重複なく数え上げるには mex を次の集合に必ず入れることにすればいい！ (ABC180F-Unbranched) だ！と思ったけどうまくいかず。要素数の大きい集合っていくつも作れなくない？√Nで抑えるやつか？と考え、素直なDPを考えてみると、√Nのやつでは無かったけど調和級数のやつであることに気づく。あとは素直にDPをするのみ。なんか考察の手札が増えてきてめっちゃ楽しい。