TCO 2012 Round 1A

惨敗。

250

ゲームを数回やる。勝者は1/2,1/2,1/4,1/4,1/8,1/8,...というようにポイントがもらえる。誰が何回勝ったかは分かっているとき、一番たくさんポイントを得た可能性のある人の名前をすべて答えよ、という問題。

回数が少ないので全部割り当てればおしまい。実は2回勝った人は最初の2回で他の人よりもたくさんのポイントを取得できることが確定するので、2回以上勝った人(もしくは全部で1回しかゲームをしていないケース)を答えれば良い。

500

既約分数のうち、分子と分母の積がN以下の整数の階乗になっているものは何通りあるか答えよ、という問題。

ある分数の分子と分母の積がKの階乗になっている場合、素数ごとに分子分母どちらかに割り当てれば良い。分子と分母が一致することはないので、全部のパターンのうち半分では分子が大きくなってしまうので、それを除去してやる。これを全部のK<=Nについて試せば良い。

1000

あるスイッチを押すと複数個の電球の状態が反転するので、現在の状態でついている全部の電球をできるだけ少ない操作数で消せ、という問題。ただし各電球について、連動しているスイッチは高々二つである。

2SATの問題なので、答えがあるかどうかは深さ優先探索で求まるが、最小操作数なので、全部数え上げる必要がある。基本的に一度やった操作を延々と繰り返すような探索になりがちなので、ある程度のまとまった操作を先にまとめてしまってから探索すればすぐに終わる。具体的には、最初から消えている電球をつけた場合、関連するスイッチは残り一つしかないのでそれを必ず使う、ということが決まる。ある電球を消すのにスイッチが二つあるので、それらの両方について、どういう結果が出るか、を覚えておき、電球ごとに優先順序を持っておいて、それの順番で操作して、より優先順序の高い電球を無視しないとか、既に操作した電球を再度操作しないとか、そんな感じで適当に探索やるだけ。