コンテストページ
AtCoder Regular Contest 100 - AtCoder
解法
✅ C - Linear Approximation（300 点）
もとの配列から予め添え字分引いておくことで、abs( a_i - b ) の和を最小化するのでよくなります。b が中央値のときが最善です。
✅ D - Equal Cut（500 点）
まず大グループ 2 つに分けましょう。その切れ目を全探索です。そしてそれぞれをだいたい均等に分けましょう。より正確には、半々を挟んで 2 つ候補を上げれば十分です。尺取り法で解けるのはわかるのですが、lower_bound のほうが書きやすいのでそちらを選びました。後日尺取りでも通しましょう。
✅ E - Or Plus Max（700 点）
添字の条件を i | j ≦ K から i | j ⊆ K に強めて、最後に累積 max を取って辻褄を合わせましょう。
こちらの条件は i, j で独立ですから、第一位と第二位を割り振りましょう。そのために、各部分集合について、第一位と第二位のペアを前計算します。これは結合的で可換な演算 (x,y) <> (z,w) = ( max(x,z), max( min(x,z), y, w) に関する部分集合累積ですから、高速ゼータ変換で計算することが出来ます。
ところで私は高速ゼータ変換を初めて書いたのですが、初めて書くのがこのような変わった演算になるなんて、思ってもいませんでした。
❌ F - Colorful Sequences（1100 点）
時間は十分にあったのですが、解けませんでした。
元の数列の位置ごとに分けて計算するのでしょうか。distinct になっている長さ K の区間でも分けたいところなのですが、こちらは重複して数えていはいけないので難しいです。包除も考えましたが、要素数だけできまりませんから、難しそうです。
そして、解説を拝見しました。制約エスパーメタ小宮なので、計算量が Θ( N * K ) であることは決めつけて考えていたのですが、「前 K 個の種類数」かなと思っていたのが良くなかったようです。どこまで無重複かの方が大事です。
結果
62 位、2537 橙パフォです。4 問目に手も足も出なかった私には、速解きゲーになってしまいました。
この 3問を爆速で通せたら赤パフォと考えると、夢があるのですが、前 3 問はどちらかというと易しい印象でしたので、不思議な気持ちです。4 問目が難しすぎてバグってしまったといった感じでしょうか。
