WARush

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

SRM607 Div1 Medium "CombinationLockDiv1"

問題

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 <= ダイヤルの数 <= 2500


Editorialsを見て

Div2の簡単版はN(ダイヤルの数)=50なので、O(N^3)でいけた。しかし、Div1では2500となり、O(N^3)なんてやってられない。どうするか?どうやらDiv2の考え方をそのままに、最適化すると(N^2)まで減らせるとのこと。

Div2では、状態(ダイヤルの位置・回した方向・回した数)のそれぞれを更新するのに、MAX_OP回=O(N)かかっていたが、ここが無駄らしい。

ダイヤルの初期状態がこんな感じだとする。

start -> ????58????
target-> ????05????
             ||
             AB

例えば、ダイヤルAをプラス方向に15回して揃えました~って時に、ダイヤルBを1003回して揃えた時のコストはいくつかな?とか考える必要あるかと言われれば、確かに無駄である。回しすぎである。

ダイヤルA・プラス方向・15回。という情報を元に、ダイヤルBを更新するとき、以下の3パターンだけ考えればよい。

1.足りない分は頑張ってもうちょい回してみる

プラス方向に15回してダイヤルAを揃えたということは、ダイヤルBもプラス方向に15回までなら、コスト0で回せるということである。しかし、それで回しが足りない場合が当然ある。例に沿うと、Bをプラス方向に15回すと3になり、目標の5まで2回足りない。そこを頑張ってさらに2回回して揃えてみようか、というやり方である。コストは2だけ余計にかかってしまうが、B以降のダイヤルは、コスト0で17も自由に回せるようになる。

2.途中でそろったからなまける

プラス方向に15回すうちに、ダイヤルBが目標の数字は通り過ぎている。じゃあ15回さないで、ダイヤルBを途中で止めればよくね?5で止めちゃえばよくね?という回し方もある。確かにこれだとコストをさらにかけることなく、ダイヤルBを揃えることができる。しかし、8 -> 5へと7回しか回していないので、B以降のダイヤルは、コスト0で回せる幅が7回に狭まってしまう。

3.流れに逆らう

前までプラス方向に回していたなんて関係ねぇ。俺は俺の道をゆく。ということで、あえてマイナス方向に回すやり方もある。前のダイヤルたちが頑張って、コスト0でプラス方向に15回せるようにしてくれた訳だが、その恩恵は受けられず、コストは3かかる。B以降のダイヤルは、コスト0でプラス方向に回せなくなる代わりに、マイナス方向に3まで回せるようになる。

結果

と、言うわけで、1回の更新がO(1)となるので、計算量は状態数と同じ、O(N * N*9) = O(N^2)となる。


ソースコード

int N; // ダイヤルの長さ
int S[2550]; // ダイヤルS
int T[2550]; // ダイヤルT
int U[2550]; // +方向にどんだけ回せばいい?
int D[2550]; // -方向に(ry
int dp[2][MAX_OP + 50][2];

class CombinationLockDiv1 {
public:
    
    // targetを最小で更新する
    void setMin(int& target, int cand){
        target = min(target, cand);
    }

    int minimumMoves(vector <string> P, vector <string> Q) {
        // 入力
        int c = 0;
        for (int i = 0; i < P.size(); i++) {
            for (int j = 0; j < P[i].size(); j++) {
                S[c++] = P[i][j] - '0';
            }
        }
        c = 0;
        for (int i = 0; i < Q.size(); i++) {
            for (int j = 0; j < Q[i].size(); j++) {
                T[c++] = Q[i][j] - '0';
            }
        }
        N = c;
        for (int i = 0; i < N; i++) {
            U[i] = (T[i] - S[i] + 10) % 10;
            D[i] = 10 - U[i];
        }

        // dp初期化
        for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= MAX_OP; j++) {
                for (int k = 0; k <= 1; k++) {
                    dp[i][j][k] = INF;
                }
            }
        }

        c = 0;
        int n = 1;

        // dp更新
        for (int i = 0; i < N; i++) {
            // 最初は何も考えずに揃える
            if (i == 0){
                // -方向
                dp[c][D[i]][0] = D[i];
                // +方向
                dp[c][U[i]][1] = U[i];
            }

            // 次のダイヤルを揃えて行く
            for (int up = 0; up <= 1; up++){
                for (int op = 0; op <= MAX_OP; op++) {
                    int cost = dp[c][op][up];
                    if (cost == INF) continue;
                    
                    if (up == 0){
                        // 前回-方向でそろえた    
                        // がんばる
                        int s = op % 10;
                        int t = D[i];
                        int add = (t - s + 10) % 10;
                        setMin(dp[n][op + add][up], cost + add);

                        // なまける
                        int rem = (10 - t + s) % 10;
                        if (rem <= op) setMin(dp[n][op - rem][up], cost);

                        // さからう
                        setMin(dp[n][U[i]][1 - up], cost + U[i]);
                    }else{
                        // 前回+方向でそろえた
                        // がんばる
                        int s = op % 10;
                        int t = U[i];
                        int add = (t - s + 10) % 10;
                        setMin(dp[n][op + add][up], cost + add);

                        // なまける
                        int rem = (10 - t + s) % 10;
                        if (rem <= op) setMin(dp[n][op - rem][up], cost);

                        // さからう
                        setMin(dp[n][D[i]][1 - up], cost + D[i]);
                    }
                }
            }
            
            // 次のdpの準備
            c = 1 - c;
            n = 1 - n;
            for (int j = 0; j <= MAX_OP; j++) {
                for (int k = 0; k <= 1; k++) {
                    dp[n][j][k] = INF;
                }
            }
        }
        
        // dp集計
        int ans = INF;
        for (int op = 0; op < MAX_OP; op++) {
            for (int up = 0; up <= 1; up++) {
                setMin(ans, dp[c][op][up]);
            }
        }

        return ans;
    }
};