AOJ2157 Dial Lock
問題ページ
Dial Lock | Aizu Online Judge
考えたこと
- 状態数が最大10^10あるから愚直は無理
- 回転させる数だけ気にすればいい気持ちになる
- i桁目について (t[i]-s[i]+10)%10 回回せばいい
- +1 +2 +4 +2 みたいなのが来たときに+2から+2の区間をまとめて回せば一回減らせる
- 一桁ずつ回せば必ずつくれるので答えの上限はK
- どれだけ減らせるかみたいなのを考える
- 回す数が同じところはまとめて1回で回せるので減らせそう
- +2 +4 +2 +4 みたいに区間が交差してると両方ともうまくまとめるのは無理で1回しか減らせない
- 区間DPとかをしたい気持ちになる
- dp[i][j] = ([i,j]を揃えるのに必要な最小の回転回数) みたいなのをやりたくなる
- dp[i][j] = min(dp[i][k] + dp[k][j]) みたいな更新をしたくなる
- (+2 +2)(+2 +1) みたいなのをマージしたいときに上の更新式を使うと +2 の回転をまとめきれていなくて正しくならない
- 左と右で同じ数字の個数を数えるみたいなのをやろうとすると (+4 +4 +2 +2 +4)(+2 +1) みたいなのでつらい
- +4をまとめてると左の+2と右の+2をマージしてはいけない
- 遷移が明らかにやばくて何もわからない
-----解説を見た----- - [a,b]を回すときに先頭の要素aをあわせるように回せばいい
- i番目を回すときにどこまで一緒に回すかでK-i通りある
- 全探索すると K*(K-1)*(K-2)*…*1 になってO(K!)
愚直10^10だけど有効な改善される遷移だけを考えると実はそんなにないので計算量が落ちるパターン
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) const ll LLINF = (1LL<<60); template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); while(true) { int n; cin >> n; if(!n) break; string s, t; cin >> s >> t; int ans = LLINF; function<void(int,int,string)> dfs = [&](int idx, int cost, string str) { if(idx == n || str == t) { chmin(ans, cost); return; } // idx番目をstr[idx]->t[idx]にもっていくのにかかるコスト int diff = (t[idx]-str[idx]+10)%10; // [idx, i] を回転させる FOR(i, idx, str.size()) { str[i] = ((str[i]-'0') + diff)%10 + '0'; dfs(idx+1, cost+(diff==0?0:1), str); } }; dfs(0, 0, s); cout << ans << endl; } return 0; }