SRM 665 div1 easy:LuckySum

SRM 665 に参加しました。今回は 0 完でしたが運良く unrated になった(なりそう)のでレート下降は避けられそうです。

前にも今回のような感じで「全探索してもギリギリいけそうなきがするけどダメな制約」的な問題があったような気がするんですが, また引っかかりました。今度からは反省してちゃんとした解法を考えることにします。

問題

lucky number は10 進法でそれぞれの桁で 4 か 7 しか使わない数のことであり, lucky sum というのは 2 つの lucky number の和である。
14 桁以内の整数 note が, ある桁は '?' になり, ある桁は指定されて与えられる。'?' には好きな数が入っても良いとして, note が lucky sum になるという制約のもとで note の値を最小化せよ。

解法

まだ practice で通してないので本当に正解かはわからないです。通りました。

桁 DP で解きます。note の数が 2 つの lucky number A と B で表せるとして,
dp[n][d][az][bz]; を桁数が n の場所で 繰り上がりの数が d (0 か 1) で A の数がleading zero であるかどうかのフラグが az で B の数がleading zero であるかどうかのフラグが bz であるような場合の数であるとします。

そうするといい感じに桁 DP ができるのでがんばります。下のソースコードでコメントで少し説明つけたのでそちらでよろしくお願いします。

const ll INF = 1ll<<50;
const int digit[3] = {0, 4, 7};
ll dp[20][2][2][2]; // 桁, 繰り上がり, Aのzero, Bのzero
ll p10[20];

class LuckySum {
public:
    long long construct(string note) {
        int len = note.size();
        reverse(note.begin(), note.end());
        for (int i = 0; i < 20; i++) for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) for (int l = 0; l < 2; l++) {
                dp[i][j][k][l] = INF;
            }
        }
        p10[0] = 1;
        for (int i = 1; i < 20; i++) p10[i] = p10[i-1] * 10;
        dp[0][0][0][0] = 0;
        for (int n = 0; n < len; n++) for (int d = 0; d < 2; d++) {
            for (int az = 0; az < 2; az++) for (int bz = 0; bz < 2; bz++) {
                if (dp[n][d][az][bz] == INF) continue;
                for (int a = 0; a < 3; a++) for (int b = 0; b < 3; b++) {
                    int num = digit[a] + digit[b] + d;
                    // 一番小さい桁は 0 じゃダメ
                    if (n == 0 && (a==0 || b==0)) continue;
                    if (num == 0) continue;
                    // 数字があってなかったらダメ
                    if (note[n] != '?') {
                        if (note[n]-'0' != num%10) continue;
                    }
                    // leading zero
                    if (az == 1 && a > 0) continue;
                    if (bz == 1 && b > 0) continue;

                    // next state
                    int nd = (num >= 10);
                    int naz = az, nbz = bz;
                    if (a == 0) naz = 1;
                    if (b == 0) nbz = 1;
                    ll number = (num%10) * p10[n] + dp[n][d][az][bz];
                    dp[n+1][nd][naz][nbz] = min(dp[n+1][nd][naz][nbz], number);
                }
            }
        }
        ll ans = INF;
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
            ans = min(ans, dp[len][0][i][j]);
        }
        if (ans == INF) ans = -1;
        return ans;
    }
};