Garland (1066)

概要

1 本の線でつながった N 個のランプが,両端だけが固定された状態になっている.それぞれのランプの(地面からの)高さ H[i] は次の式にしたがう.

  • H[1] = A,H[N] = B
  • H[i] = (H[i−1] + H[i+1]) / 2 − 1

ただし,左端のランプの高さ A は与えられる.このとき,ランプが地面にべたりとつかない(つまり任意の i について H[i] ≧ 0 となる)ようにするためには,右端のランプの高さ B が最低どれだけ必要であるかを求めよ.ここに,ランプの大きさは無視できるものとする.

解法

H[i] = H([i−1] + H[i+1]) / 2 − 1 を漸化式とみなして解くと,

H[i] = (i−1)(i−2) + (i−1) · H[2] − (i−2) · H[1]

となる.したがって H[N] の最小化問題は H[2] の最小化問題,さらには H[i] の最小値が 0 となるような H[2](あるいは H[N])を求める問題に帰着する.ここで H[i] は 2 次式であり,整頓すると

H[i] = i² − (H[1] − H[2] + 3) · i + (2 · H[i] - H[2] + 2)

となることから,H[i] が最小となる i の値は (H[1] − H[2] + 3) / 2 にもっとも近い整数である.したがって H[i] の最小値が計算可能かつ連続であるから二分法によって H[2] あるいは H[N] の値が計算できる.

(H[1] − H[2] + 3) / 2 > N のときは例外なので注意すること.この場合は H[N] が最小値をとる.

添付の PDF ファイルに式の導出などを含めた詳しい解説を記してあります.

ソースコード

file1066.cpp


添付ファイル: file1066.pdf 376件 [詳細] file1066.cpp 819件 [詳細]

Last-modified: 2009-11-06 (金) 13:25:51 (4575d)