メンズワキガ対策専門ブランドD AGICA【ディーアジカ】

 

■競技プログラミング AtCoder Beginner Contest 133 B問題 その3

AtCoder Beginner Contest 133 の B 問題「Good Distance」のプログラムを書いてみました。

 

/*  AtCoder Beginner Contest 133 B - Good Distance
    2019.07.25 by meyon  */

 

#include <stdio.h>
#include <stdlib.h>

 

void err()
{
  printf("Error!¥n");
  exit(1);
}

 

int main()
{
  // input N:point and D:dimension
  int N, D;
  scanf("%d %d", &N, &D);
  if(N<2 || N>10 || D<1 || D>10) {
    err();
  }

 

  // input X:coordinates
  int X[N][D];
  for(int i=0; i<N; i++) {
    for(int j=0; j<D; j++) {
      scanf("%d", &X[i][j]);
      if(X[i][j] < -20 || X[i][j] > 20) {
        err();
      }
    }
  }

 

  // calculate norm
  int ans=0;
  for(int i=0; i<N-1; i++) {
    for(int j=i+1; j<N; j++) {
      int norm=0;
      for(int k=0; k<D; k++) {
        int diff = X[i][k] - X[j][k];
        norm += diff * diff;
      }

 

      // check norm whether integer
      int flag=0;
      for(int k=0; k*k <= norm; k++) {
        if(k*k == norm) {
          flag=1;
        }
      }
      if(flag) {
        ans++;
      }
    }
  }

 

  // display answer
  printf("%d¥n", ans);

 

  return 0;
}

 

err() 関数は Error! を表示してプログラムをエラー終了します。exit() を利用するために stdlib.h をインクルードしています。

点の数 N と次元数 D を入力したら、その数で座標の配列変数を定義します。for 文で座標データを入力します。

calculate norm と check norm whether integer の部分は解説の実装例を参考にしました。ループの条件式がちょっと異なっているのと、差分の絶対値とはせずそのまま差をだしているところが相違点です。

ちなみに diff は差分、norm はベクトルの距離みたいな意味ですね。

実装例のように flag を boolean 型にするには別のヘッダファイルが必要になります。まぁ int 型でも問題ないかなと。

 

提出した結果、AC をいただきました。

今回はちょっと難しかったですけど、考え方さえ分かればなんとかなりそうですよね。たくさん勉強させていただきました。

 


コメント
コメントする








   
この記事のトラックバックURL
トラックバック

■calendar

S M T W T F S
    123
45678910
11121314151617
18192021222324
25262728293031
<< August 2019 >>

■search this site.

■recommend

毎日貯まるポイントサイト ECナビ

■recommend

* 楽天ROOM *

■Twitter

■recommend

■recommend

■selected entries

■categories

■archives

■recent comment

■recent trackback

■links

■profile

■others

■mobile

qrcode

■powered

無料ブログ作成サービス JUGEM