628.1

やるだけセットだったそうです。

250

整数Nが与えられるので、N=M^(Mの約数の数)なる最小のMを答えよ、という問題。

Nは2以上なので、約数の個数が1個という状況はあり得ない。ということで、2以上の根を拾ってきて(ここ間違えた)、後は約数の数をループするだけの簡単なお仕事。が、別に10^9ループくらいまでは通るらしい。気持ち悪い。

500

ノードのMAXまたは和を取る二分木が与えられる。各ノードに数字を割り当てて、最終的にルートにアサインされるスコアを最大化せよ、という問題。

MAXを取ると、片側が完全に死んで、和を取ると両方が生き残る。という感じなので、取り敢えずアサインは後回しにして、最終的に生き残るノードの個数を最大化するような割り当てを考えれば良さそう。たとえばMAX取るなら、子がK個の和かM個の和の比較になるはずなので、大きい方を取る、和の場合は何も考えずに個数を取る。で、最後にルートにアサインできる個数が分かれば、数値を大きい方から適当に拾ってやるだけ。

1000

なんかN個あるステージを全部クリアして、最適にM点取って終わるために必要なプレイ回数の期待値を答えよ、という問題。各ステージでは1点または2点取れるとして、その点数の取れる確率が与えられる。

うまいことソートして適当にDPすれば通るらしい。まじめに数式立てて線形計画法するのかと思ったが、そんなことはないらしい。ふ〜ん。