AOJ2157 Dial Lock - ferinの競プロ帳

考えたこと

状態数が最大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;
}