AOJ 2157 Dial Lock

問題

Dial Lock | Aizu Online Judge

k 桁の数字が与えられる。もとの数 now から target という数を作りたいが, そのために以下の動作が許される。
動作: 区間 [s, t] および数 d を選び, その区間の数について, nxt = (prev+d)%10 とする。

動作回数の最小の値を求めよ。

解法

普通に考えると 10^k の状態がありそうですが, 有効な遷移(答えに近づく遷移)を考えると,

• まだあっていない左端の数を合わせる(ついでに右側の数も動かす)
• まだあっていない右端の数を合わせる(ついでに左側の数も動かす)

の 2 通りしかならないので, 意外に遷移は少なくて済みそうです。なので幅優先探索とかをやれば良さそうですが, 気分が乗ったので下のコードでは IDA (あってるよね？)をやっています。

ある時点で, 「あと右に i だけ動かさないと target と合わない」という数があったとします。このような i の種類が cnt 種類あったとすると, すべてをそろえるためには最低でも cnt-1 回は操作をしないといけないので, 枝刈りができます。

…と思ったけどそんなことない気がする…後で書き直すかも(?)

int N;
vi now, target;

bool dfs(int d, int maxDepth) {
    if (d == maxDepth) {
        if (now == target) return true;
        else return false;
    }
    int exist = 0;
    for (int i = 0; i < N; i++) {
        int tmp = (10+target[i]-now[i])%10;
        exist |= 1<<tmp;
    }
    int cnt = __builtin_popcount(exist);
    if (cnt+d > maxDepth+1) return false;
    for (int i = 0; i < N; i++) if (now[i] != target[i]) {
        int diff = (10+target[i]-now[i])%10;
        for (int j = i; j < N; j++) {
            for (int k = i; k <= j; k++) {
                now[k] = (now[k]+diff)%10;
            }
            if (dfs(d+1, maxDepth)) return true;
            for (int k = i; k <= j; k++) {
                now[k] = (now[k]+10-diff)%10;
            }
        }
        break;
    }
    for (int i = N-1; i >= 0; i--) if (now[i] != target[i]) {
        int diff = (10+target[i]-now[i])%10;
        for (int j = 0; j <= i; j++) {
            for (int k = j; k <= i; k++) {
                now[k] = (now[k]+diff)%10;
            }
            if (dfs(d+1, maxDepth)) return true;
            for (int k = j; k <= i; k++) {
                now[k] = (now[k]+10-diff)%10;
            }
        }
        break;
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> N) {
        if (N==0) break;
        now.clear(); target.clear();
        now.resize(N); target.resize(N);
        string s, t;
        cin >> s >> t;
        for (int i = 0; i < N; i++) {
            now[i] = (s[i]-'0');
            target[i] = (t[i]-'0');
        }
        int ans = N;
        for (int i = 0; i < ans; i++) {
            if (dfs(0, i)) {
                ans = i;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}