結果

問題 No.2738 CPC To F
ユーザー gew1fw
提出日時 2025-06-12 15:15:43
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,057 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,268 KB
実行使用メモリ 96,112 KB
最終ジャッジ日時 2025-06-12 15:16:11
合計ジャッジ時間 2,143 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    s = input[1]
    
    # Precompute is_cpc
    is_cpc = [False] * n
    for j in range(n - 2):
        if s[j] == 'C' and s[j+1] == 'P' and s[j+2] == 'C':
            is_cpc[j] = True
    
    # Precompute possible: suffix array
    possible = [False] * (n + 1)
    possible[n] = False
    for k in range(n-1, -1, -1):
        possible[k] = is_cpc[k] or possible[k+1]
    
    # Collect candidates
    candidates = []
    for i in range(n - 4):
        if s[i] == 'C' and s[i+1] == 'P' and s[i+2] == 'C' and s[i+3] == 'T':
            if s[i+4] == 'F' or possible[i+4]:
                candidates.append(i)
    
    # Sort candidates by end position
    candidates.sort(key=lambda x: x + 4)
    
    # Greedily select non-overlapping intervals
    count = 0
    last_end = -1
    for start in candidates:
        end = start + 4
        if start > last_end:
            count += 1
            last_end = end
    
    print(count)

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