コンテスト中AC:A,B
A - Erase by Value
同じ数は消えるので、一旦連続して重複した数について、重複を削除して考えます。
から始めて、単調増加している間は、消すと辞書順では大きくなってしまうので、消さない方がよいです。
そこで、減少に転じた時に、その直前の数(すなわち、を開始点とした、単調増加な部分の最大値)を消してみます。この時消す数を
とし、生成される数列を
とします。
すると、より後の数を消すと、必ず
という部分が残るので、この時生成される数列が
より辞書順で小さくなることはあり得ません。よって、
が辞書順最小となります。
なお、減少に転じない場合もあるので、その場合は末尾の数を削除対象にします。
[提出コード] (https://atcoder.jp/contests/arc133/submissions/28684574)
B - Dividing Subsequence
を、それぞれ
とすることを
と
を対応させると呼ぶことにします。
また、問題文の制約に沿って生成されるを適合列と呼ぶことにします。適合列の要素数と言った時には
(または
)の要素数を指すことにします。
と
を対応させた時に得られる適合列の要素数の最大値は、
から作られる適合列の内、要素数が最大であるもの + 1
です。
添字に着目すると、かつ
を満たすすべての
の適合列の要素数の最大値が計算されていれば、
のときの最大値を計算できます。そこで、添字の問題に帰着させます。
と
が対応可能である場合に
となる配列
を作ることを考えます。
と
のあり得るすべての組を
に記録します。
例),
は
と対応可能
は
と対応可能
は
と対応可能
は
と対応可能
の構築方法は後述します。一見全組を得るのに
になりそうですが、エラトステネスの篩と同じ様に
で構成できます。
をキーとして昇順ソートします。すると、
なら
になります。
一旦、の場合を無視すると、
を満たす
(つまり、
より前に出現したもの)のうち、
となる
から最大値を得る
問題となります。これはBynary Indexed Treeによって反転数を求める問題の考え方を応用できます。
今回は最大値を得たいので、maxの二項演算が規定されたSegment Treeを使います。Segment Treeの値を保持する配列をとします。最初、全て0です。
を計算したいとき、
という計算によって、
となる
から最大値を得ることができます。
そして、
と更新すれば良いです。の場合ですが、今回はこれを満たす
は無視したいです。そこで、
が等しいものについて最大値を全て計算し終わった時点で、一括して上記の更新を行うようにすれば良いです。
上に示した方法によって、の小さい方から順に最大値を計算して行くことができます。
さて、後回しにしていた数列の構築方法です。
配列を用意し、
が出現したインデックス
を記録します(
)。
例)
の時、
と対応可能な
は
の倍数です。よって、この時の
を得たい場合、配列
を利用すると、
というように得ることができます。
これはエラトステネスの篩と似たような処理であり、です。よって、
それぞれの配列サイズも
で収まると言えます。
全体の計算量は、の構築に
で、最大値の計算と更新にも
となるので、
だと思います。
提出コード
ちなみに、上記コードはインデックスの組を二次元配列として持たせています。
iと組が作れるjは、