AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC148 D - Brick Break

問題原文

atcoder.jp

問題要旨

整数列  A が左から  1, 2, 3... と並ぶようにするためには、いくつの数字を削除する必要があるか?
条件を満たせない場合には -1 を出力せよ。

解法

俗に言うスターリンソート。(?)
例えば、  1a, x, x, x, 1b, x, x とあった時に「1aと1bのどちらを残すべきか?」 と疑問に思うかもしれないが、1aを残すと決めた方が、1a~1b間の3つの x のいずれかが2であった時に得をする = 損することはない。
よって数列を左から見て行って、次に欲しい数が来た場合には、それを使うと確定して問題ない。

実装

N = int(input())
A = list(map(int, input().split()))

next_break = 1
ans = 0
for a in A:
    if next_break == a:
        next_break += 1
    else:
        ans += 1

if next_break == 1:
    print(-1)
else:
    print(ans)  

next_break1 のまま」 = 「1 が見つからなかった」なので、 -1 を出力する。

感想

ある操作をしても損をすることはない という発想は、常に頭の引き出しに入れておきたいですね。