概要

平面上に配置された \(N\) 個の集落から、指定された集落 \(C_k\) を基準点とし、そこからすべての集落へのユークリッド距離（切り捨て）の合計を求めるクエリに \(Q\) 回答える問題です。

考察

素朴なアプローチ

最も単純な方法は、各クエリ \(k\) が与えられるたびに、集落 \(C_k\) と他のすべての集落 \(j\) との距離を計算することです。 この場合、1つのクエリあたり \(O(N)\) の計算量がかかります。クエリ数は \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となります。

制約を見ると、\(N \le 2000\)、\(Q \le 2 \times 10^5\) です。 最悪の場合、計算回数は \(2000 \times (2 \times 10^5) = 4 \times 10^8\) 回（4億回）程度となり、さらに平方根の計算などの重い処理が含まれるため、実行時間制限（通常 2.0 秒）に間に合わず TLE (Time Limit Exceeded) となってしまいます。

効率的なアプローチ（事前計算）

ここで、クエリ数 \(Q\) に比べて集落の数 \(N\) が比較的少ない（\(N \le 2000\)）ことに注目します。 基地になり得る候補は \(N\) 個しかありません。したがって、「あらかじめすべての集落を基地とした場合の答えを計算しておく（事前計算）」 というアプローチが有効です。

集落のすべてのペア \((i, j)\) の組み合わせは \(\frac{N(N-1)}{2}\) 通りあります。\(N = 2000\) のとき、このペアの数は約 \(2 \times 10^6\)（200万）通りです。 すべてのペアについて距離を計算し、各集落の合計値に足し合わせていく処理は \(O(N^2)\) の時間で行うことができます。

事前計算をしておけば、各クエリ \(C_k\) に対しては、あらかじめ計算しておいた配列の値を参照するだけで \(O(1)\) で回答できます。これにより、全体の計算量を \(O(N^2 + Q)\) まで削減することができ、実行時間制限に余裕で間に合わせることができます。

アルゴリズム

1. 初期化 各集落 \(i\) からの距離の合計を記録する配列 ans（サイズ \(N\)、初期値 \(0\)）を用意します。

2. 事前計算 (\(O(N^2)\)) すべての集落のペア \((i, j)\) （ただし \(i < j\)）について以下を行います。

   • 2点間の距離の平方 \(dist\_sq = (X_i - X_j)^2 + (Y_i - Y_j)^2\) を計算します。
   • その平方根の床関数 \(d = \lfloor \sqrt{dist\_sq} \rfloor\) を求めます。
   • 集落 \(i\) と集落 \(j\) のそれぞれの合計値に \(d\) を加算します（ans[i] += d, ans[j] += d）。

3. クエリ処理 (\(O(Q)\)) 各クエリで集落 \(C_k\) が与えられたら、事前計算した ans[C_k] の値をそのまま出力します。

計算量

• 時間計算量: \(O(N^2 + Q)\)
  • 事前計算において、集落の全ペアの距離を計算するのに \(O(N^2)\) 時間かかります。
  • 各クエリへの回答は \(O(1)\) で行えるため、クエリ全体で \(O(Q)\) 時間となります。
  • \(N = 2000, Q = 2 \times 10^5\) のとき、全体の計算回数は約 \(2.2 \times 10^6\) 回となり、非常に高速に動作します。
• 空間計算量: \(O(N)\)
  • 各集落の座標を保持する配列と、計算した答えを保持する配列 ans のために \(O(N)\) のメモリを使用します。

実装のポイント

• 正確な整数平方根の計算 (isqrt 関数) C++の標準関数 std::sqrt は浮動小数点数（double）を返すため、非常に大きな値の計算や精度の限界によって、切り捨て（床関数）を適用した際に誤差が生じる可能性があります。 これを防ぐため、提示されたコードでは isqrt 関数を定義しています。std::sqrt で大まかな値を求めた後、その周辺の整数（x）に対して x * x <= n を満たす最大の整数を整数演算のみで厳密に探索することで、誤差を完全に排除しています。

• 入出力の高速化 クエリ数 \(Q\) が \(2 \times 10^5\) と非常に大きいため、C++の標準入出力（cin/cout）の同期を切り、高速化を行っています。

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  

  また、改行の際にも std::endl（バッファをフラッシュするため遅い）ではなく、"\n" を使用することで、入出力によるボトルネックを防いでいます。

  ソースコード

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 整数nの平方根の床関数を正確に求める関数
long long isqrt(long long n) {
    if (n <= 0) return 0;
    long long x = sqrt(n);
    while ((x + 1) * (x + 1) <= n) x++;
    while (x * x > n) x--;
    return x;
}

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    vector<long long> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> Y[i];
    }

    // 各集落から全集落への距離の切り捨て合計を事前に計算する
    vector<long long> ans(N, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            long long dx = X[i] - X[j];
            long long dy = Y[i] - Y[j];
            long long dist_sq = dx * dx + dy * dy;
            long long d = isqrt(dist_sq);
            ans[i] += d;
            ans[j] += d;
        }
    }

    // 各クエリに対してO(1)で回答する
    for (int k = 0; k < Q; ++k) {
        int C;
        cin >> C;
        --C; // 0-indexed に変換
        cout << ans[C] << "\n";
    }

    return 0;
}

この解説は gemini-3.5-flash-thinking によって生成されました。