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