結果

問題 No.1542 ぽんぽんぽん ぽんぽんぽんぽん ぽんぽんぽん
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:54:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,804 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 74,928 KB
最終ジャッジ日時 2025-03-31 17:55:59
合計ジャッジ時間 3,043 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().strip()
    if N < 6:
        print(-1)
        return

    # Check if 'ponpon' is a subsequence of S
    def has_original(s):
        target = list("ponpon")
        idx = 0
        for c in s:
            if idx < 6 and c == target[idx]:
                idx += 1
        return idx == 6

    if not has_original(S):
        print(-1)
        return

    # Calculate character counts
    from collections import Counter
    count = Counter(S)
    max_possible_k = (N - 6) // 3  # Maximum possible k due to length constraint

    for k in range(max_possible_k, -1, -1):
        # Check if current k meets character count requirements
        required_p = 2 + k
        required_o = 2 + k
        required_n = 2 + k
        if count['p'] < required_p or count['o'] < required_o or count['n'] < required_n:
            continue  # Skip if counts are insufficient

        # Try to remove k 'pon's greedily from the right
        s_list = list(S)
        removed = 0
        last = len(s_list) - 1  # Track the end of the remaining string

        # We need to remove exactly k 'pon's
        for _ in range(k):
            # Find the rightmost 'n', 'o' before it, then 'p' before that
            p_pos = -1
            o_pos = -1
            n_pos = -1

            # Search for 'n' starting from the end
            for i in range(last, -1, -1):
                if s_list[i] == 'n':
                    n_pos = i
                    break
            if n_pos == -1:
                break  # No 'n' found, cannot proceed

            # Search for 'o' before n_pos
            for i in range(n_pos - 1, -1, -1):
                if s_list[i] == 'o':
                    o_pos = i
                    break
            if o_pos == -1:
                break  # No 'o' found before 'n'

            # Search for 'p' before o_pos
            for i in range(o_pos - 1, -1, -1):
                if s_list[i] == 'p':
                    p_pos = i
                    break
            if p_pos == -1:
                break  # No 'p' found before 'o'

            # Remove the found 'p', 'o', 'n' in reverse order
            # To avoid index shifting, start from largest index
            s_list.pop(n_pos)
            s_list.pop(o_pos)
            s_list.pop(p_pos)
            removed += 1
            last = p_pos - 1  # Adjust the search end for next iteration
            if last < 0:
                break  # No more characters left

        if removed < k:
            continue  # Couldn't remove enough 'pon's

        # Check if the remaining string has 'ponpon' as subsequence
        remaining = ''.join(s_list)
        if has_original(remaining):
            print(k)
            return

    print(-1)

solve()
0