結果

問題 No.584 赤、緑、青の色塗り
ユーザー qwewe
提出日時 2025-05-14 13:12:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 10,056 bytes
コンパイル時間 962 ms
コンパイル使用メモリ 94,712 KB
実行使用メモリ 14,756 KB
最終ジャッジ日時 2025-05-14 13:13:36
合計ジャッジ時間 4,712 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 6
other AC * 7 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <vector>
#include <map>
#include <tuple> // Include tuple header
#include <vector> // Use std::vector

using namespace std;

// Define StateKey as a tuple of three integers (r, g, b) representing counts of Red, Green, Blue cells used.
using StateKey = tuple<int, int, int>; 

long long N; // Number of cells in the row
int R, G, B; // Required number of Red, Green, Blue cells
long long MOD = 1000000007; // Modulo value

// State representation indices:
// These indices represent the state of the suffix of the currently built sequence.
// They capture information about the last one or two cells needed to check constraints.
// 0: ends in W (_W) - The last cell is blank.
// 1: ends in R, preceded by W (WR) - Last cell is Red, previous is Blank.
// 2: ends in G, preceded by W (WG) - Last cell is Green, previous is Blank.
// 3: ends in B, preceded by W (WB) - Last cell is Blue, previous is Blank.
// 4: ends in R, preceded by G (GR) - Last two cells are Green then Red.
// 5: ends in R, preceded by B (BR) - Last two cells are Blue then Red.
// 6: ends in G, preceded by R (RG) - Last two cells are Red then Green.
// 7: ends in G, preceded by B (BG) - Last two cells are Blue then Green.
// 8: ends in B, preceded by R (RB) - Last two cells are Red then Blue.
// 9: ends in B, preceded by G (GB) - Last two cells are Green then Blue.
const int NUM_STATES = 10;

// Use map for DP state storage. The key is StateKey (r, g, b).
// The value is a vector of size NUM_STATES storing the number of ways to reach this (r,g,b) count ending in each of the 10 suffix states.
// We use two maps to represent dp[i] and dp[i-1] to save memory.
map<StateKey, vector<long long>> dp[2];


int main() {
    // Faster IO operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input values
    cin >> N >> R >> G >> B;

    // Basic check for non-negative counts. Problem constraints say R,G,B >= 0 anyway.
    if (R < 0 || G < 0 || B < 0) { 
         cout << 0 << endl;
         return 0;
    }
    
    // Initialize DP state
    int current = 0; // Index for the current DP table (dp[i])
    // Base case: At step i=0 (empty prefix), we have used 0 R, G, B cells.
    // The state conceptually ends in W (blank), so we initialize state 0 count to 1.
    StateKey initial_key = make_tuple(0, 0, 0);
    dp[current][initial_key] = vector<long long>(NUM_STATES, 0); // Initialize vector with zeros
    dp[current][initial_key][0] = 1; // There's 1 way to have an empty prefix (state 0)

    // Iterate N times, processing one cell at a time from i=0 to N-1
    for (int i = 0; i < N; ++i) {
        int next = 1 - current; // Index for the next DP table (dp[i+1])
        dp[next].clear(); // Clear the map for the next step before filling it

        // Iterate through all reachable states (r, g, b) at the current step i
        for (auto const& [key, state_values] : dp[current]) {
            int r, g, b;
            tie(r, g, b) = key; // Extract current counts r, g, b from the key
            
            // Iterate through all 10 possible suffix states for this (r, g, b) count
            for (int state_idx = 0; state_idx < NUM_STATES; ++state_idx) {
                // If the number of ways to reach this state is 0, skip calculation
                if (state_values[state_idx] == 0) continue; 

                long long current_ways = state_values[state_idx]; // Number of ways to reach this state

                // Try adding a Blank cell (W)
                // Always possible regardless of the previous state. The new state ends in W (state 0). Counts r,g,b unchanged.
                {
                   StateKey next_key = make_tuple(r, g, b);
                   // Ensure the entry for next_key exists in the dp[next] map. If not, create it and initialize with zeros.
                   if (dp[next].find(next_key) == dp[next].end()) {
                       dp[next][next_key] = vector<long long>(NUM_STATES, 0);
                   }
                   // Add current_ways to the count for state 0 at (r,g,b) in the next step.
                   dp[next][next_key][0] = (dp[next][next_key][0] + current_ways) % MOD;
                }

                // Try adding a Red cell (R)
                if (r + 1 <= R) { // Check if we have not exceeded the required count R
                    bool possible = true;
                    int next_state_idx = -1;
                    
                    // Constraint 6: Cannot have RR. Check if the current state ends in R.
                    // States ending in R are 1 (WR), 4 (GR), 5 (BR).
                    if (state_idx == 1 || state_idx == 4 || state_idx == 5) possible = false; 
                    // Constraint 8: Cannot have 3 consecutive colored cells. Check if current state ends in 2 colored cells.
                    // States ending in 2 colored cells are 4 through 9.
                    if (state_idx >= 4) possible = false; 

                    if (possible) {
                        // Determine the next state index based on the current state
                        if (state_idx == 0) next_state_idx = 1;      // Current ends W (_W), add R -> WR (state 1)
                        else if (state_idx == 2) next_state_idx = 4; // Current ends G (WG), add R -> WGR (state 4)
                        else if (state_idx == 3) next_state_idx = 5; // Current ends B (WB), add R -> WBR (state 5)
                        // If current state index is 1, or 4..9, 'possible' would be false.
                         
                         if (next_state_idx != -1) { // If a valid transition exists
                            StateKey next_key = make_tuple(r + 1, g, b); // Update counts: r+1
                            // Ensure entry exists for next_key
                            if (dp[next].find(next_key) == dp[next].end()) {
                                dp[next][next_key] = vector<long long>(NUM_STATES, 0);
                            }
                            // Add ways to the corresponding next state
                            dp[next][next_key][next_state_idx] = (dp[next][next_key][next_state_idx] + current_ways) % MOD;
                        }
                    }
                }
                
                // Try adding a Green cell (G)
                 if (g + 1 <= G) { // Check G budget
                     bool possible = true;
                     int next_state_idx = -1;

                     // Constraint 6: Cannot have GG. Check if current state ends in G.
                     // States ending in G are 2 (WG), 6 (RG), 7 (BG).
                     if (state_idx == 2 || state_idx == 6 || state_idx == 7) possible = false; 
                     // Constraint 8: Check if current state ends in 2 colored cells.
                     if (state_idx >= 4) possible = false; 

                     if (possible) {
                         if (state_idx == 0) next_state_idx = 2;      // W -> WG (state 2)
                         else if (state_idx == 1) next_state_idx = 6; // WR -> WRG (state 6)
                         else if (state_idx == 3) next_state_idx = 7; // WB -> WBG (state 7)
                         
                         if (next_state_idx != -1) {
                            StateKey next_key = make_tuple(r, g + 1, b); // Update counts: g+1
                            if (dp[next].find(next_key) == dp[next].end()) {
                                dp[next][next_key] = vector<long long>(NUM_STATES, 0);
                            }
                            dp[next][next_key][next_state_idx] = (dp[next][next_key][next_state_idx] + current_ways) % MOD;
                         }
                     }
                 }

                // Try adding a Blue cell (B)
                 if (b + 1 <= B) { // Check B budget
                     bool possible = true;
                     int next_state_idx = -1;

                     // Constraint 6: Cannot have BB. Check if current state ends in B.
                     // States ending in B are 3 (WB), 8 (RB), 9 (GB).
                     if (state_idx == 3 || state_idx == 8 || state_idx == 9) possible = false;
                     // Constraint 8: Check if current state ends in 2 colored cells.
                     if (state_idx >= 4) possible = false;

                     if (possible) {
                         if (state_idx == 0) next_state_idx = 3; // W -> WB (state 3)
                         else if (state_idx == 1) next_state_idx = 8; // WR -> WRB (state 8)
                         else if (state_idx == 2) next_state_idx = 9; // WG -> WGB (state 9)
                         
                         if (next_state_idx != -1) {
                            StateKey next_key = make_tuple(r, g, b + 1); // Update counts: b+1
                             if (dp[next].find(next_key) == dp[next].end()) {
                                 dp[next][next_key] = vector<long long>(NUM_STATES, 0);
                             }
                            dp[next][next_key][next_state_idx] = (dp[next][next_key][next_state_idx] + current_ways) % MOD;
                         }
                     }
                 }
            }
        }
        current = next; // Switch dp table index for the next iteration
    }

    // Calculate the final answer
    long long total_ways = 0;
    StateKey final_key = make_tuple(R, G, B); // The target state with exact counts R, G, B
    
    // Check if the target state (R, G, B) is reachable after N steps
    if (dp[current].count(final_key)) { 
        // If reachable, get the vector of counts for the 10 suffix states
        const vector<long long>& final_state_values = dp[current].at(final_key); // Use .at() for const access
        // Sum up the ways for all possible ending states
        for (int state_idx = 0; state_idx < NUM_STATES; ++state_idx) {
            total_ways = (total_ways + final_state_values[state_idx]) % MOD;
        }
    }

    // Output the final answer
    cout << total_ways << endl;

    return 0;
}
0