結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:22:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,657 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,756 KB
実行使用メモリ 276,928 KB
最終ジャッジ日時 2025-03-20 20:25:00
合計ジャッジ時間 4,902 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

current_dp = defaultdict(lambda: defaultdict(int))
current_dp[(None, 0)][(0, 0, 0)] = 1

for _ in range(n):
    next_dp = defaultdict(lambda: defaultdict(int))
    for (prev_color, streak), color_counts in current_dp.items():
        for (r, g, b), cnt in color_counts.items():
            # Option 1: leave blank
            key = (None, 0)
            next_dp[key][(r, g, b)] = (next_dp[key][(r, g, b)] + cnt) % MOD
            
            # Option 2: paint with color 'R', 'G', or 'B'
            for color in ['R', 'G', 'B']:
                if prev_color == color:
                    continue
                # Calculate new_streak
                if prev_color is None:
                    new_streak = 1
                else:
                    new_streak = streak + 1
                if new_streak > 2:
                    continue
                # Update color counts
                dr = 1 if color == 'R' else 0
                dg = 1 if color == 'G' else 0
                db = 1 if color == 'B' else 0
                nr = r + dr
                ng = g + dg
                nb = b + db
                if nr > R or ng > G or nb > B:
                    continue
                key_new = (color, new_streak)
                next_dp[key_new][(nr, ng, nb)] = (next_dp[key_new][(nr, ng, nb)] + cnt) % MOD
    current_dp = next_dp

result = 0
for (prev_color, streak), color_counts in current_dp.items():
    for (r, g, b), cnt in color_counts.items():
        if r == R and g == G and b == B:
            result = (result + cnt) % MOD

print(result)
0