AtCoderログ：0041 - ABC 133 B

問題

問題文

$D$ 次元空間上に $N$ 個の点があります。
$i$ 番目の点の座標は $(X_{i1},X_{i2},\dots,X_{iD})$ です。
座標 $(y_1,y_2,\dots,y_D)$ の点と座標 $(z_1,z_2,\dots,z_D)$ の点の距離は $\sqrt{(y_1−z_1)^2+(y_2−z_2)^2+\dots+(y_D−z_D)^2}$ です。
$i$ 番目の点と $j$ 番目の点の距離が整数となるような組 $(i,j)~(i<j)$ はいくつあるでしょうか。

制約

・入力は全て整数である。
・$2 \le N \le 10$
・$1 \le D \le 10$
・$-20 \le X_{ij} \le 20$
・同じ座標の点は与えられない。すなわち、$i \ne j$ ならば $X_{ik} \ne $X_{jk}$ なる $k$ が存在する。

収録されている問題セット

• AtCoder に登録したら次にやること (第04問類題)

回答

回答1 (AC)

整数 n と n 個の点の座標をベクトルを受け取った後、i 番目の点と j 番目の点の距離を計算し、それが整数ならカウンター answer に1を加える、という処理になります。ここで 変化 i は 0 から n-1 まで、変数 j は i+1 から n-1 まで変化させていけば良いでしょう。

距離が整数になるとき、二乗和 sum ($\sum_k (x_{ik}-x_{jk})^2$ のこと) は平方数になっているので、sum が平方数かを判定することになります。ここでは二乗和の平方根の整数部分を2乗したらもとの値になるか (つまり $(\lfloor \sqrt{x} \rfloor)^2 \stackrel{?}{=} x$ をチェックすることにしました。実際、$x=a^2$ ならば $(\lfloor \sqrt{x} \rfloor)^2 = (\lfloor \sqrt{a^2} \rfloor)^2 = (\lfloor a \rfloor)^2 = a^2 = x$ となりますが、$x$ が平方数でない場合には等号は成立しません。

abc133b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, d;
  cin >> n >> d;
 
  vector<vector<int>> x( n, vector<int>(d) );
  for ( int i=0; i<n; i++ ) {
    for ( int j=0; j<d; j++ ) {
      cin >> x.at(i).at(j);
    }
  }
 
  int answer = 0;
  for ( int i=0; i<n; i++ ){
    for ( int j=i+1; j<n; j++ ){
      int sum = 0;
      for ( int k=0; k<d; k++ ){
        sum += pow(x.at(i).at(k)-x.at(j).at(k),2);
      }
      if ( pow(int(sqrt(sum)),2)==sum ) {
        answer += 1;
      }
    }
  }

  cout << answer << endl;
}

調べたこと

AtCoder の解説 → ユーザ回答

回答1と同じ方針でしたが、平方数判定には isSquare という関数を使っていました、私の環境ではこの関数は使えなかったので、自作されているのでしょう。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でしたが、平方数判定では浮動小数を用いない実装になっていました。

リンク

前後の記事

• 前の記事 → AtCoderログ：0040 - ABC 211 C