結果

問題 No.291 黒い文字列
コンテスト
ユーザー norioc
提出日時 2025-11-29 15:48:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,203 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 134,860 KB
最終ジャッジ日時 2025-11-29 15:49:00
合計ジャッジ時間 8,461 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict

S = input()

dp = defaultdict(int)
dp[0, 0, 0, 0] = 0
for c in S:
    pp = dp.copy()
    dp, pp = pp, dp
    for key in pp.keys():
        k, u, r, o = key
        nkey = None
        match c:
            case 'K':
                nkey = (k+1, u, r, o)
            case 'U':
                nkey = (k-1, u+1, r, o)
            case 'R':
                nkey = (k, u-1, r+1, o)
            case 'O':
                nkey = (k, u, r-1, o+1)
            case 'I':
                if o > 0:
                    dp[k, u, r, o-1] = max(dp[k, u, r, o-1], pp[k, u, r, o] + 1)

        if nkey is not None and all(0 <= x <= 20 for x in nkey):
            dp[nkey] = max(dp[nkey], pp[key])

        if c == '?':
            nkeys = [
                (k+1, u, r, o),
                (k-1, u+1, r, o),
                (k, u-1, r+1, o),
                (k, u, r-1, o+1),
            ]
            for nkey in nkeys:
                if all(0 <= x <= 20 for x in nkey):
                    dp[nkey] = max(dp[nkey], pp[key])

            # for 'I'
            if o > 0:
                dp[k, u, r, o-1] = max(dp[k, u, r, o-1], pp[k, u, r, o] + 1)

ans = max(dp.values())
print(ans)
0