[ABC376] Hands on Ring (Hard)

[Q] Hands on Ring (Hard)
丁寧に場合分けをすれば確実にACできるはず！と思うものの、50分では間に合いませんでした///
残念。

考察
1. 最小手数になりうる選択肢は、時計回りと反時計回りの2通りしかない。
a. B問題の(Easy)で実装した、LRをまたがずに移動する周り。（緑線）
b. aと逆回りでLRどちらも移動する。（赤線）
になる。

2. ターン毎にありえそうな状況をmap[{L, R}] = 最小手数 として管理すれば、3000ターンのDPで間に合いそう。
3. 解答はmapに含まれている要素のうち最小手数。
4. (Easy)の入力値では、すでに違う手が置いてあるような入力は来なかった。(Hard)ではそういったシチュエーションがありうる。
5.入力値にすでに別の手が置いてある場合は、時計回りの場合はL+1に。反時計回りではL-1に動かす必要がある。

実装

int main() {
  ll N, Q;
  cin >> N >> Q;
  map<pll, ll> mp; mp[{L, R}] = 最小手数でDP
  mp[{0, 1}] = 0;
  rep(i, Q){
    char h;
    ll t;
    cin >> h >> t;
    --t;
    map<pll, ll> nmp;
    //// helper
    auto init=[&](ll l, ll r, ll c){
      if (nmp.count({l, r}) == 0){
        nmp[{l, r}] = c;
      }
      else{
        chmin(nmp[{l, r}], c);
      }
    };
    auto rotate_r=[&](ll l, ll r, ll tl, ll tr, ll c){ // 現在l, 現在r, 目的l, 目的r, cost
      init(tl, tr, c + (tl - l + N) % N + (tr - r + N) % N);
    };
    auto rotate_l=[&](ll l, ll r, ll tl, ll tr, ll c){
      init(tl, tr, c + (l - tl + N) % N + (r - tr + N) % N);
    };

    for(auto [p, c]: mp){ // 今時点でありうるシチュエーションから2通りの移動を行う
      auto [l, r] = p;
      vector<pll> V = {{l, 0}, {r, 1}, {t, 2}};
      sort(all(V));
      if (h == 'R'){
        if (r == t){ // すでに到達してるならおしまい
          init (l, r, c);
        }
        // LRT, RTL, TLR
        else if ((V[0].second == 0 && V[1].second == 1 && V[2].second == 2)
              || (V[0].second == 1 && V[1].second == 2 && V[2].second == 0)
              || (V[0].second == 2 && V[1].second == 0 && V[2].second == 1)){
          // (Easy) 時計回りが最短
          if (l == t) rotate_r(l, r, (l + 1) % N, t, c); // lの位置がtかもしれない。時計回りなのでl + 1に移動する
          else rotate_r(l, r, l, t, c);
          // 反時計回り
          rotate_l(l, r, (t - 1 + N) % N, t, c);
        }
        else{
          // (Easy) 反時計回りが最短
          if (l == t) rotate_l(l, r, (l - 1 + N) % N, t, c); // lの位置がtかもしれない。反時計回りなのでl - 1に移動
          else rotate_l(l, r, l, t, c);
          // 時計回り
          rotate_r(l, r, (t + 1) % N, t, c);
        }
      }
      else{
        if (l == t){
          init (l, r, c);
        }
        // lrt, rtl, tlr
        else if ((V[0].second == 0 && V[1].second == 1 && V[2].second == 2)
              || (V[0].second == 1 && V[1].second == 2 && V[2].second == 0)
              || (V[0].second == 2 && V[1].second == 0 && V[2].second == 1)){
          if (r == t) rotate_l(l, r, t, (r - 1 + N) % N, c);
          else rotate_l(l, r, t, r, c);
          rotate_r(l, r, t, (t + 1) % N, c);
        }
        else{
          if (r == t) rotate_r(l, r, t, (r + 1) % N, c);
          else rotate_r(l, r, t, r, c);
          rotate_l(l, r, t, (t - 1 + N) % N, c);
        }
      }
    }
    swap(mp, nmp); // 次のシチュエーションがnmp
  }

  // ありうるシチュエーションのうち、最小手数が答え
  ll ans = oo;
  for(auto[p, c]: mp){
    chmin(ans, c);
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc376/submissions/58992489