結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:34:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,701 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 81,936 KB
実行使用メモリ 89,532 KB
最終ジャッジ日時 2025-06-12 21:35:21
合計ジャッジ時間 5,414 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 7 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 10**9 + 7

def main():
    import sys
    N, R, G, B = map(int, sys.stdin.readline().split())

    max_r = R
    max_g = G
    max_b = B

    from collections import defaultdict
    dp = defaultdict(int)
    initial_prev = ' '
    initial_streak = 0
    initial_r = R
    initial_g = G
    initial_b = B
    dp[(0, initial_prev, initial_streak, initial_r, initial_g, initial_b)] = 1

    for i in range(N):
        new_dp = defaultdict(int)
        for state, count in dp.items():
            current_i, prev_color, streak, rem_r, rem_g, rem_b = state

            if current_i != i:
                continue

            colors = ['R', 'G', 'B', ' ']
            for c in colors:
                if c == 'R' and rem_r == 0:
                    continue
                if c == 'G' and rem_g == 0:
                    continue
                if c == 'B' and rem_b == 0:
                    continue

                if c == prev_color and c != ' ':
                    continue

                if c == ' ':
                    new_prev = ' '
                    new_streak = 0
                    new_rem_r = rem_r
                    new_rem_g = rem_g
                    new_rem_b = rem_b
                    new_dp[(i + 1, new_prev, new_streak, new_rem_r, new_rem_g, new_rem_b)] += count
                    new_dp[(i + 1, new_prev, new_streak, new_rem_r, new_rem_g, new_rem_b)] %= MOD
                else:
                    if streak >= 2:
                        continue
                    new_streak = streak + 1 if streak != 0 else 1
                    if new_streak > 3:
                        continue
                    new_prev = c
                    if c == 'R':
                        new_rem_r = rem_r - 1
                        new_rem_g = rem_g
                        new_rem_b = rem_b
                    elif c == 'G':
                        new_rem_r = rem_r
                        new_rem_g = rem_g - 1
                        new_rem_b = rem_b
                    else:  # 'B'
                        new_rem_r = rem_r
                        new_rem_g = rem_g
                        new_rem_b = rem_b - 1
                    new_dp[(i + 1, new_prev, new_streak, new_rem_r, new_rem_g, new_rem_b)] += count
                    new_dp[(i + 1, new_prev, new_streak, new_rem_r, new_rem_g, new_rem_b)] %= MOD
        dp = new_dp

    total = 0
    for state, count in dp.items():
        i = state[0]
        if i == N:
            prev_color, streak, rem_r, rem_g, rem_b = state[1:]
            if rem_r == 0 and rem_g == 0 and rem_b == 0:
                total += count
                total %= MOD
    print(total % MOD)

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