結果
| 問題 |
No.281 門松と魔法(1)
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:07:13 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,335 bytes |
| コンパイル時間 | 984 ms |
| コンパイル使用メモリ | 99,208 KB |
| 実行使用メモリ | 91,772 KB |
| 最終ジャッジ日時 | 2025-05-14 13:08:58 |
| 合計ジャッジ時間 | 4,137 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 15 TLE * 1 -- * 41 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <map>
#include <algorithm>
#include <vector> // Ensure vector is included
using namespace std;
// Define long long type for convenience, as heights and d can be large
typedef long long ll;
// Use a map to store the minimum distance (operations) found so far to reach each state.
// The key is the state represented as a tuple of three heights (h1, h2, h3).
// The value is the minimum number of operations.
// `map` is used here for simplicity and standard compliance. `unordered_map` might be faster
// but requires a custom hash function for tuples.
map<tuple<ll, ll, ll>, ll> dist;
// Function to check if a state (h1, h2, h3) satisfies the problem conditions:
// 1. All three bamboo heights must be distinct.
// 2. The middle bamboo's height (h2) must be strictly the highest or strictly the lowest among the three.
bool check_condition(ll h1, ll h2, ll h3) {
// Check for distinctness
if (h1 == h2 || h1 == h3 || h2 == h3) {
return false; // Heights are not distinct
}
// Check if middle bamboo is strictly the maximum
bool middle_is_max = (h2 > h1 && h2 > h3);
// Check if middle bamboo is strictly the minimum
bool middle_is_min = (h2 < h1 && h2 < h3);
// Return true if either condition (max or min) is met
return middle_is_max || middle_is_min;
}
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll d; // The amount height decreases by magic per operation
cin >> d;
vector<ll> H(3); // Vector to store initial heights H1, H2, H3
cin >> H[0] >> H[1] >> H[2];
// Handle the special case where d = 0.
// If d=0, the magic operation does not change heights (max(0, h-0) = h for h>=0).
// So, we only need to check if the initial heights satisfy the condition.
if (d == 0) {
if (check_condition(H[0], H[1], H[2])) {
cout << 0 << endl; // Initial state is valid, 0 operations needed.
} else {
cout << -1 << endl; // Initial state is invalid, and cannot be changed. Impossible.
}
return 0; // Exit program after handling d=0 case.
}
// Use a priority queue for Dijkstra's algorithm (effectively BFS since edge weights are uniform 1).
// It stores pairs of {cost, state}. `greater<>` makes it a min-priority queue based on cost.
priority_queue<pair<ll, tuple<ll, ll, ll>>, vector<pair<ll, tuple<ll, ll, ll>>>, greater<pair<ll, tuple<ll, ll, ll>>>> pq;
// Create the initial state tuple from input heights.
tuple<ll, ll, ll> initial_state = make_tuple(H[0], H[1], H[2]);
// The distance to the initial state is 0 operations. Store this in the distance map.
dist[initial_state] = 0;
// Push the initial state and its cost (0) into the priority queue.
pq.push({0, initial_state});
ll min_ops = -1; // Variable to store the minimum operations found. Initialize to -1 (signifying impossible/not found yet).
int nodes_expanded_count = 0; // Counter for the number of nodes expanded (processed) from the priority queue.
// Set a limit on the number of nodes expanded to prevent exceeding time or memory limits,
// especially if the state space is huge or finding a solution requires many steps.
// This value is a heuristic based on typical competitive programming constraints. 2 million states is reasonable for 128MB.
const int MAX_NODES_EXPANDED = 2000000;
while (!pq.empty()) {
// Extract the state with the minimum cost from the priority queue.
auto top = pq.top();
pq.pop();
ll current_dist = top.first; // The minimum cost found so far to reach this state.
tuple<ll, ll, ll> current_state = top.second; // The state itself (h1, h2, h3).
// Optimization: Check if we have already processed this state via a path with less or equal cost.
// If the recorded distance in `dist` map for this state is less than `current_dist`,
// it means we found a shorter path earlier and already processed it, so we can skip this instance.
auto it = dist.find(current_state);
// Note: The check `it != dist.end()` is technically redundant if we ensure states are only added to PQ after being put in `dist`.
// But it's safer. The condition `it->second < current_dist` correctly identifies redundant paths.
if (it != dist.end() && it->second < current_dist) {
continue;
}
// Unpack the current state tuple into individual heights h1, h2, h3.
ll h1, h2, h3;
tie(h1, h2, h3) = current_state;
// Check if the current state satisfies the problem conditions.
if (check_condition(h1, h2, h3)) {
min_ops = current_dist; // Found the solution. Record the minimum operations.
break; // Exit the loop as Dijkstra guarantees the first time we extract a valid state, it's via the shortest path.
}
// Increment the count of expanded nodes.
nodes_expanded_count++;
// Check if we exceeded the expansion limit.
if (nodes_expanded_count > MAX_NODES_EXPANDED) {
min_ops = -1; // Ensure result is -1 if limit reached without finding solution.
break; // Stop the search.
}
// Explore neighboring states by applying the magic operation to each of the three bamboos.
vector<ll> current_heights = {h1, h2, h3};
for (int i = 0; i < 3; ++i) { // Iterate through each bamboo (index 0, 1, 2).
ll current_h = current_heights[i];
// If the current height is 0, applying magic won't change it (since d > 0).
// Skip this to avoid redundant processing and potential infinite loops if d=0 (already handled).
if (current_h == 0) {
continue;
}
// Apply the magic operation: new height is max(0, current_height - d).
ll next_h = max(0LL, current_h - d);
// Create the tuple representing the next state.
vector<ll> next_heights = current_heights;
next_heights[i] = next_h; // Update the height of the i-th bamboo.
tuple<ll, ll, ll> next_state = make_tuple(next_heights[0], next_heights[1], next_heights[2]);
// The cost to reach the next state is one more than the cost to reach the current state.
ll new_dist = current_dist + 1;
// Check if the next state has not been visited before, or if the new path found is shorter
// than any previously found path to this state.
auto it_next = dist.find(next_state);
if (it_next == dist.end() || new_dist < it_next->second) {
// Update the minimum distance found to reach `next_state`.
dist[next_state] = new_dist;
// Add the `next_state` and its cost `new_dist` to the priority queue for future exploration.
pq.push({new_dist, next_state});
}
}
}
// Output the minimum number of operations found. If no solution was found (or limit reached), min_ops remains -1.
cout << min_ops << endl;
return 0;
}