421.1

自分の分不相応にレートが上がっているような気がしますが...。そもそも1000点問題が全然解けていないのにレートが上がっている時点で、近いうちにさっくり落ちるとは思いつつ。

250

一次元上で並んでいるN個の点の座標と質量が与えられるので、重力的に釣り合っている点の座標をN-1個求めよ、という問題。

直線状の隣接する2点間でバイナリサーチして、均衡する点を探す。

500

N個のケーキの大きさが与えられ、切って良い回数が与えられるので、最大のものと最小のものの大きさの差の最小値を求めよ、という問題。

現時点で一番大きいものについて分割数を増していく、という計算をしつつ、その時点での最大のものと最小のものとの大きさの差を覚えておいて、最小のものを答えれば良い。

最大のものを切らないと差は縮まらないし、切った後で最小になるなら均等な切り方の方が良い、というのを突き詰めていけば検証できるんじゃないかなぁ、という感じ。

1000

N人の中からK人を選ぶとき、最初に選ぶことができる人のリストと、既に相手が選ばれているなら選ぶことのできる人のペアが与えられる。K人以外の人が選ばれていないと選べない人は含まないようなK人の組をすべて均等と考える。このとき各人が選ばれる確率はどれくらいあるか答えよ、という問題。

人の隣接関係がランク3以下の木になるので計算量が抑えられているんだろうという感じの問題。全然分からないや。