結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:23:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,246 bytes
コンパイル時間 622 ms
コンパイル使用メモリ 81,224 KB
実行使用メモリ 462,924 KB
最終ジャッジ日時 2025-04-16 00:24:32
合計ジャッジ時間 5,092 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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())
    total = R + G + B
    if total > N:
        print(0)
        return

    # Initialize DP: dp[i][last_color][streak][r][g][b]
    # Using defaultdict to save space
    dp = [defaultdict(int) for _ in range(N+1)]
    # Initial state: at position 0, no color (None), streak 0, remaining R, G, B
    dp[0][(None, 0, R, G, B)] = 1

    for i in range(N):
        current_dp = dp[i]
        next_dp = defaultdict(int)
        for state, ways in current_dp.items():
            last_color, streak, r, g, b = state

            # Option 1: place blank
            new_state = (None, 0, r, g, b)
            next_dp[new_state] = (next_dp[new_state] + ways) % MOD

            # Option 2: place a color
            for color in ['R', 'G', 'B']:
                if color == last_color:
                    continue  # same color is not allowed
                if streak == 2:
                    continue  # cannot place after two consecutive colors

                # Check remaining count
                if color == 'R' and r == 0:
                    continue
                if color == 'G' and g == 0:
                    continue
                if color == 'B' and b == 0:
                    continue

                # Update remaining colors
                new_r, new_g, new_b = r, g, b
                if color == 'R':
                    new_r -= 1
                elif color == 'G':
                    new_g -= 1
                else:
                    new_b -= 1

                # Update streak
                new_streak = 1 if last_color is None else streak + 1
                if new_streak > 2:
                    continue  # cannot have streak > 2

                new_state = (color, new_streak, new_r, new_g, new_b)
                next_dp[new_state] = (next_dp[new_state] + ways) % MOD

        dp[i+1] = next_dp

    # Sum all states where i=N, r=0, g=0, b=0
    result = 0
    for state, ways in dp[N].items():
        _, _, r, g, b = state
        if r == 0 and g == 0 and b == 0:
            result = (result + ways) % MOD
    print(result)

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