554.1

解ける問題を落とすのはどうかと思う。

250

二種類の石を交互に積んでいくことを考える。石の数と大きさが与えられるので、積むことのできる高さは何通りあるか答えよ、という問題。

二種類といいつつ同じ大きさのときはどちらを先に積んでも同じ。片方の石がなくなったときに、もう一方が残っていればもう一つできる。

500

N個の物体を一列に並べることを考える。隣り合う二つの距離は、それらのうちの高い方の高さと同じであるとするとき、N個を並べたときの距離が最小のもので、辞書順で最初のものを答えよ、という問題。

一番背の高いものは端にあると、自分の高さが影響するのは1回で済む。次に高いのはそれの隣か別の端であれば同様...。という感じで、結局並んだ結果は下に凸になる。なので、貪欲に下降列を作り、残りをソートしてやれば良い。

1000

2x2xHの形状に1x1x1のブロックを積むことを考える。ブロックは何色かあるので、隣接するものが同じ色になるような場所が高々K個であるような積み方は何通りあるか答えよ、という問題。

最初の段を積んで、後は前段からの遷移がどうなるかの漸化式を書いて、行列乗算やるだけ。時間制限がシビアな感じ。