AOJ 2709 - 真っ暗な部屋 - ツバサの備忘録

解法

真っ暗な部屋が多くて16個しかないので、真っ暗な部屋に関する何かしらの情報をbitで持つことができます。
基本的な考え方は、幅優先探索です。
例えば $x$ 回指示を出すとしたとき、指示列の選び方は $K^{x}$ 種類になります。全ての部屋に対して、 $x$ 個の指示を適用していき、明るい部屋に到達するかどうかを調べることで、 $x$ を小さい方から試していけばいつか答えが求まります。 $x$ を固定したときに調べるためには、1つの指示列を処理するのに $O(xM)$ だけかかるので、 $O(xMK^{x})$ になります。もちろんこれでは間に合いません。そこで次のような考え方をします。
まず、真っ暗な部屋全てにA君を立たせます。つまり、A君はこの時点で $M$ 人いて、全て違う部屋に立っています。その後、 $K$ 種類ある指示のうち、1つを選んで全てのA君に対して同じ指示を出します。
すると、 $M$ 人いるA君のうち $p$ 人(0以上 $M$ 以下)は明るい部屋に到達することができます。
残った $M-p$ 人について、また $K$ 種類の中から好きな指示を出し、暗い部屋にいるA君が0人になるまで繰り返せば、幅優先探索によって答えを求めることができます。ここで、現在暗い部屋に残っているA君の状態は、それぞれの暗い部屋にA君が"いる"or"いない"の2通りなので、全体で $2^{M}$ となります。ある部屋にA君が複数人いたとしても、全員に同じ指示を出しているので、1人だけいれば十分です。これは、最初に言ったように $M$ が16以下のため、bitで状態を考えることができます。
ですが、この考え方でも、指示の種類が膨大なためまだ間に合いません。
そこで、暗い部屋にA君がいるかどうか、という状態が $2^{M}$ 通りしかないことに注目すると、
dp[S] = 暗い部屋にA君がいるかどうかの状態がSになるような指示列の長さの最小値
とすると、これは $O(KM2^{M})$ で解くことができます。現在の状態Sに対しての指示が $K$ 通りで、1つの指示をSに対して適用するのに $O(M)$ かかります。
状態Sについて、左から $i$ 桁目を $D_i$ にA君がいるとき1、いないとき0とすると、
初期状態が
dp[ $2^{M}-1$ ] = 0
そして答えは
dp[0]
となります。
幅優先探索をすると、すでにある状態Sにたどり着いたかどうか(dp[S]が埋まっているかどうか)さえわかれば、遷移を気にせずに答えが求まります。