結果

問題 No.291 黒い文字列
ユーザー lam6er
提出日時 2025-04-16 16:42:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,131 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 401,144 KB
最終ジャッジ日時 2025-04-16 16:44:06
合計ジャッジ時間 9,680 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 TLE * 2 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

S = input().strip()
n = len(S)
max_count = 20  # since maximum possible sequences is 20 (100/5)

# Initialize DP: dp[pos] is a dictionary mapping (a, b, c, d) to the maximum total up to pos
dp = [{} for _ in range(n + 1)]
dp[0][(0, 0, 0, 0)] = 0

for pos in range(n):
    current_char = S[pos]
    possible_choices = []
    if current_char == 'K':
        possible_choices = ['K', 'ignore']
    elif current_char == 'U':
        possible_choices = ['U', 'ignore']
    elif current_char == 'R':
        possible_choices = ['R', 'ignore']
    elif current_char == 'O':
        possible_choices = ['O', 'ignore']
    elif current_char == 'I':
        possible_choices = ['I', 'ignore']
    elif current_char == '?':
        possible_choices = ['K', 'U', 'R', 'O', 'I']
    else:
        possible_choices = ['ignore']
    
    current_states = dp[pos]
    for (a, b, c, d), total in current_states.items():
        for choice in possible_choices:
            if choice == 'ignore':
                new_a, new_b, new_c, new_d = a, b, c, d
                new_total = total
                key = (new_a, new_b, new_c, new_d)
                if key in dp[pos + 1]:
                    if new_total > dp[pos + 1][key]:
                        dp[pos + 1][key] = new_total
                else:
                    dp[pos + 1][key] = new_total
            else:
                if choice == 'K':
                    new_a = min(a + 1, max_count)
                    new_b = b
                    new_c = c
                    new_d = d
                    new_total = total
                elif choice == 'U':
                    if a == 0:
                        continue
                    new_a = a - 1
                    new_b = min(b + 1, max_count)
                    new_c = c
                    new_d = d
                    new_total = total
                elif choice == 'R':
                    if b == 0:
                        continue
                    new_a = a
                    new_b = b - 1
                    new_c = min(c + 1, max_count)
                    new_d = d
                    new_total = total
                elif choice == 'O':
                    if c == 0:
                        continue
                    new_a = a
                    new_b = b
                    new_c = c - 1
                    new_d = min(d + 1, max_count)
                    new_total = total
                elif choice == 'I':
                    if d == 0:
                        continue
                    new_a = a
                    new_b = b
                    new_c = c
                    new_d = d - 1
                    new_total = total + 1
                else:
                    continue  # shouldn't happen
                key = (new_a, new_b, new_c, new_d)
                if key in dp[pos + 1]:
                    if new_total > dp[pos + 1][key]:
                        dp[pos + 1][key] = new_total
                else:
                    dp[pos + 1][key] = new_total

# The answer is the maximum total in the final position
if dp[n]:
    print(max(dp[n].values()))
else:
    print(0)
0