370.1

リハビリ最初からやり直す必要ありそう...。

250

箱の中にいくつかの種類のものが入っている。K個取り出すとき、全部同じ種類のものを取り出す確率を求めよ、という問題。

それぞれについて何通りあるか求めて合計し、全体から選ぶ方法で割る。double精度で良いので厳密なことは考えない。

500

二地点間に中継地点がいくつかある。二地点間の中継地点を再配置して、隣接する地点間の距離の最大値をできるだけ小さくしたい。中継地点を移動する距離に比例するコストがかかり、整数座標での移動しかできない。最大コストとして許容される値が与えられるので、隣接する地点間の距離の最大値の最小値を答えよ、という問題。

二地点間の距離が十分小さいので、できるだけ小さい値から開始して、隣接する地点間の距離の最大値として可能な値かどうかを判定していき、うまくいった最初の値が答え、という方針で良い。判定については、K番目の中継地点を特定の位置に移動させるときに要したコスト(最小のコストを持つ方が良い？)でDPしてやる。移動させる際には、一つ前に移動させた地点からの距離が目的の値以内になるように注意するだけ。

950

約数の数がちょうどK個ある値のうち、最小のものを答えよ、という問題。大き過ぎる場合は-1を返す。

2^60は大き過ぎるので、Kを素因数分解したときに61以上の素数が出てきた場合は大き過ぎるとみなせる。後は、Kを適当に分割して、小さい方の素数から順に割り当てていく、というのを全探索してやれば良い。自分より小さい素数を使う回数が少ないことはないはずであるとか、大き過ぎる中間値になるとか、そういうのを枝狩りしてやれば終わる。