SRM 400 Medium: ReverseChain

SRM

競プロもうちょっと上に行きたいモチベあるので、mediumを不定期で解き漁る。
週に２，３問、問題は飛ばさずに全部解く、を目標。
続けるモチベの為にブログに解法乗っけていく。
とりあえず400くらいから順番に解いていくつもり。

初回はSRM400 500 ReverseChain

(問題概要)
r(i1, j1), r(i2, j2), ...という操作を繰り返す。

  1. r(i, j)は文字列の[i..j]をreverseする。(例、"abcd" -- r(1, 2) --> "acbd")
  2. i1 <= i2 <= ..., j1 >= j2 >= ...

文字列 init から goal まで何回の操作で変換できるか。

(解法)
2.の制約から、一旦(i, j)をひっくり返すと外側をひっくり返せないので、外側から決めていく。
initやgoalの見てるとこの両端とひっくり返っているかどうかでDPできる。
下の解法ではひっくり返っているかはゴールの両端のindexの大小を入れ替えることで表現。

#include <set>
#include <cstring>
#include <queue>
#include <iostream>
#include <sstream>

using namespace std;

class ReversalChain {
public:
  int minReversal(string init, string goal);
};

int memo[51][51][51][51];
string s;
string d;
const int MAX = 10000000;

int solve(int sl, int sr, int dl, int dr){
  if(sl == sr) return s[sl] == d[dl] ? 0 : MAX;
  if(memo[sl][sr][dl][dr] != -1) return memo[sl][sr][dl][dr];
  int ret = MAX;

  const int nextl = dl + (dl < dr ? 1 : -1);
  const int nextr = dr + (dl < dr ? -1 : 1);

  if(s[sl] == d[dl]) ret = min(ret, solve(sl + 1, sr, nextl, dr));
  if(s[sr] == d[dr]) ret = min(ret, solve(sl, sr - 1, dl, nextr));
  if(s[sl] == d[dr]) ret = min(ret, 1 + solve(sl + 1, sr, nextr, dl));
  if(s[sr] == d[dl]) ret = min(ret, 1 + solve(sl, sr - 1, dr, nextl));

  return memo[sl][sr][dl][dr] = ret;
}

int ReversalChain::minReversal(string init, string goal){
  s = init; d = goal;
  memset(memo, -1, sizeof(memo));
  int ret = solve(0, s.size() - 1, 0, s.size() - 1);
  return ret == MAX ? -1 : ret;
}