結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:25:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,367 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 285,948 KB
最終ジャッジ日時 2025-03-31 17:25:55
合計ジャッジ時間 4,995 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 7 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    from collections import defaultdict

    N, R, G, B = map(int, sys.stdin.readline().split())
    S = R + G + B
    if S > N:
        print(0)
        return
    
    # Check if any color exceeds maximum possible count
    max_single = (N + 1) // 2
    if R > max_single or G > max_single or B > max_single:
        print(0)
        return
    
    # Initialize DP with defaultdict for states (r_used, g_used, b_used, prev_color, cont) : count
    # prev_color: 0-R, 1-G, 2-B, 3-Empty
    current_dp = defaultdict(int)
    # Initial state: 0 used, prev_color is 3 (empty), cont 0
    current_dp[(0, 0, 0, 3, 0)] = 1
    
    for _ in range(N):
        next_dp = defaultdict(int)
        for (r, g, b, prevc, cont), cnt in current_dp.items():
            # Option 1: Paint empty
            key_empty = (r, g, b, 3, 0)
            next_dp[key_empty] = (next_dp[key_empty] + cnt) % MOD
            
            # Option 2: Paint a color if possible
            for c in [0, 1, 2]:  # 0-R, 1-G, 2-B
                # Check color availability
                required = [0, 0, 0]
                required[c] = 1
                new_r = r + required[0]
                new_g = g + required[1]
                new_b = b + required[2]
                if new_r > R or new_g > G or new_b > B:
                    continue
                
                # Check previous color
                if prevc != 3 and prevc == c:
                    continue  # same color as previous
                
                # Calculate new consecutive count
                if prevc == 3:  # previous was empty
                    new_cont = 1
                else:
                    new_cont = cont + 1
                    if new_cont > 2:
                        continue  # can't have more than 2 consecutive colors
                
                # Add the new state to next_dp
                new_prevc = c
                key = (new_r, new_g, new_b, new_prevc, new_cont)
                next_dp[key] = (next_dp[key] + cnt) % MOD
        
        current_dp = next_dp
    
    # Collect all states where r = R, g = G, b = B
    total = 0
    for (r, g, b, prevc, cont), cnt in current_dp.items():
        if r == R and g == G and b == B:
            total = (total + cnt) % MOD
    print(total)

if __name__ == "__main__":
    main()
0