結果

問題 No.2738 CPC To F
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:02:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,523 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 96,308 KB
最終ジャッジ日時 2025-04-16 00:03:57
合計ジャッジ時間 2,209 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

marked = [False] * n
original_count = 0

# Mark positions covered by original CPCTF
i = 0
while i <= n - 5:
    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
        # Mark the positions from i to i+4
        for j in range(i, i+5):
            if j < n:
                marked[j] = True
        i += 5  # Skip ahead to avoid overlapping
    else:
        i += 1

candidates = []

# Collect all CPC candidates not in marked regions and check their preceding characters
for j in range(n - 2):
    if s[j] == 'C' and s[j+1] == 'P' and s[j+2] == 'C':
        # Check if any of j, j+1, j+2 is marked
        if marked[j] or marked[j+1] or marked[j+2]:
            continue
        # Check if the preceding four characters form C P C T
        if j >= 4:
            if s[j-4] == 'C' and s[j-3] == 'P' and s[j-2] == 'C' and s[j-1] == 'T':
                # Add the interval [j, j+2]
                candidates.append((j, j + 2))

# Now apply interval scheduling to select maximum non-overlapping intervals
conversion_count = 0
if candidates:
    # Sort by end position
    candidates.sort(key=lambda x: x[1])
    conversion_count = 1
    last_end = candidates[0][1]
    for i in range(1, len(candidates)):
        current_start, current_end = candidates[i]
        if current_start > last_end:
            conversion_count += 1
            last_end = current_end

answer = original_count + conversion_count
print(answer)
0