結果

問題 No.602 隠されていたゲーム2
ユーザー qwewe
提出日時 2025-05-14 13:08:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 7,412 bytes
コンパイル時間 1,179 ms
コンパイル使用メモリ 108,824 KB
実行使用メモリ 9,368 KB
最終ジャッジ日時 2025-05-14 13:09:50
合計ジャッジ時間 2,371 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cmath> // For std::abs
#include <unordered_set>
#include <algorithm> // For std::sort, std::lower_bound

/*
Problem Analysis:
We need to find the minimum number of moves (0, 1, or 2) to get from (0, 0) to (x, y) on an infinite grid.
A move involves traveling a Manhattan distance equal to one of the given values d_1, ..., d_n.
If it's impossible to reach (x, y) in 2 moves or less, output -1.

Manhattan Distance: |x1 - x2| + |y1 - y2|

Let D = |x| + |y| be the Manhattan distance from the origin (0, 0) to the target (x, y).

Check moves in increasing order:

Case 0 moves:
Possible only if the start and target points are the same. Since we start at (0, 0), this is possible iff (x, y) = (0, 0), which means D = 0.

Case 1 move:
Possible if we can move directly from (0, 0) to (x, y). This requires the Manhattan distance D = |x| + |y| to be one of the allowed move distances d_i. Check if D exists in the set {d_1, ..., d_n}.

Case 2 moves:
Possible if there exists an intermediate point (x1, y1) such that we can move from (0, 0) to (x1, y1) using distance d_i, and then from (x1, y1) to (x, y) using distance d_j.
This means:
1. |x1 - 0| + |y1 - 0| = |x1| + |y1| = d_i
2. |x - x1| + |y - y1| = d_j
for some d_i, d_j from the allowed set.

It's a known property that such an intermediate point (x1, y1) exists if and only if the following conditions hold for the target distance D = |x| + |y| and the chosen distances d_i, d_j:
1. Triangle Inequality: D <= d_i + d_j
2. Reverse Triangle Inequality: D >= |d_i - d_j|
3. Parity Condition: D % 2 == (d_i + d_j) % 2

These conditions capture the geometric constraints (intersection of Manhattan distance boundaries) and the grid movement property (parity of distance corresponds to parity of change in coordinate sum).

To efficiently check for Case 2:
We need to determine if there exists *any* pair (d_i, d_j) from the set {d_1, ..., d_n} that satisfies the three conditions.
We can iterate through each possible first move distance d_i. For a fixed d_i, we need to find if there exists a second move distance d_j such that:
  L <= d_j <= R   where L = |D - d_i| and R = D + d_i. (These combine conditions 1 and 2)
  And d_j must satisfy the parity condition: d_j % 2 == (D - d_i + 2) % 2. (This is condition 3 rearranged).

To find such a d_j efficiently:
- Separate the allowed distances into two lists: d_even (containing even d_k) and d_odd (containing odd d_k).
- Sort both lists.
- For each d_i:
    - Calculate L and R.
    - Determine the required parity P for d_j (0 for even, 1 for odd).
    - Select the appropriate list (d_even or d_odd) based on P.
    - Use binary search (specifically `std::lower_bound`) on the selected sorted list to find the first element `d_k` that is >= L.
    - If such an element `d_k` is found (`it != search_vec.end()`) and `d_k` is also <= R, then we have found a valid d_j. The pair (d_i, d_k) satisfies all conditions. We can conclude that 2 moves are possible.

If we iterate through all d_i and find no such pair, then it's impossible to reach (x, y) in 2 moves.

Implementation Details:
- Use `long long` for coordinates (x, y), distances (d_i), and intermediate calculations (D, L, R) because values can reach up to 2*10^9 or 3*10^9.
- Use `std::unordered_set` for efficient checking in Case 1.
- Use `std::vector` to store distances and categorized lists.
- Use `std::sort` and `std::lower_bound` from `<algorithm>`.
- Use `std::abs` from `<cmath>` for absolute values.
*/

int main() {
    // Optimize C++ standard streams for faster I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // Number of allowed move distances
    std::cin >> n;

    std::vector<long long> d(n); // Store all original distances d_i
    std::unordered_set<long long> d_set; // Hash set for fast O(1) average lookup (for 1-move check)
    std::vector<long long> d_even; // Store even distances
    std::vector<long long> d_odd;  // Store odd distances

    // Read distances, populate the hash set, and categorize into even/odd vectors
    for (int i = 0; i < n; ++i) {
        std::cin >> d[i];
        d_set.insert(d[i]);
        if (d[i] % 2 == 0) {
            d_even.push_back(d[i]);
        } else {
            d_odd.push_back(d[i]);
        }
    }

    long long x, y; // Target coordinates
    std::cin >> x >> y;

    // Calculate the target Manhattan distance D = |x| + |y|
    long long target_dist = std::abs(x) + std::abs(y);

    // Check Case 0: Target is the origin
    if (target_dist == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // Check Case 1: Target reachable in one move
    // Check if the target distance D exists in the set of allowed distances
    if (d_set.count(target_dist)) {
        std::cout << 1 << std::endl;
        return 0;
    }

    // Check Case 2: Target reachable in two moves
    // Sort the even and odd distance lists to enable binary search
    std::sort(d_even.begin(), d_even.end());
    std::sort(d_odd.begin(), d_odd.end());

    bool possible_in_2_moves = false;
    // Iterate through each possible distance d_i for the first move
    for (int i = 0; i < n; ++i) {
        long long d_i = d[i]; // Current distance for the first move
        
        // Calculate the required range [L, R] for the second move distance d_j
        long long L = std::abs(target_dist - d_i); // Lower bound for d_j based on reverse triangle inequality
        long long R = target_dist + d_i;         // Upper bound for d_j based on triangle inequality
        
        // Determine the required parity P for d_j based on the overall parity condition
        // D % 2 == (d_i % 2 + d_j % 2) % 2  =>  d_j % 2 == (D % 2 - d_i % 2 + 2) % 2
        int required_parity = (int)((target_dist % 2 - d_i % 2 + 2) % 2); // 0 for even, 1 for odd

        // Select the appropriate sorted list (even or odd distances) to search within
        std::vector<long long>& search_vec = (required_parity == 0) ? d_even : d_odd;
        
        // Perform search only if the relevant list (even or odd) is not empty
        if (!search_vec.empty()) {
            // Use std::lower_bound to find the first element in the sorted list that is >= L
            // This is the smallest potential candidate for d_j that satisfies the lower bound L
            auto it = std::lower_bound(search_vec.begin(), search_vec.end(), L);

            // Check if such an element was found (iterator `it` is not past the end of the vector)
            // And check if the found element `*it` also satisfies the upper bound R
            if (it != search_vec.end()) {
                long long d_j = *it; // The candidate distance found by lower_bound
                if (d_j <= R) {
                    // If d_j is within the range [L, R], we have found a valid pair (d_i, d_j)
                    // This means it's possible to reach the target in 2 moves.
                    possible_in_2_moves = true;
                    break; // Exit the loop early, as we've found the minimum moves (which is 2)
                }
            }
        }
    }

    // Output the result based on whether a 2-move solution was found
    if (possible_in_2_moves) {
        std::cout << 2 << std::endl;
    } else {
        // If not possible in 0, 1, or 2 moves, output -1
        std::cout << -1 << std::endl;
    }

    return 0;
}
0