POJ-1759 : Garland
問題概要
長さN(<1000)の数列Aがある。A[1]は固定されている。それ以外の部分について、A[i]>=0, A[i] = (A[i-1]+A[i+1])/2 - 1 (i in (1,N))となる。A[N]のとりうる最小値を求める問題。
解法
最小値はA[N]について単調なので答について二分探索する。答を決めたらそれ以外の値は連立一次方程式を解くことで求めることができる。
長さN(<1000)の数列Aがある。A[1]は固定されている。それ以外の部分について、A[i]>=0, A[i] = (A[i-1]+A[i+1])/2 - 1 (i in (1,N))となる。A[N]のとりうる最小値を求める問題。
最小値はA[N]について単調なので答について二分探索する。答を決めたらそれ以外の値は連立一次方程式を解くことで求めることができる。