結果

問題 No.291 黒い文字列
ユーザー lam6er
提出日時 2025-03-26 15:45:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,603 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 275,064 KB
最終ジャッジ日時 2025-03-26 15:46:02
合計ジャッジ時間 8,518 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

s = input().strip()

current_dp = defaultdict(int)
current_dp[(0, 0, 0, 0)] = 0  # (c1, c2, c3, c4) -> total

for c in s:
    next_dp = defaultdict(int)
    for state in current_dp:
        c1, c2, c3, c4 = state
        current_total = current_dp[state]
        
        possible_uses = []
        if c == '?':
            possible_uses = ['K', 'U', 'R', 'O', 'I']
        else:
            if c in {'K', 'U', 'R', 'O', 'I'}:
                possible_uses.append(c)
        possible_uses.append(None)  # option to not use the character
        
        for use in possible_uses:
            new_c1 = c1
            new_c2 = c2
            new_c3 = c3
            new_c4 = c4
            new_total = current_total
            
            if use == 'K':
                new_c1 += 1
            elif use == 'U':
                if new_c1 > 0:
                    new_c1 -= 1
                    new_c2 += 1
            elif use == 'R':
                if new_c2 > 0:
                    new_c2 -= 1
                    new_c3 += 1
            elif use == 'O':
                if new_c3 > 0:
                    new_c3 -= 1
                    new_c4 += 1
            elif use == 'I':
                if new_c4 > 0:
                    new_c4 -= 1
                    new_total += 1
            # else: use is None, do nothing
            
            key = (new_c1, new_c2, new_c3, new_c4)
            if next_dp[key] < new_total:
                next_dp[key] = new_total
    current_dp = next_dp

if current_dp:
    print(max(current_dp.values()))
else:
    print(0)
0