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 ファイルに式の導出などを含めた詳しい解説を記してあります．

ソースコード †

1066.cpp