344.1

前のセットがつながらないので...。ちょっとひどいセット...。

250

バレーボールの勝った試合数・負けた試合数・取ったセット数・取られたセット数が与えられるので、元の試合結果を復元せよ、という問題。

復元できる条件として、勝った試合のうち、高々1試合で1セット落とし、それ以外の試合で落としたセット数は全部0または全部2になり、負けた試合のうち、高々1試合で1セット取り、それ以外の試合で取ったセット数が全部0または全部2になることである。後はこれから復元するだけ。

500

いくつかの物質について作る方法がそれぞれ高々一通り与えられる。手持ちの物質から目的の物質を作るのに必要な最小ステップ数を求めよ、という問題。

高々一通りなので、足りないものは貪欲に作っていけば良い。また、物質の作成時に物質は単調に減るので、物質の総数が明らかに合わなくなれば打ち切って良い。目的の物質から必要な物質を逆算していくと比較的簡単に書ける。

1000

1からNの整数を並べたとき、整数Iの位置がI番目から高々K個しか離れていないような並べ方は何通りあるか答えよ、という問題。

I番目の位置に入れられる整数は、I-K以上I+K以下である。使った整数を除去しつつ、入れられる整数を状態に、DPをしていけば良い。離れ過ぎるといけないので、ギリギリの数がある場合はそれを入れ、そうでないときは自由に選ぶ。答えはとても大きい数になるのでBigIntegerを使いましょうという問題の模様。比較的やるだけ。