E - Sequence Decomposing
- 考えたこと
- 同じ色のグループに着目すると単調増加列になっている
- 先頭から見ていって単調増加なら同じ色で塗る、という貪欲法でOKなのかを考える
- ある最良解である値xが単調増加なのに選択されてないとする
- 列がxの手前で終わってるか、xの先でxより大きい値yになってる時、コストを増やさずにxを追加できる
- そうでない時
- yではなくxを選択することでyから開始する列が1つ増えるが、xから始まる列が1つ減るので損はしない
- ただしxがもっと手前から始まる別の列に入ってる場合は別
- よって下記の貪欲法でOK
- 先頭から見ていく、既に存在するどの単調増加列にも入らないなら新しい単調増加列を追加する
- 追記: 入る場合の入れ方に関して考察漏れ
- 公式解説
- 自分実装
- 既に存在する単調増加列の複数に入りうる時に自由に入れられるわけではないと気づいた
- 2,1,4,5,3で、5は4の入った列に入れなければならない
- つまりこれ、入れる数より小さくて最大の値を見つけなければならない
- 線形探索すると最悪ケースでTLEしそう
- 対象が静的でないからソートして二分探索というわけにはいかない
- フェニック木で二分探索か…値の範囲が10^9だなぁ
- この方針でやるなら座標圧縮→フェニック木→二分探索という流れになるな
- この前処理や、本処理で二分探索が必要になるところから計算量は公式解説と同じオーダーになる
- 公式解説
- 僕と逆に後ろから見ている
- 制約を満たす中で最小のものを選ぶのは僕の「入れる数より小さくて最大の値」を選ぶ方法の裏返し
- フェニック木を使う方法は最長増加部分列の解法の一つ
- なるほど、「xを超えない最大の値をxに更新」はソートされた状態を維持するのか
- 更新され二分探索できる配列