250 点(i,Y[i-1])と点(i+1,Y[i]) を i = 1..n としてつないだ曲線がある。 この曲線と、直線 y = a との交点の個数の最大値を求めよ。という問題です。y[i]が大きく、aを沢山調べるのは難しいので、Y[i]とその近くだけを調べれば良いです。 (整数点(Y[i])だ…

250 高さがhの二分木が与えられる。枝分かれのない辺の集合に分割するとき、その集合の個数の最小値(を定数で割ったもの)を求める。分かりやすく言うと、一筆書きを何回か行って、高さhの二分木をつくるのに必要な回数の最小値を求める。証明はできませんが…