結果

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

ソースコード

diff # 

def main():
    import sys
    from functools import lru_cache

    n = int(sys.stdin.readline())
    s = sys.stdin.readline().strip()

    if n < 6:
        print(-1)
        return

    required_deletions = n - 6
    max_a = required_deletions // 3
    max_a_possible = max_a if max_a >= 0 else 0

    target = "ponpon"

    @lru_cache(maxsize=None)
    def dp(i, j, a_rem, b_rem):
        if j == len(target) and a_rem == 0 and b_rem == 0:
            return i == len(s)
        if i >= len(s):
            return False
        
        res = False
        
        if j < len(target) and s[i] == target[j]:
            res = dp(i + 1, j + 1, a_rem, b_rem)
            if res:
                return True
        
        if a_rem > 0 and i + 2 < len(s) and s[i] == 'p' and s[i+1] == 'o' and s[i+2] == 'n':
            res = res or dp(i + 3, j, a_rem - 1, b_rem)
            if res:
                return True
        
        if b_rem > 0:
            res = res or dp(i + 1, j, a_rem, b_rem - 1)
            if res:
                return True
        
        return res

    for a in range(max_a_possible, -1, -1):
        b = required_deletions - 3 * a
        if b < 0:
            continue
        if dp(0, 0, a, b):
            print(a)
            return

    print(-1)

if __name__ == "__main__":
    main()
0