WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM665 Div1 Easy "LuckySum"

解法

以下、参考にさせていただきました。m(_ _)m
kmjp.hatenablog.jp

事後

実装がちょっと難しくなると頭が混乱するのなんとかして

ソースコード

const long long INF = 123456789012345LL;
long long dp[20][2][3];
int sums[20];

class LuckySum {
    public:
    long long construct(string note) {
        int n = note.size();

        // sums初期化
        for (int i = 0; i < n; i++)
            sums[n - i - 1] = note[i] == '?' ? -1 : note[i] - '0';

        // dp初期化
        for (int d = 0; d <= n; d++)
            for (int c = 0; c < 2; c++)
                for (int e = 0; e < 3; e++)
                    dp[d][c][e] = INF;

        dp[0][0][0] = 0;

        // dp更新
        int ds[] = {7, 4, 0};
        long long p_10 = 1;
        for (int d = 0; d < n; d++) {
            for (int c = 0; c < 2; c++) for (int e = 0; e < 3; e++) {
                if (dp[d][c][e] == INF) continue;

                for (int i = 0; i < 3; i++)  for (int j = 0; j < 3; j++) {
                    int a = ds[i];
                    int b = ds[j];
                    int s = a + b + c;
                    int dight = s % 10;
                    int carry = s / 10;
                    int end = (a == 0 ? 1 : 0) + (b == 0 ? 1 : 0);

                    // 未完了のlackyNumberの数より使用するLackyNumberの数の方が多ければやらない
                    if (2 - e < 2 - end) continue;

                    // 最初の桁であり、endが1以上であればやらない
                    if (d == 0 && end >= 1) continue;

                    // sumsと合っていなければやらない
                    if (sums[d] != -1 && sums[d] != dight) continue;

                    // endが2であり、最後の桁でない、または繰り上がりがなければやらない
                    if (end == 2 && (d != n - 1 || c == 0)) continue;

                    dp[d + 1][carry][end] 
                        = min(dp[d + 1][carry][end], dp[d][c][e] + dight * p_10);
                }
            }
            p_10 *= 10;
        }

        // dp答え
        long long ans = INF;
        for (int e = 0; e < 3; e++) {
            ans = min(ans, dp[n][0][e]);
        }
        return ans == INF ? -1 : ans;
    }
};