Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What are the problem?
@RoadLynton

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$ が存在する。

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

回答

回答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と同じ方針でしたが、平方数判定では浮動小数を用いない実装になっていました。

リンク

前後の記事

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
0
Help us understand the problem. What are the problem?