結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:46:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,490 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 81,988 KB
実行使用メモリ 277,700 KB
最終ジャッジ日時 2025-06-12 18:47:00
合計ジャッジ時間 4,654 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

# dp[prev_color][run_length][(r_used, g_used, b_used)] = count
dp = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
dp[0][0][(0, 0, 0)] = 1  # Initial state: no color, run_length 0, used colors (0,0,0)

for _ in range(N):
    new_dp = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
    for prev_color in dp:
        for run_length in dp[prev_color]:
            for (r_used, g_used, b_used), cnt in dp[prev_color][run_length].items():
                # Option 1: Leave the current cell blank
                new_color = 0
                new_run = 0
                new_dp[new_color][new_run][(r_used, g_used, b_used)] = (
                    new_dp[new_color][new_run][(r_used, g_used, b_used)] + cnt
                ) % MOD

                # Option 2: Paint the current cell with a color
                for color in [1, 2, 3]:  # 1: Red, 2: Green, 3: Blue
                    if color == prev_color:
                        continue  # Same color cannot be adjacent
                    if prev_color != 0 and run_length >= 2:
                        continue  # Cannot have three consecutive painted cells

                    # Check if we can use this color
                    new_r = r_used + (1 if color == 1 else 0)
                    new_g = g_used + (1 if color == 2 else 0)
                    new_b = b_used + (1 if color == 3 else 0)
                    if new_r > R or new_g > G or new_b > B:
                        continue

                    # Calculate new run length
                    if prev_color == 0:  # Previous was blank, reset run length
                        new_run_length = 1
                    else:  # Continue the run
                        new_run_length = run_length + 1

                    if new_run_length > 2:
                        continue  # Cannot have run length over 2

                    new_dp[color][new_run_length][(new_r, new_g, new_b)] = (
                        new_dp[color][new_run_length][(new_r, new_g, new_b)] + cnt
                    ) % MOD

    dp = new_dp

# Sum all valid states where used colors match R, G, B
result = 0
for prev_color in dp:
    for run_length in dp[prev_color]:
        for (r, g, b), cnt in dp[prev_color][run_length].items():
            if r == R and g == G and b == B:
                result = (result + cnt) % MOD

print(result)
0