426.1

手を抜いた分だけ情けないミスをしましたよ、という感じ。情けないっていう次元ではなさそう。

250

カードをPermutationを用いて1回以上N回以下のいずれかの回数だけシャッフルする。初期配置を好きなようにいじって良いとき、自分の欲しいカードが配られる枚数の期待値を答えよ、という問題。

自分に配られるカードの初期位置である確率の高い順に欲しいカードを置いておく。そのためにはN回だけPermutationを使ってカードの移動をシミュレーションすれば良い。

500

N匹のネズミを同時に一つの箱で捕まえられる最小の正方形の箱の大きさを答えよ、という問題。

ネズミのx座標の最大値と最小値の差分とy座標の最大値と最小値の差分のうちの大きい方がその瞬間に必要な箱の大きさ。各座標の最大値は下に凸な関数で、最小値は上に凸な関数になる。(ネズミは線形な移動をするので。)差分は下に凸な関数になるので、三文探索するだけ。

最初INFを大きくとりすぎたせいで、doubleの範囲に入らなくなり、見当違いなデバッグをした結果、それが最終的な精度を損なうというひどいことをやってしまった。INFはできるだけギリギリにしましょうということ。ただ大きければいいってものじゃあない。(前に500を間違えた時は小さ過ぎたし、何事にも程度ってものがある、ってことだとは思う。)

1000

ある場所までの距離が書かれた標識が与えられる。これから目的地までの距離を算出せよ、という問題。途中で矛盾があったり、通り過ぎていたりしてはダメ。

ひたすら正当な推論を行って、無矛盾であることを確認しつつ、距離を算出する問題だとは思う。50*50*200*200が収束するまで推論しないといけない気もする。