Exploring Caves 解説

問題名：Exploring Caves
出典：Problem A, ACM/ICPC Japan Domestic, 2002-10-02
難易度：☆
問題の種類：シミュレーション
解法：ユークリッド距離，最大値を出力
解答ソースコード：
- p0004-deq.cpp

アルゴリズムの概略

ロボットの初期座標を (0, 0) とし，与えられた移動量 (dx, dy) だけ毎回足し合わせていきます。各移動後に原点 (0, 0) からのユークリッド距離 d = sqrt(x² + y²) を計算し，その最大値を持つ (x, y) 座標を答えとして出力します。もし同じ最大値を持つ点が複数あれば，x座標が大きい値を答えとします。

最も簡単なシミュレーション＋幾何問題だといえるでしょう。

アルゴリズムの計算量

移動回数を n 回とすると，移動の計算量やユークリッド距離を求める計算量は定数ですので， O(n) の計算量なので問題ありません。

アルゴリズムの実装

アルゴリズムは非常に簡単で，擬似コードは次のようになります。

cx, cy = 0, 0
max, mx, my = 0, 0, 0
for each 入力値(dx, dy):
  cx, cy = cx + dx, cy + dy
  ユークリッド距離dを求める
  if d > max or (d == max and cx > mx):
    max = d
    mx, my = cx, cy

ただし，一つだけ重要な点があります。それは，ここでは求めたユークリッド距離 d は比較しか行っていないので，平方根を取る必要がないということです。つまり，d = sqrt(cx², cy²) ではなく d = cx² + cy² で代用できます。これによる利点は二つあって，

少数の誤差を気にする必要がなくなる（一般に少数の比較では a == b が使えません）
計算量が削減される（平方根を求めるのは加算や乗算に比べるとけっこうな処理になります）

です。このテクニックは今後も利用するので覚えておきましょう。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $

deq notes