ARC087 C - Good Sequence

問題
提出コード

解法

xは数列の中にちょうどx個存在しないといけないのですが、今回数字を増やす操作ができないので、xの個数がx未満であったら、全て取り除かなければなりません。
ここで制約をみると、数列の長さは以下なので、この時点でこれを超える大きさの数字はすべて取り除くことが確定します。これによって計算量を落とす必要があります。
あとは~のすべての数字について全探索をします。今iを見ているとき、iの個数がちょうどiか、iを超えているか、iを下回っているかで操作がかわります。ちょうどのときは何も起こらないので省略します。

(1). 超えているとき
ちょうどi個にするので、

• (今ある個数) - i

が取り除く個数になります。

(2). 下回っているとき
先ほども述べたように、ちょうどi個にすることができないので、

• (今ある個数)

が取り除く個数になります。

あとはこれを足し合わせていけば答えになります。