結果
問題 |
No.584 赤、緑、青の色塗り
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:27:28 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,490 bytes |
コンパイル時間 | 419 ms |
コンパイル使用メモリ | 82,720 KB |
実行使用メモリ | 277,724 KB |
最終ジャッジ日時 | 2025-06-12 13:33:19 |
合計ジャッジ時間 | 5,388 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 7 TLE * 1 -- * 6 |
ソースコード
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)