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

 

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

調子に乗った meyon さんはさらに挑戦してみました (^_^;)

AtCoder Beginner Contest 133 の B 問題「Good Distance」です。

 

画像キャプション

 

この問題はピンときました。座標上の 2点の間の距離を求めるのですから、いわゆる三平方の定理ってやつですね。

多次元の場合については俺は知らなかったのですが、問題に示された公式で適用できるのでしょう。基本的な考え方は三平方の定理も同じなんだろうなと想像できます。

 

例 1 を見てみましょう。

N=3 、D=2 ですから、平面 (二次元空間) 上に 3 個の点があるということです。ごく普通に三平方の定理で考えればいいですね。

たとえば 1 番目の点 (1,2) から 2 番目の点 (5,5) までの距離は √( (5-1)+ (5-2)) です。 え〜と式の表示が変ですけど、笑ってこらえてやってください (^_^;)

 

さて、次にこの式の値が整数かどうかを判定しないといけませんが、えーと、どうしましょう? 思いついたのは以下のようなものです。

 

  1. 小数部分を取り出して、それが 0 かどうか。0 なら整数です。
  2. 小数点以下を切り捨てて、それが元の値と同じかどうか。同じなら整数です。

 

でもなんだかねぇ、なぜだかいまいちすっきりしないんですよ…

迷ったのでちょっと解説をカンニングしてみました。すると

 

k2=Yij を満たす k が存在するかを調べれば √ Yij が整数であることを判定できます。

 

とあります。

そうか、平方根というムズムズするような値を判定するんじゃなくて、整数 k を二乗した値が (5-1)2+(5-2)2 と等しいかどうかを調べればよいのですね。それならすべての変数を int 型で扱えます。

ポン、なるほど、目から鱗のアルゴリズム (^_^;)

 

例 2 はどうでしょうか。

N=3 、D=4 ですから四次元空間上に 3 個の点が存在します。四次元空間…… う〜ん、四次元空間を想像することはできませんが、公式に当てはめて計算するだけのことです。

1 番目の点から 2 番目の点までの距離は、

 

Y12=(-3+12)2+(7-1)2+(10-8)2+(2-2)2=121

 

121 は 112 なので真 (整数) です。

2 番目と 3 番目の間は 、

 

Y23=(-2+12)2+(8-1)2+(10-9)2+(3-2)2=151

 

151 は 122 と 132 の間なので偽 (整数ではない) です。

同様に 1 番目と 3 番目の間は、

 

Y31=(-2+3)2+(8-7)2+(9-8)2+(3-2)2=4

 

これは 22 ですから真です。

したがって真が 2 つでしたから、出力は 2 となります。

 

例 3 は直線 (一次元空間) 上に 5 個の点があります。座標はすべて整数ですから、これらの点の間の距離は、計算するまでもなく整数であるとわかります。でも、プログラムでは何次元でも同じように処理できなければなりませんので、公式に当てはめてみましょう。

1 番目と 2 番目の間は Y12=(2-1)2=12 で真です。2 番目と 4 番目の間も Y24=(4-2)2=22 で真です。3 番目と 5 番目の間も Y35=(5-3)2=22 で真です。他の組み合わせもすべて同じく真になります。組み合わせの数は 10  ( 5C2 ) です。

 

さて、これで問題が理解できましたので、次回はプログラムを考えてみることにします。

 


コメント
コメントする








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