#1083886 (C++17) No.281 門松と魔法(1)

• 問題: 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;
}