結果

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

ソースコード

diff #
raw source code 

from collections import defaultdict


def encode(key):
    k, u, r, o = key
    h = (min(k, 20) << 24) | (min(u, 20) << 16) | (min(r, 20) << 8) | min(o, 20)
    return h


def decode(h):
    o = h & 0xff
    r = (h >> 8) & 0xff
    u = (h >> 16) & 0xff
    k = (h >> 24) & 0xff
    return k, u, r, o


S = input()

dp = defaultdict(int)
dp[encode((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 = decode(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[encode((k, u, r, o-1))] = max(dp[encode((k, u, r, o-1))], pp[key] + 1)

        if nkey is not None and all(x >= 0 for x in nkey):
            dp[encode(nkey)] = max(dp[encode(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(x >= 0 for x in nkey):
                    dp[encode(nkey)] = max(dp[encode(nkey)], pp[key])

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

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