451.1

簡単な解法が浮かんだので解いてみた。そもそも難しくはないはずなんだけど。

500

縦方向に一定速度(+1)で、横方向には常に加速(直前の横向き速度+1以上)しながら進む状況で、途中にある指定された点をいくつ経由できるか答えよ、という問題。速度は常に整数。

ある点(x,y)にいるときの、横向きの速度(d)が分かれば、別の点(X,Y)に到達できるかどうか分かる。これは横向きの最低速度が(d+1),(d+2),...,(d+Y-y)となるからで、この総和が(X-x)よりも大きくなければ良い。さらにこのとき、足りない分を後ろから分配していくと、途中の速度が狭義単調増加になる。

後は各点について、N個目の点として到達できるかどうかを求める。その条件はN-1個目の点として到達している他の点から到達できるか。その際に到達する最低横向き速度を覚えておけばいい。