🍣

Kickstart 2022 RoundA: Speed Typing

2022/03/22に公開

Python

algorithm

kickstart

tech

問題

お題となる文字列Iが与えられる。Barbaraはスピード重視で、途中の打ち間違えを気にせずタイプを続ける。タイプ制限時間の経過後に生成された文字列をPとした時に、PからIにするには何文字削除する必要があるかを求める。ただし、削除してもIにならない場合にはIMPOSSIBLEを出力する。

アルゴリズム

PがIの部分列（subsequence）であれば、PとIの文字列長の差が削除文字数であり、PがIの部分列でなければ削除してもIにはならないので、IMPOSSIBLEとなる。

部分列かどうかを判定するメソッドをis_subsequenceとして、二つのポインタを使って実装する。先頭から比較していき、 Pの文字列を全て走査する前にIの文字列を走査し終えた場合は部分列でTrue、そうでなければ部分列ではないとしてFalseを返す。

Pの文字列長（M）回のチェックにより部分列が判定できるので、計算量はO（M）となる。

# Sub sequence check can be done in O(M) with constant extra space.
def is_subsequence(I, P):
    N = len(I)
    M = len(P)
    i, j = 0, 0
    while i < len(I) and j < len(P):
        if I[i] == P[j]:
            i += 1
            j += 1
        else:
            j += 1
    return True if i == N else False


T = int(input())
for t in range(1, T + 1):
    I = input().rstrip()
    P = input().rstrip()
    if is_subsequence(I, P):
        print('Case #{}: {}'.format(t, len(P) - len(I)))
    else:
        print('Case #{}: IMPOSSIBLE'.format(t))

問題

アルゴリズム

Discussion