WARush

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

SRM607 Div2 Hard "CombinationLockDiv2"

問題

TopCoder Statistics - Problem Statement

アンドリューはダイアル錠を持っている。この鍵は複数のダイヤルが並ぶようにしてできている。それぞれのダイヤルは0~9の数字が順番に並んでいる。そして、各ダイヤルでは、ただ1つの数字が見えるようになっている。現在見えている数字を文字列にしたものを"current combination"と呼ぶ。

ダイヤルでの見えている数字は、それを上か下に回すことによって変えることができる。上に回せば0が1に、1が2に、となっていく。そして、9ならば0が再び見えるようになる。下に回す場合は、この逆である。

隣接したものならば、複数のダイアルを一気に回すこともできる。正確には、隣接した複数のダイヤルを1ステップで同じ方向にいっぺんに回すことができる。

例えば、current combinationが"123"だとする。1ステップで"012"(全てのダイヤルを下に回す)や、"133"(真ん中のダイヤルを上に)や、"013"(最初と2番目のダイヤルを下に)など、いろいろ変えることができる。また、"123"を"224"と1ステップではできない。

あなたは文字列S, Tが与えられる。Sはcurrent combinationであり、Tは鍵を開けるためのsecret combinationである。ダイヤルを回転させることによってSからTへと変化させ、鍵を開けたい。最小のステップ数を返せ。

制約

1 <= ダイヤルの数 <= 50


Editorialsを見て

最適解を得る回し方で、ひとつのダイヤルを上に回したり下に回したりすることはない。
というか、上に回すだけ、もしくは下に回すだけ、で置き換えることができるから、考える必要はない。

という特性を利用すると、下記DPを得る。

dp[id][op][d] := id番目をd方向にopだけ回して、id番目のダイヤルまで揃えた時のステップ数

  • 初期化

dp[id][op][d] = INF
dp[0][0][up or down] = 0

  • 更新

現在考えているダイヤルの回す方向をcd、直前のダイヤルの回した方向をpd.
現在考えているダイヤルの回す回数をcop、直前のダイヤルの回した回数をdop.

cd == pdの時
新たにかかるステップ数はcost = max(cop - pop, 0)
dp[id+1][cop][cd] = dp[id][pop][pd] + cost

cd != pdの時
新たにかかるステップ数はcost = cop
dp[id+1][cop][cd] = dp[id][pop][pd] + cost

感想

なにこれむずい


ソースコード

int S[55];
int T[55];
int N;
int MAX_OP = 450;

int dp[55][500][500];

int count1 = 0;

class CombinationLockDiv2 {
public:

    int dfs(int id, int pop, int pd){
        // 揃え切った
        if (id == N) return 0;

        int& res = dp[id][pop][pd];
        
        // メモってたら、メモを返す
        if (res != -1) return res;

        res = MAX_OP;

        for (int cd = 0; cd <= 1; cd++){
            for (int cop = 0; cop <= MAX_OP; cop++){
                // Tにいかないならやり直し
                if (cd == 0){
                    if ((T[id] - S[id] + cop) % 10 != 0) continue;
                }else{
                    if ((S[id] - T[id] + cop) % 10 != 0) continue;
                }

                int step;
                if (pd == cd){
                    // 前回と同じ方向
                    step = max(cop - pop, 0);
                }
                else{
                    // 前回と違う方向
                    step = cop;
                }

                res = min(res, dfs(id + 1, cop, cd) + step);
            }
        }

        return res;
    }

    int minimumMoves(string _S, string _T) {
        N = _S.size();

        for (int i = 0; i < N; i++){
            S[i] = _S[i] - '0';
            T[i] = _T[i] - '0';
        }

        memset(dp, -1, sizeof(dp));
        
        return dfs(0, 0, 0);
    }
};