結果

問題 No.291 黒い文字列
ユーザー gew1fw
提出日時 2025-06-12 20:55:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,149 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 54,456 KB
最終ジャッジ日時 2025-06-12 20:59:23
合計ジャッジ時間 2,445 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

def max_kuroi_subsequences(s):
    target = "KUROI"
    counts = {c: 0 for c in target}
    for c in s:
        if c in counts:
            counts[c] += 1
    M = s.count('?')

    # Step 1: Compute maximum possible t based on counts and M
    sum_counts = sum(counts[c] for c in target)
    max_t = (sum_counts + M) // 5
    low, high = 0, max_t
    best_t = 0
    while low <= high:
        mid = (low + high) // 2
        needed = 0
        for c in target:
            if counts[c] < mid:
                needed += (mid - counts[c])
                if needed > M:
                    break
        if needed <= M:
            best_t = mid
            low = mid + 1
        else:
            high = mid - 1
    t = best_t

    # Step 2: Compute the number of subsequences using DP
    dp = [0] * (len(target) + 1)
    dp[0] = 1
    for c in s:
        for i in reversed(range(len(target))):
            if c == target[i] or c == '?':
                dp[i+1] += dp[i]
    dp_result = dp[len(target)]

    # The answer is the minimum of t and dp_result
    return min(t, dp_result)

# Read input
s = input().strip()
print(max_kuroi_subsequences(s))
0