272.1

500>>>1000というか1000のどこが難しいのか分からないままに通ってしまったセット。全然吟味していないけど。どうでもいいけど、一通りやり終えると250の内容を忘れてしまうのはいかがかと...。

250

N(<=5)個の数字が与えられるので、それらを組み合わせてできる整数のうち、一番約数が少ないもので最小の整数を答えよ、という問題。

N!通り整数を作ってみて、それぞれ約数の数をカウントする。約数の数のカウントは素因数分解で、ある素数で割れる回数+1を累乗していけば良い。

500

2つのグループの人がそれぞれA(<=5)人、B(<=5)人ずついる。異なるグループの人との距離が少なくともNあるように円卓に座るとき、椅子の数をC(<=50)として何通りの座り方があるか、という問題。回転して重なるものはそれぞれ異なるとし、同じグループの人も異なる人とみなす。

取り敢えず特定の一人を固定して、座らせる。この人の隣に今までに座っていない人の中から一人選び、着席させる。このとき新しく座る人との間にはもう誰も座らないものとする。...という感じでDPしていけば良い。最後に回転を考慮する必要があり、最初の人は任意の椅子に座って問題ないので、C倍しておけば良い。

座る可能性のある人は10人(実際には一人固定するので9人)なので、2^10だけ座った人の状態ができる。これと直前に座った人がどのグループかを覚えておく必要があるので、更に倍の状態が発生する。次の人を座らせる場所は高々C通りで、一つ前の人が座っている場所も高々C通り。つまり2^(A+B)*C^2だけの計算量が必要。

1000

幅wの道が間隔dで等間隔に縦横に並んでいる。ある交差点の中心から、別の交差点の中心まで移動することを考えるとき、道以外の場所を通らないで移動する最短距離を答えよ、という問題。

ある交差点から別の交差点に移動できるかどうかは、二つの交差点が同じ道の上にあるかどうか。交差点の数は高々50x50で、ある交差点に至るには高々50+50の交差点から。交差点から交差点に移動するとき、最短となる可能性があるのは、交差点の中央を通る(これは初期状態と終了状態がそうであるため)か、交差点の四隅を通る場合の5通り。つまり各交差点について、5か所を調べてやれば良い。これをDPすればおしまい。

本格的に正当性を吟味しようと思ったら相当大変なんだろうとは思う。(特に精度は注意しないといけない。)想定解が別にあるのかも知れない。