561.1

メモ忘れ。

250

色が全部異なる風船がいくつかずつある。それぞれ大きさは大小のどちらかである。同じ大きさ同じ色の風船が必要な数がいくらかずつあり、それぞれ異なる色であれば良いとき、何個の風船の色を塗りかえればそれを実現できるか答えよ、という問題。

大小それぞれについて必要な個数を分けて考える。必要な風船がK種類なら、2^K通り試してやれば良い。後は、同じ大きさの風船について、割り当てをしていき、不足分を塗り替える。割り当ては個数が多い方からやるだけ。

550

二次元平面上に円がいくつかある。円はそれぞれ接触しないように配置されているが、中に完全に含まれるなどの配置は起こりうる。任意の円について、内部に既に赤い点がないものを選び、内部の任意の位置に赤い点を置くという操作を交互に行うとき、その操作の最後の一回を行うようにできるのは先手か後手答えよ、という問題。

いわゆるNimに帰着することを考えればいいだけ。内包関係を親子関係に置き換えて木を作ると、ある円を選んで、その内部の円のどれの中にも点がこないように点を配置すると、親から根までのパス上にある円全部が点を配置済みになる。それを除去してできる森について同様の操作を交互に行っていく。森の中のそれぞれの木については独立に考えれば良いので、適当に木を選んでやって、任意のノードを選び作成されるすべての森についての状態がどうなっているかについて考えたい。つまり、森の中の木は常にどんどん小さくなっていくので、小さい部分木から順番に計算していってやる。

要はGrundyNumberを全部分木について計算していって、最終的に森全体のGrundyNumberが0かどうかを判定してやればいいだけとも言う。

GrundyNumberの決定する際には、ある状態のGrundyNumberはそこから遷移可能な状態すべてのGrundyNumberを計算して、出てこない最小の値となる。こうしておくと、GrundyNumberを任意の値に減らすことができるので、XORとった最終的な値が与えられたときに必ず0にできる操作があることが保障される。相手方がどのような操作をしてもそれを打ち消してやれるので、自分の番のときに0でないGrundyNumberが与えられた方が勝つ。

たとえば、GrundyNumberのXORが6だったら、4の重みのビットが立っている山が少なくとも一つあることが保障されていて(奇数子のはず)それを選んでやれば、(それより上のビットを無視して)4から7のいずれかの値になってて、どれも6とXORを取れば(4の重みのビットが立たなくなるからだけど)0から3のいずれかの値になる。で、GrundyNumberの決め方として、自分より小さい値には任意に遷移できることを保障しているので、このような遷移は可能。というような感じでやっていけば良いっぽい。

1000

見てない。