mayoko’s diary

プロコンとかいろいろ。

Japan Alumni Group Summer Camp 2015 Day 2 D - 真っ暗な部屋

解法

見た目からわかるように bitDP で解きます。

dp[state] = (今暗い部屋のうち state で表される部屋にいる可能性がある場合の, 最小移動距離) とします。

すると, 各部屋から i 番目の部屋に移った時の次の状態 nstate がわかります。その nstate について再び最小移動距離を求める, ということを繰り返すことによって答えを求めることが出来ます。

下の実装はかなり雑で, 1 秒くらいかかってしまいましたが, inD を求めるところを O(M) ではなく O(1) でできるのでそれで 16 倍です。

const int MAXM = 16;
const int MAXN = 101;
const int INF = 1e9;
int N, M, K;
int D[MAXM];
int v[MAXN][MAXN];
int dp[1<<MAXM];

int dfs(int state) {
    if (state == 0) return 0;
    int& ret = dp[state];
    if (ret >= 0) return ret;
    ret = INF;
    for (int i = 0; i < K; i++) {
        int nstate = 0;
        for (int j = 0; j < M; j++) {
            if ((state>>j)&1) {
                int next = v[D[j]][i];
                int inD = -1;
                for (int k = 0; k < M; k++) if (D[k] == next) {
                    inD = k;
                    break;
                }
                if (inD != -1) nstate |= (1<<inD);
            }
        }
        if (state == nstate) continue;
        ret = min(ret, 1+dfs(nstate));
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        cin >> D[i];
        D[i]--;
    }
    for (int i = 0; i < N; i++) for (int j = 0; j < K; j++) {
        cin >> v[i][j];
        v[i][j]--;
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs((1<<M)-1) << endl;
    return 0;
}