535.1

コーナーケースに弱かった...。

250

二つの数の最大公約数と最小公倍数が与えられるので、可能な元の数のペアについて、和が最小になるものの和を答えよ、という問題。

実際には最小公倍数を最大公約数で割って得られる数を求めて、最大公約数が1になるように二つに因数分解してやって、最後に最大公約数をかけてやれば良い。

500

見てない。

1000

二次元グリッド上に数字が振られている。左上から開始して右下まで移動することを考える。下側の値が大きいときだけ下に進み、それ以外は右に進み、一番下か一番右に到達したら後は右下までまっすぐ進むという方針のとき、通ったセルに書かれている数字の合計がKになるような二次元グリッド上の数字配置はいくつあるか答えよ、という問題。

基本的に下に進める回数は高々Kなので、それを考慮して探索空間を狭める。端に到達すると移動は制限されるので、それまでの移動のパターンについて考える。移動する数が決まれば、右と下の順番は組み合わせで計算できる。後は、右に移動するときに数字がいくつ書いてあるかのパターンと下に移動するときに数字がいくつ書いてあるかのパターンをDPで計算してやる。最後の残りも同様にDPで計算できる。全部掛けた結果を足し合わせてやれば答えは出る。