#1102410 (C++17) No.3018 目隠し宝探し

• 問題: No.3018 目隠し宝探し
• ユーザー: eom2357
• 提出日時: 2025-07-02 00:55:51
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 9,024 bytes
• コンパイル時間: 1,196 ms
• コンパイル使用メモリ: 90,888 KB
• 実行使用メモリ: 26,320 KB
• 平均クエリ数: 2.68
• 最終ジャッジ日時: 2025-07-02 00:55:56
• 合計ジャッジ時間: 4,073 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 1
other	AC * 15 WA * 6

コンパイルメッセージ

main.cpp: In function ‘int main()’:
main.cpp:242:37: warning: ‘final_i’ may be used uninitialized [-Wmaybe-uninitialized]
  242 |     std::cout << "! " << final_i << " " << final_j << std::endl;
      |                                     ^~~
main.cpp:31:9: note: ‘final_i’ was declared here
   31 |     int final_i, final_j;
      |         ^~~~~~~
main.cpp:242:44: warning: ‘final_j’ may be used uninitialized [-Wmaybe-uninitialized]
  242 |     std::cout << "! " << final_i << " " << final_j << std::endl;
      |                                            ^~~~~~~
main.cpp:31:18: note: ‘final_j’ was declared here
   31 |     int final_i, final_j;
      |                  ^~~~~~~

ソースコード

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm> // for std::min and std::max

// 標準出力をフラッシュするヘルパー関数
void flush_stdout() {
    std::cout << std::flush;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int H, W;
    std::cin >> H >> W;

    long long d1, d2;

    // 1回目の質問: マス (1, 1)
    std::cout << "? 1 1" << std::endl;
    flush_stdout();
    std::cin >> d1;
    if (d1 == -1) {
        return 0; // エラー終了
    }

    // H=1 の場合、行は確定 (i=1)
    // W=1 の場合、列は確定 (j=1)

    int final_i, final_j;

    if (H == 1 && W == 1) {
        final_i = 1;
        final_j = 1;
    } else if (H == 1) { // H=1の場合、iは確定
        final_i = 1;
        // j を特定するために、マス (1, W) を質問
        std::cout << "? 1 " << W << std::endl;
        flush_stdout();
        std::cin >> d2;
        if (d2 == -1) {
            return 0; // エラー終了
        }

        // d1 = (1-1)^2 + (j-1)^2 = (j-1)^2
        // d2 = (1-1)^2 + (j-W)^2 = (j-W)^2
        // (j-1)^2 = d1
        // (j-W)^2 = d2
        // (j-1)^2 - (j-W)^2 = d1 - d2
        // (j^2 - 2j + 1) - (j^2 - 2Wj + W^2) = d1 - d2
        // -2j + 1 + 2Wj - W^2 = d1 - d2
        // 2j(W-1) = d1 - d2 - 1 + W^2
        // j = (d1 - d2 - 1 + W*W) / (2 * (W-1)) + 1
        
        // よりシンプルな導出:
        // (j-1)^2 = d1
        // j-1 = sqrt(d1)  (j-1 >= 0)
        // j = 1 + sqrt(d1)
        // または
        // j-1 = -sqrt(d1) (j-1 < 0)
        // j = 1 - sqrt(d1)

        // 適応的ジャッジのため、sqrt(d1)はj-1か-(j-1)のどちらかになる
        // (j-1)^2 = d1
        // (j-W)^2 = d2
        // この2つからjを求める
        // j^2 - 2j + 1 = d1
        // j^2 - 2Wj + W^2 = d2
        // 上の式から下の式を引くと
        // (-2j + 2Wj) + (1 - W^2) = d1 - d2
        // 2j(W-1) = d1 - d2 - 1 + W^2
        // j = (d1 - d2 - 1 + W*W) / (2.0 * (W-1)) + 1
        
        // この計算は浮動小数点になるため、整数で扱う場合は注意が必要
        // d1 - (j-1)^2 = 0
        // d2 - (j-W)^2 = 0
        // d1 + 2Wj - W^2 = d2 + 2j - 1 (j^2項が消える)
        // 2j(W-1) = d2 - d1 - 1 + W^2
        // j = (d2 - d1 - 1 + W*W) / (2 * (W-1)) + 1
        
        // W=1ではないので、W-1 > 0
        // d1は(j-1)^2
        // d2は(j-W)^2
        // jを特定するために、もう一つ点を質問する必要はない
        // d1からjの候補を絞り、d2からその候補を検証
        // sqrt(d1) を s1とする。 j = 1 + s1 もしくは j = 1 - s1
        // sqrt(d2) を s2とする。 j = W + s2 もしくは j = W - s2

        // (j-1)^2 = d1 より j-1 = k (k=sqrt(d1) or -sqrt(d1))
        // (j-W)^2 = d2 より j-W = m (m=sqrt(d2) or -sqrt(d2))
        // j = 1 + k
        // j = W + m
        // 1 + k = W + m => k - m = W - 1
        // kとmはそれぞれsqrt(d1)とsqrt(d2)の正負どちらか
        // 4通りの組み合わせを試して、一致するjを探す
        
        for (long long k_val : {static_cast<long long>(std::sqrt(d1)), -static_cast<long long>(std::sqrt(d1))}) {
            if ((k_val * k_val) != d1) continue; // k_valが整数にキャストされた結果なので元のd1と一致するか確認
            long long current_j = 1 + k_val;
            if (current_j >= 1 && current_j <= W) {
                if (((current_j - W) * (current_j - W)) == d2) {
                    final_j = static_cast<int>(current_j);
                    break;
                }
            }
        }

    } else if (W == 1) { // W=1の場合、jは確定
        final_j = 1;
        // i を特定するために、マス (H, 1) を質問
        std::cout << "? " << H << " 1" << std::endl;
        flush_stdout();
        std::cin >> d2;
        if (d2 == -1) {
            return 0; // エラー終了
        }

        // d1 = (i-1)^2 + (1-1)^2 = (i-1)^2
        // d2 = (i-H)^2 + (1-1)^2 = (i-H)^2
        // 上と同様にiを特定
        for (long long k_val : {static_cast<long long>(std::sqrt(d1)), -static_cast<long long>(std::sqrt(d1))}) {
            if ((k_val * k_val) != d1) continue;
            long long current_i = 1 + k_val;
            if (current_i >= 1 && current_i <= H) {
                if (((current_i - H) * (current_i - H)) == d2) {
                    final_i = static_cast<int>(current_i);
                    break;
                }
            }
        }
    } else { // H > 1 かつ W > 1 の場合
        // マス (1, W) を質問して d2 を得る
        // これにより、(i-1)^2 と (j-W)^2 の情報が得られる
        std::cout << "? 1 " << W << std::endl;
        flush_stdout();
        std::cin >> d2;
        if (d2 == -1) {
            return 0; // エラー終了
        }

        // d1 = (i-1)^2 + (j-1)^2
        // d2 = (i-1)^2 + (j-W)^2
        // d1 - d2 = (j-1)^2 - (j-W)^2
        // d1 - d2 = (j^2 - 2j + 1) - (j^2 - 2Wj + W^2)
        // d1 - d2 = -2j + 1 + 2Wj - W^2
        // d1 - d2 = 2j(W-1) + 1 - W^2
        // 2j(W-1) = d1 - d2 - 1 + W^2
        // j = (d1 - d2 - 1 + W*W) / (2.0 * (W-1)) + 1
        
        // 浮動小数点誤差を避けるため、整数で計算
        // (j-1)^2 は d1 - (i-1)^2
        // (j-W)^2 は d2 - (i-1)^2
        // よって、d1 - (i-1)^2 と d2 - (i-1)^2 の差が一定
        // この差を利用してjを決定します。
        // sqrt(d1)とsqrt(d2)を考慮して、jを特定
        
        // (i-1)^2 = A
        // (j-1)^2 = B
        // (j-W)^2 = C
        // A + B = d1
        // A + C = d2

        // C - B = d2 - d1
        // (j-W)^2 - (j-1)^2 = d2 - d1
        // j^2 - 2Wj + W^2 - (j^2 - 2j + 1) = d2 - d1
        // -2Wj + W^2 + 2j - 1 = d2 - d1
        // 2j(1-W) + W^2 - 1 = d2 - d1
        // 2j(1-W) = d2 - d1 - W^2 + 1
        // j = (d2 - d1 - W*W + 1) / (2.0 * (1-W))
        // これでjが求まります。

        // 適応的ジャッジのため、複数の候補がある場合でも、
        // 1つの質問でi座標の候補が2つ、もう1つの質問でj座標の候補が2つ
        // 合計4つの交点候補がある可能性がある。
        // しかし、実際には2つの質問で一意に定まることが多い。

        // 確実な方法: 2点からの距離で円の方程式を立て、交点を求める
        // 宝物の座標を (r, c) とする
        // (r-1)^2 + (c-1)^2 = d1
        // (r-1)^2 + (c-W)^2 = d2
        
        // 上記2式から (r-1)^2 を消去
        // d1 - (c-1)^2 = d2 - (c-W)^2
        // d1 - (c^2 - 2c + 1) = d2 - (c^2 - 2Wc + W^2)
        // d1 - c^2 + 2c - 1 = d2 - c^2 + 2Wc - W^2
        // 2c - 2Wc = d2 - d1 - W^2 + 1
        // 2c(1 - W) = d2 - d1 - W^2 + 1
        // c = (d2 - d1 - W*W + 1) / (2.0 * (1 - W))
        // if (1 - W == 0) (i.e. W == 1) then this formula is invalid
        // W != 1 の場合、上記の式で c が一意に定まる。
        // H != 1 の場合、r を求めるために同様に (1,1) と (H,1) で質問が必要？
        // いいえ、2回で特定する必要がある。

        // d1: (r-1)^2 + (c-1)^2
        // d2: (r-1)^2 + (c-W)^2

        // ここで r と c を直接計算する
        // 実際には2つの質問で (i-1)^2 と (j-1)^2 を特定する。
        // d1 = (i-1)^2 + (j-1)^2
        // d2 = (i-1)^2 + (j-W)^2

        // x = i-1
        // y = j-1
        // z = j-W
        // x^2 + y^2 = d1
        // x^2 + z^2 = d2
        // y = j-1
        // z = j-W = (j-1) - (W-1) = y - (W-1)

        // x^2 + y^2 = d1
        // x^2 + (y - (W-1))^2 = d2

        // (y - (W-1))^2 = d2 - x^2
        // y^2 - 2y(W-1) + (W-1)^2 = d2 - x^2

        // d1 - x^2 - 2y(W-1) + (W-1)^2 = d2 - x^2
        // d1 - 2y(W-1) + (W-1)^2 = d2
        // 2y(W-1) = d1 + (W-1)^2 - d2
        // y = (d1 + (W-1)*(W-1) - d2) / (2.0 * (W-1))
        
        // もし W-1 が 0 なら (W=1の場合)、この式は使えない。
        // 上で W=1 の場合はすでに処理済み。

        long long y_val_times_2_W_minus_1 = d1 + (long long)(W-1)*(W-1) - d2;
        long long divisor_for_y = 2 * (W-1);

        // yが整数であることを確認し、除算
        // y = j-1
        final_j = 1 + static_cast<int>(y_val_times_2_W_minus_1 / divisor_for_y);

        // x^2 = d1 - y^2
        // x^2 = d1 - (final_j - 1)^2
        long long x_squared = d1 - (long long)(final_j - 1)*(final_j - 1);
        final_i = 1 + static_cast<int>(std::sqrt(x_squared));
        // x = i-1 なので、i = 1 + x
        // xは正の値を取るようにすることで、1 <= i <= H の範囲で妥当な値になるはず。
        // 適応的ジャッジのため、sqrt(x_squared)は適切な値になる
    }

    // 解答を出力
    std::cout << "! " << final_i << " " << final_j << std::endl;
    flush_stdout();

    return 0;
}