#1083796 (C++17) No.584 赤、緑、青の色塗り

• 問題: No.584 赤、緑、青の色塗り
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:01:26
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,504 bytes
• コンパイル時間: 793 ms
• コンパイル使用メモリ: 86,152 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:03:42
• 合計ジャッジ時間: 5,580 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 6
other	AC * 7 TLE * 1 -- * 6

ソースコード

#include <iostream>
#include <vector>
#include <map>

// Define a structure for the state key to be used in the map.
// This improves readability and organization compared to using tuples or vectors directly.
struct StateKey {
    int r, g, b; // Counts of Red, Green, Blue colors used so far
    int p1;      // Color of the last cell (cell i)
    int p2;      // Color of the second to last cell (cell i-1)

    // Colors are represented as integers: 0:Red, 1:Green, 2:Blue, 3:Empty

    // Define the less than operator '<'. This is required for std::map keys 
    // to maintain order and allow efficient lookups.
    bool operator<(const StateKey& other) const {
        // Compare components in a fixed order. If any component differs,
        // the comparison result is determined. If all components match up to the last one,
        // compare the last component.
        if (r != other.r) return r < other.r;
        if (g != other.g) return g < other.g;
        if (b != other.b) return b < other.b;
        if (p1 != other.p1) return p1 < other.p1;
        return p2 < other.p2;
    }
};

// Use std::map to store the DP states. The key is the StateKey struct, 
// and the value is the count of ways to reach that state (long long for potentially large counts).
// We use two maps, `dp[0]` and `dp[1]`, to represent the DP states for the current step (i)
// and the next step (i+1). This technique is often called "ping-pong" or double buffering.
std::map<StateKey, long long> dp[2]; 

// Define the modulus for calculations, as required by the problem statement.
long long MOD = 1000000007;


int main() {
    // Use faster I/O operations by disabling synchronization with C stdio
    // and unlinking cin from cout.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N, R, G, B; // Grid size N, target counts R, G, B
    std::cin >> N >> R >> G >> B;

    // Basic feasibility check: The total number of required colored cells
    // cannot exceed the total number of cells in the grid.
    // If R+G+B > N, it's impossible to satisfy the requirements.
    if (R + G + B > N) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // Initialize the DP. The state before processing the first cell (at index 0) is:
    // 0 Red, 0 Green, 0 Blue cells used.
    // We assume the two fictitious cells before the grid start (-1 and 0) were Empty (color code 3).
    // There is 1 way to reach this initial state.
    dp[0][{0, 0, 0, 3, 3}] = 1; 

    int current_dp_idx = 0; // Index (0 or 1) to access the current DP table
    // The main DP loop iterates N times, corresponding to processing cells 1 through N.
    for (int i = 0; i < N; ++i) { 
        int next_dp_idx = 1 - current_dp_idx; // Index for the DP table for the next step
        dp[next_dp_idx].clear(); // Clear the map for the next state calculation to ensure it's fresh.

        // Optimization: If the current DP table is empty, it means no valid states were reached
        // in the previous step. Thus, no further states can be reached. We can break early.
        if (dp[current_dp_idx].empty()) { 
             break;
        }
        
        // Iterate through all reachable states ending at cell i (stored in dp[current_dp_idx])
        for (auto const& [current_state, count] : dp[current_dp_idx]) {
            // `current_state` contains {r, g, b, p1, p2} information after processing cell i.
            // `count` is the number of ways to reach this state.

            // Unpack state variables from the key for easier access
            int r = current_state.r;
            int g = current_state.g;
            int b = current_state.b;
            int p1 = current_state.p1; // Color of cell i
            int p2 = current_state.p2; // Color of cell i-1

            // Try placing each possible color (R, G, B, E) at the next cell, i+1
            for (int new_p1 = 0; new_p1 < 4; ++new_p1) { // Loop through colors 0:R, 1:G, 2:B, 3:E
                int next_r = r, next_g = g, next_b = b; // Initialize counts for the next state
                bool is_new_cell_colored = (new_p1 != 3); // Check if the new cell is colored or empty

                // Update color counts based on the color being placed at cell i+1
                // Also check if the target count for that color has already been reached.
                if (new_p1 == 0) { // Placing Red
                    if (r >= R) continue; // Cannot place Red if R count is already met/exceeded
                    next_r++;
                } else if (new_p1 == 1) { // Placing Green
                    if (g >= G) continue; // Cannot place Green if G count is already met/exceeded
                    next_g++;
                } else if (new_p1 == 2) { // Placing Blue
                    if (b >= B) continue; // Cannot place Blue if B count is already met/exceeded
                    next_b++;
                }
                // No count change needed if placing an Empty cell (new_p1 == 3)

                // Check rule constraints before adding the state transition:

                // Constraint 1: No adjacent identical colors.
                // Compare the color of cell i+1 (new_p1) with the color of cell i (p1).
                // This check only applies if the new cell is colored.
                if (is_new_cell_colored && new_p1 == p1) {
                    continue; // Invalid transition: results in RR, GG, or BB pattern
                }

                // Constraint 2: No three consecutive colored cells.
                // Check if placing `new_p1` at cell i+1 would create a sequence of three colored cells.
                // This happens if cell i+1, cell i, and cell i-1 are all colored.
                bool is_p1_colored = (p1 != 3); // Was cell i colored?
                bool is_p2_colored = (p2 != 3); // Was cell i-1 colored?

                if (is_new_cell_colored && is_p1_colored && is_p2_colored) {
                     continue; // Invalid transition: results in a CCC pattern
                }
                
                // If all constraints are satisfied, this transition is valid.
                // Construct the StateKey for the resulting state after placing `new_p1` at cell i+1.
                // The new state has updated counts {next_r, next_g, next_b}.
                // The last color is `new_p1`. The second to last color is the previous last color `p1`.
                StateKey next_state = {next_r, next_g, next_b, new_p1, p1};
                
                // Add the number of ways (`count`) from the current path to the total count
                // for the `next_state` in the `next_dp_idx` table. Perform addition modulo MOD.
                dp[next_dp_idx][next_state] = (dp[next_dp_idx][next_state] + count) % MOD;
            }
        }
        // After processing all states in the current DP table, switch context for the next iteration.
        current_dp_idx = next_dp_idx; 
    }

    // After the loop finishes (N iterations), dp[current_dp_idx] contains states for the full grid of size N.
    long long total_ways = 0;
    // Sum up the counts for all final states that exactly match the target R, G, B counts.
    for (auto const& [final_state, count] : dp[current_dp_idx]) {
        if (final_state.r == R && final_state.g == G && final_state.b == B) {
            total_ways = (total_ways + count) % MOD;
        }
    }

    // Output the final answer.
    std::cout << total_ways << std::endl; 

    return 0;
}