SRM 665 Div2 Hard LuckySum

TopCoder Statistics - Problem Statement

• 復習。復習。
• 最後の桁と最初の桁だけ例外判定が必要。
• こういう dp はまだまだパッと思いつかない。

class LuckySum {
public:
    //
    // a,b を 1桁目から確定させていく。
    // 各桁は 0,4,7 の組み合わせ(0 は leading zero 、つまり a,b の桁数が異なるケース)と
    // 前の桁の繰り上がりとの和で決定する。
    // よって状態として 桁数とくりあがりの有無と leading zero の有無の (n,u,z) となる。
    //
    // dp[n][u][z] := a+b の n 桁目までで条件を満たすものの最小値
    //                u==1 のときは桁上がりがある。
    //                z==0 のときは a, b ともにまだ leading zero でない
    //                z==1 のときは a は leading zero
    //                z==2 のときは b は leading zero
    //
    // として DP すればよい。
    //
    long long construct(string note) {
            int len = note.length();
            const ll  inf = (1LL<<60);

            // 1 桁目からみていくので逆順にしておく
            reverse(RANGE(note));


            // 10^k 倍用に用意
            vector<ll> p10(len+1,0);
            p10[0] = 1;
            REP(i,len)
                p10[i+1] = 10*p10[i];

            ll dp[len+1][2][3];
            REP(i,len+1)
            REP(j,2)
            REP(k,3)
                dp[i][j][k] = inf;
            dp[0][0][0] = 0;

            for (int l = 0; l < len; ++l)
            REP(u,2)
            REP(z,3)
            {
                // そこまで遷移不可なら飛ばす
                if (dp[l][u][z]==inf)
                    continue;

                const int lucky[] = {0,4,7};
                REP(a,3)
                REP(b,3)
                {
                    // 0 桁目が leading zero はダメ
                    if ( l==0 && (a==0 || b==0))
                        continue;
                    // すでに leading zero なら使えるものは 0 のみ
                    if ( z==1 && a!=0 )
                        continue;
                    if ( z==2 && b!=0 )
                        continue;
                    // 両方 leading zero がゆるされるのは
                    if ( a==0 && b==0 )
                    {
                        // 最後の桁で繰り上がりがあるときのみ
                        if ( !(l+1==len && u==1) )
                            continue;
                    }

                    // 0,4,7 を使って n 桁目を足し合わせる。このとき繰り上がり分 u も加える
                    int num = lucky[a]+lucky[b]+u;

                    // 指定されている数と違ったら飛ばす
                    if (note[l] != '?' && num%10 != note[l]-'0')
                        continue;

                    int nz = 0;
                    // この桁で使われるのが 0 なら次の桁以降で leading zero になるはず。       
                    if (z == 1 || a == 0)
                        nz = 1;
                    if (z == 2 || b == 0)
                        nz = 2;
                    // 更新
                    dp[l+1][num/10][nz] = min(dp[l+1][num/10][nz],
                                              (num%10)*p10[l]+dp[l][u][z]);
                }
            }
            ll res = inf;
            REP(z,3)
            {
                res = min(res, dp[len][0][z]);
            }
            if (res == inf)
                return -1;
            return res;
    }
};