524.1

分かるけど、できない。できなきゃ意味ない...。

250

距離Xだけ荷物を運ぶが、一度の運搬で移動して良い距離は素数でない距離でなくてはならない。何回の運搬に分けて行えば良いか答えよ、という問題。

Xが素数なら1だけ動かして、素数でなくなるまで試す。

500

見てない。

1000

1x1x1のキューブが詰んである。二つの方向から見たときの形状が与えられるので、可能な配置は何通りあるか答えよ、という問題。

DPするだけ...。ある方向から見たときの形状は、ソートしても全体の配置の可能性については影響しない。後は大きい方から決定していく。一番高いものが一つの方向からしか見えない場合のみ不自然なことが起きていて、それ以外では実現可能。

一番大きい値が出てくる場所を調べると、矩形領域のどこかに出現しないといけないことが分かる。なので、各行各列に一度は出現するようなパターンをDPしてやれば全列挙できる。次の値にいくと、同様の矩形領域が得られるが、一つ前の矩形領域を内包しているので、その分除去してやらないといけない。つまりそれによって既により高いものが存在するため、任意の高さにして良い行や列が存在する。この部分を適当に処理しつつ、同様のDPをしてやれば良い。最終的に積算すれば全通り列挙される。