318.1

かなり良くできているセット。

250

コストTで固定距離Dを移動できる移動方法と、任意の距離を距離と等しいコストで移動できる移動方法があるとき、目的地へ移動するのにかかる最小コストを求めよ、という問題。

前者の移動を使うには、T

600

盤面に書かれた数字の分だけ利益を得ることのできるすごろくがある。盤面に書かれた数字の総計は負の値になる。任意のタイミングでゲームをやめて良いとするとき、得られる利益の期待値を答えよ、という問題。

連立方程式になるので、解けば良いだけ。実際にはかなりのステップ数をシミュレーションすれば収束するので、時間いっぱいまでループさせればおしまい。

各マスの期待値は、そこから移動できる6マスの期待値と書かれている数字の和から計算できる。負の値になる場合はやめることに相当するので、期待値は0とみなせる。

900

複数の棒が与えられるので、棒の長さがちょうどになるような結合をして長方形を作りたい。このときに作れる長方形の最大面積を答えよ、という問題。

4辺を一度に作ろうとするとTLEする。向かい合う辺の長さが等しいことを利用する。各棒の部分集合について作ることのできる等しい長さの辺の最大値を計算する。これは部分集合Aと部分集合Bが同じ長さになるとき、部分集合A+Bがその辺の長さを作れると考える。

後は更にもう一度同じような処理をして、部分集合Aで作れる辺対の最大長と部分集合Bで作れる辺対の最大長から最大の面積を計算すれば良い。