結果
| 問題 |
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;
}