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; } };