結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:40:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,712 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 82,324 KB
実行使用メモリ 277,464 KB
最終ジャッジ日時 2025-06-12 18:40:51
合計ジャッジ時間 4,962 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 7 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

N, R, G, B = map(int, input().split())

from collections import defaultdict

prev_dp = defaultdict(int)
prev_dp[(0, 0, 0, 0, 0)] = 1  # (prev_color, clen, r, g, b)

for _ in range(N):
    current_dp = defaultdict(int)
    for (prev_color, clen, r, g, b), cnt in prev_dp.items():
        # Option 1: Do not paint this column
        new_clen = 0
        new_state = (0, new_clen, r, g, b)
        current_dp[new_state] = (current_dp[new_state] + cnt) % MOD
        
        # Option 2: Paint this column with a color different from previous
        for color in [1, 2, 3]:  # 1: Red, 2: Green, 3: Blue
            if color == prev_color:
                continue  # Same color as previous is not allowed
            
            # Check consecutive length constraint
            if prev_color != 0:  # Previous column was painted
                new_clen_p = clen + 1
                if new_clen_p > 2:
                    continue  # Exceeds maximum consecutive allowed
            else:
                new_clen_p = 1  # Start new consecutive
            
            # Update color counts
            nr = r + (1 if color == 1 else 0)
            ng = g + (1 if color == 2 else 0)
            nb = b + (1 if color == 3 else 0)
            
            if nr > R or ng > G or nb > B:
                continue  # Exceeds required counts
            
            new_state = (color, new_clen_p, nr, ng, nb)
            current_dp[new_state] = (current_dp[new_state] + cnt) % MOD
    
    prev_dp = current_dp

# Sum all states where r=R, g=G, b=B
result = 0
for (pc, clen, r, g, b), cnt in prev_dp.items():
    if r == R and g == G and b == B:
        result = (result + cnt) % MOD

print(result)
0