384.1

250

ある情報を得るのに、ユーザグループに所属していて、かつ部屋に入る権限を持っていることが求められるときに、いくつの情報が得られるか答えよという問題。

入れる部屋と所属しているユーザグループにマッチする情報を重複しないようにカウントするだけ。ライブラリをちゃんと使いましょうね、という問題。

500

プレイヤーが他のプレイヤーをヒットする確率が与えられ、ヒットされたプレイヤーが抜けていくゲームで、勝者を決定させるのに必要な最小のターン数の期待値を答えよという問題。

今残っているプレイヤーと誰のターンかを考えると、期待値が求められるので、それをもとに起こり得るすべての状態を記録しながら探索。ミスが続くとループが発生することがあるので、そこの式を解けば答えは出る。

実際には単純なDPで求めることができるらしく、他の人はサックリ解いていた模様。

1000

盤面上にクイーンがいくつかある状況で、クイーン間の相互作用を無視した上で、いずれかのクイーンを先に左上に持っていったプレイヤーを勝ちとする。各プレイヤーは1個のクイーンを左上方向に移動させないといけない。プレイヤーは二人で交互に動かす時、最善手で勝つのはどちらのプレイヤーか答えよ、という問題。

有名な問題だそうで、grundy numberというものを途中経過に注意しつつ求めると良いそうです。xorで求めるものらしいけれど、結局偶奇がこの場合問題で、単純に足し算でもいいのかも？