564.1

昼飯ゲット。

250

盤面の大きさが与えられるので、初期位置を自由に決めて良いとき、チェスのナイトが到達可能なマスの数の最大値を答えよ、という問題。

盤面が十分に大きければどこにでも行けるので、幅が狭いときとかを全探索すれば良いそうで。場合わけしてひどい目にあうなど。

500

赤、緑、青の順番でボールを取り出すことを考える。ない色の場合はスキップする。箱の中にN個ボールがあって、K番目に取り出されたのが赤と分かっているとき、箱の中身のパターンとして可能なものは何通りあるか答えよ、という問題。

K番目に到達した時点で、全部の色が一度も欠けていないか、一つの色が欠けたか、二つの色が欠けたか、に分けて適当に数え上げるだけ。本当はDPで取り出した個数とか、使い切った色とかを状態に持って計算するものらしい。

850

ある非負整数配列の各要素の上限値が与えられる。全部のXORの結果がNになることが分かっているとき、その整数配列として可能なものは何通りあるか答えよ、という問題。

もしNよりもとても大きい値が一個ある場合、それ以外の数をどう選んでもそいつで帳尻あわせできるそうで...。じゃあない場合どうするの？という感じだけれど、いつか考える。