結果

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

ソースコード

diff # 

MOD = 10**9 + 7

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

if R + G + B > N:
    print(0)
    exit()

from collections import defaultdict

prev_dp = defaultdict(int)
prev_dp[(R, G, B, 0, 0)] = 1  # (r, g, b, prev_color, prev_len), count

for i in range(1, N + 1):
    current_dp = defaultdict(int)
    for (r, g, b, prev_color, prev_len), cnt in prev_dp.items():
        # Option 1: choose blank
        current_dp[(r, g, b, 0, 0)] = (current_dp[(r, g, b, 0, 0)] + cnt) % MOD
        
        # Option 2: choose red
        if r > 0:
            if prev_color != 1:
                if prev_color == 0:  # previous was blank
                    new_state = (r-1, g, b, 1, 1)
                    current_dp[new_state] = (current_dp[new_state] + cnt) % MOD
                else:
                    if prev_len < 2:
                        new_len = prev_len + 1
                        new_state = (r-1, g, b, 1, new_len)
                        current_dp[new_state] = (current_dp[new_state] + cnt) % MOD
        
        # Option 3: choose green
        if g > 0:
            if prev_color != 2:
                if prev_color == 0:
                    new_state = (r, g-1, b, 2, 1)
                    current_dp[new_state] = (current_dp[new_state] + cnt) % MOD
                else:
                    if prev_len < 2:
                        new_len = prev_len + 1
                        new_state = (r, g-1, b, 2, new_len)
                        current_dp[new_state] = (current_dp[new_state] + cnt) % MOD
        
        # Option 4: choose blue
        if b > 0:
            if prev_color != 3:
                if prev_color == 0:
                    new_state = (r, g, b-1, 3, 1)
                    current_dp[new_state] = (current_dp[new_state] + cnt) % MOD
                else:
                    if prev_len < 2:
                        new_len = prev_len + 1
                        new_state = (r, g, b-1, 3, new_len)
                        current_dp[new_state] = (current_dp[new_state] + cnt) % MOD
    
    prev_dp = current_dp

result = 0
for (r, g, b, _, _), cnt in prev_dp.items():
    if r == 0 and g == 0 and b == 0:
        result = (result + cnt) % MOD

print(result)
0