384.1

凄く久し振りにつながった件。問題としては良くないけれど、一度はやっておかないと騙し討ちくらってイラッとしそう。

250

あるリソースにアクセスするためには二種類の権限の両方を持っていないといけない。それぞれの種類について持っている権限のリストが与えられるので、最大で何種類のリソースにアクセスできるか答えよ、という問題。

権限のチェックをセット使ってやるだけ。

500

N人が順番に自分以外の誰かを指名していく。指名された相手は指名した相手の持つ確率に応じて追い出される。全員の目的が、誰でもいいからできる限り早く一人残る状態にすることであるとき、指名回数の期待値を答えよ、という問題。

誰のターンかと、現在残っている人の集合を状態にしてDPで期待値を埋めていく。基本的には残っている人が少ない方から埋めていけば良いが、全員失敗でループすることがあり得るので、ループする確率を使って求めたい期待値について一次方程式を立ててやる必要がある。計算量的には余裕があるので後はどうとでも。

1000

上か左か左上にしか進めないチェスのクイーンが複数ある。交互にどれか一つを選んで移動させることを考える。同じマスに複数いたり、途中にいるヤツを飛び越したりしても構わないので、先にどれかを一番左上のマスに移動させたプレイヤーが勝ちとする。どちらのプレイヤーが勝つか答えよ、という問題。

すぐに一番左上のマスに移動できるものが一つでもあれば先手必勝。後はそれ以外のマスについて、GrundyNumberを計算してやる。とにかく一番左上のマスに移動できるようなマスには移動させたくないので、そういうマスにしか移動できない点があればそこのGrundyNumberが0になり、それ以外については、到達可能な点のGrundyNumberを列挙して、最初に登場しない値にセットすればいいらしい。(GrundyNumberとはそういうものらしい。そもそもそういう名前なのかも良く知らない。)

勝手な解釈を付け加えるなら、GrundyNumberのXORを0にするのが目的なので、増やすことには余り興味がなく、0以外のときに必ず0にできる移動があることに意味があるので、途中に登場しない値が出ては困る、という感じなのだろうけれど、これって十分条件でしかなくない？