CODE FESTIVAL 2014 予選A D - 壊れた電卓

去年の予選 D 問題解いてなかったので解いてみました。結構苦戦したので予選通れるか心配になってきた。

問題

code-festival-2014-quala.contest.atcoder.jp

解法

桁 DP 的に解きます。

dp[keta][state][lt][gt] = (keta 目の桁までで, 0〜9 の数字のうち state で表される数字のみを使用していて, A より小さいフラグが lt, A より大きいフラグが gt の時の A との差の最小値)
とします。

lt が true のときは keta 目の数字はなるべくでかい数字を使うのが良く, gt が true のときは keta 目の数字はなるべく小さい数字を使うのが良いです。また, それ以外の場合は数字を適当に選んだ際に, lt と gt のフラグがどうなるかを調べる感じでやれば OK です。

得た知見

• stoll(s) は s が空文字の時は死ぬ
• 桁 DP というかとにかく DP では状態として何を考えるかが重要(n 回目)

const ll INF = 1ll<<60;
string A;
int K, n;
ll a;

ll ans = INF;

void dfs(int keta, int s, int lt, int gt, string now) {
    if (keta == n) {
        ll res = stoll(now);
        ans = min(ans, abs(a-res));
        return;
    }
    int num = A[keta]-'0';
    if (!lt&&!gt) {
        for (int i = 0; i < 10; i++) {
            int ngt = 0, nlt = 0;
            int ns = s|1<<i;
            if (__builtin_popcount(ns) > K) continue;
            if (i < num) nlt = 1;
            if (i > num) ngt = 1;
            string next = now+(char)(i+'0');
            dfs(keta+1, ns, nlt, ngt, next);
        }
    } else if (lt) {
        for (int i = 9; i >= 0; i--) {
            int ns = s|1<<i;
            if (__builtin_popcount(ns) > K) continue;
            string next = now+(char)(i+'0');
            dfs(keta+1, ns, 1, 0, next);
            break;
        }
    } else if (gt) {
        for (int i = 0; i < 10; i++) {
            int ns = s|1<<i;
            if (__builtin_popcount(ns) > K) continue;
            string next = now+(char)(i+'0');
            dfs(keta+1, ns, 0, 1, next);
            break;
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> A >> K;
    a = stoll(A);
    n = A.size();
    dfs(0, 0, 0, 0, "");
    {
        string p;
        for (int i = 0; i < n-1; i++) p += '9';
        if (p != "") {
            ll tmp = stoll(p);
            ans = min(ans, abs(a-tmp));
        }
    }
    cout << ans << endl;
    return 0;
}