JOI難易度７ JJOOII 2 - あっとのTECH LOG

問題原文

問題要旨

J, O, I からなる長さ $N$ の文字列 $S$ が与えられる。
また、 J, O, Iを $K$ 個ずつ並べた文字列を「レベル $K$ のJOI文字列」と呼ぶことにする。

「ある位置の文字を削除する」という操作を最低何回行えば $S$ をレベル $K$ のJOI文字列にできるか。
ただし、先頭もしくは末尾の削除は操作回数にカウントしない。またレベル $K$ のJOI文字列にできない場合には -1 とせよ。　　

$1 \leq N \leq 2×10^{5}$

解法

「ある箇所からレベル $K$ のJOI文字列の構築を始める」と決めた時、そこから貪欲的に構築していくのが最適。
すると、ある場所の J から始めるとして、そこから数えて $K$ 番目の J の場所、 $K$ 番目の J の場所の次の O の場所、その O から数えて $K$ 番目の O の場所。。。が欲しくなる。そしてこれは予め $O(N)$ でおけばよい。

実際に次にみるべきindexは二分探索とかで適当にやれば求められる。

実際のコストは（Jの始まりとJの終わりの間にある邪魔者の数） + (Jの終わりとOの始まりの間にある邪魔者の数) + (Oの始まりとOの終わりの間にある邪魔者の数) + (Oの終わりとIの始まりの間にある邪魔者の数) + (Iの始まりとIの終わりの間にある邪魔者の数) になる。

実装

ちょっと汚いので各indexだけ求めて最後に計算すればよかったね判定としてはI の終わりのindexが場外にはみ出さなければOKなので

まぁ読めるからいいか！w

from bisect import bisect_left
N, K = map(int, input().split())
S = input()

J_indexes = [i for i, s in enumerate(S) if s == 'J']
O_indexes = [i for i, s in enumerate(S) if s == 'O']
I_indexes = [i for i, s in enumerate(S) if s == 'I']


ans = float('inf')
for Js in range(len(J_indexes) - K + 1):
    tmp = J_indexes[Js + K - 1] - J_indexes[Js] - (K - 1)

    Os = bisect_left(O_indexes, J_indexes[Js + K - 1])
    if Os + K > len(O_indexes):
        continue
    tmp += O_indexes[Os] - J_indexes[Js + K - 1] - 1  # Jの終わりとOの最初の接続部分
    tmp += O_indexes[Os + K - 1] - O_indexes[Os] - (K - 1)

    Is = bisect_left(I_indexes, O_indexes[Os + K - 1])
    if Is + K > len(I_indexes):
        continue
    tmp += I_indexes[Is] - O_indexes[Os + K - 1] - 1  # Oの終わりとIの最初の接続部分
    tmp += I_indexes[Is + K - 1] - I_indexes[Is] - (K - 1)

    ans = min(ans, tmp)

print(ans if ans != float('inf') else - 1)

感想

難易度７埋めてくぞ〜