結果
| 問題 |
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 |
ソースコード
#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;
}