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

 

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

AtCoder Beginner Contest 133 B - Good Distance を考えています。問題は理解できたので、次はプログラムを考えてみようと思います。

 

流れとしては、

 

  1.  点の数、次元の数を入力
  2.  座標データを入力
  3.  Yij を計算
  4.  k2==Yij かどうかを判定
  5.  3. 4. をすべての点間で繰り返す
  6.  4. が真だった数を出力として表示

 

といった感じですが、俺にはどうすればよいのかわからない部分があります。

一つは「3. Yij を計算」について。次元の数 D によって計算する項目数が変わってきます。D によって式を変化させるにはどうすればよいのでしょうか。もう一つは「5. すべての点間で繰り返す」です。漠然と「for 文を使って N、D の数だけ繰り返す」というイメージを浮かべますが、具体的な方法に考えが進みません。

 

今の俺の実力は「考えて悩むよりも真似してみよう」レベル (^_^;) 幸い解説に C++ の実装例がありましたので、これを参考にしてみましょう。

実装例で計算を行なっている部分は以下です。なるほど!と思ったのは太字の部分、( ) を計算し二乗して加算代入していくというところです。これで二つの疑問点は一気に解決できそうです。

 

for (int i = 0; i < N; ++i) {

for (int j = i+1; j < N; ++j) {

  int norm = 0;

  for (int k = 0; k < D; ++k) {

    int diff = abs(X[i][k] - X[j][k]);

    norm += diff * diff;

  }

 

では、入力例 2 の N=3、D=4 の場合で考えてみましょう。

座標は、

 

        1 番目の点 (X00 X01 X02 X03)

        2 番目の点 (X10 X11 X12 X13)

        3 番目の点 (X20 X21 X22 X23)

 

で、配列変数 X[N][D] に格納されています。

最初に 1 番目の点と 2 番目の点の距離の二乗 Y01 を求めます。

 

Y01 =(X00-X10)2+(X01-x11)2+(X02-X12)2+(X03-X13)2

 

次に 1 番目の点と 3 番目の点の距離の二乗 Y02 を求めます。

 

Y02 =(X00-X20)2+(X01-x21)2+(X02-X22)2+(X03-X23)2

 

最後は 2 番目の点と 3番目の点の間です。

 

Y12 =(X10-X20)2+(X11-x21)2+(X12-X22)2+(X13-X23)2

 

これですべての点の間の計算は終わりです。

X[i][k]-X[j][k] とすると、

 

for (i=0; i<N-1; i++) {

  for (j=i+1; j<N; j++) {

    for (k=0; k<D; k++) {

      X[i][k] - X[j][k]

 

といったループを作ればよいことがわかります。

ちなみに、N=10 とすると必要な計算式は、i=0 のときに 9 個、i=1 のときに 8 個、……、i=8 のときに 1 個の計 45 個 (10C2=45) となります。実装例では i=9 までループしますが、次の j のループが偽となって終了するので、結果は変わりません。ループが 1 回空振りするだけですね。

なお、実装例では差分の絶対値をとっていますが、どうせ二乗するのですから不必要だと考えています。

 

さぁて、ようやくアルゴリズムも理解できたので、次回こそプログラムを書いてみることにしましょう。

 


コメント
コメントする








   
この記事のトラックバック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