結果

問題 No.2738 CPC To F
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:35:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,056 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 193 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 93,216 KB
最終ジャッジ日時 2025-03-31 17:36:27
合計ジャッジ時間 2,413 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n = int(input())
s = input().strip()

# Step 1: Count original CPCTF substrings
original_count = 0
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' and s[i+4] == 'F':
        original_count += 1

# Step 2: Collect all valid CPC positions that can generate CPCTF when converted
valid_cpc = []
for i in range(n - 2):
    if s[i] == 'C' and s[i+1] == 'P' and s[i+2] == 'C':
        # Check if the previous characters form T followed by CPC
        if i >= 4:
            if (s[i-1] == 'T' and
                s[i-4] == 'C' and
                s[i-3] == 'P' and
                s[i-2] == 'C'):
                valid_cpc.append( (i, i+2) )

# Step 3: Find the maximum non-overlapping intervals using greedy algorithm
conversion_count = 0
if valid_cpc:
    # Sort intervals by their end points
    valid_cpc.sort(key=lambda x: x[1])
    last_end = -1
    for start, end in valid_cpc:
        if start > last_end:
            conversion_count += 1
            last_end = end

print(original_count + conversion_count)
0