TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

文字列$s$が与えられて，カーソルは今一番最初の文字にある．操作として

カーソルを右に動かす
カーソルを左に動かす
カーソルにある文字を打ち出す

をすることができる．この操作の中で辞書順最小に打ち出す時，最小何回で行うことができるか．

$$ dp[i][j] := アルファベットiを場所jで打ち終わった時の最小値 $$

として動的計画法．$s$中の全てのアルファベットの両端のindexを$vmin, vmax$として，また場所のvectorを持っておく．次のアルファベット$\alpha$を打ち終わることを考えるとき，必ず打ち終わる場所は$\alpha$のはずなので，事前に持っておいたvectorの場所のみ遷移可能である．$pre$を場所$j$で打ち終わった場合から，$alpha$を場所$id[k]$で打ち終わった場合への遷移を考えると，$\alpha$の右端のindex:$vmax$が$j$より小さい時は$j$$\to$$vmin$$\to$$id[k]$という経路で行くのが最小である．同様に$\alpha$の左のindex:$vmin$が$j$より小さい時は$j$$\to$$vmax$$\to$$id[k]$という経路で行くのが最小である．どちらの場合でも無い場合は$vmin$に行って戻ってくるパターンと$vmax$に行って戻ってくるパターンを試した．

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int dp[30][55]; //alphaまでを位置jで打ち終わった時に最小値

class LexStringWriter {
  public:
  int minMoves(string s) {
      int n = s.size();
      map<int, vector<int> > m;
      map<int, int> vmax, vmin;
      rep(i, n) {
          int x = s[i] - 'a' + 1;
          m[x].push_back(i);

          if(vmax.count(x) == 0) {
              vmax[x] = i;
          } else {
              vmax[x] = max(vmax[x], i);
          }

          if(vmin.count(x) == 0) {
              vmin[x] = i;
          } else {
              vmin[x] = min(vmin[x], i);
          }
      }

      string t = s;
      sort(t.begin(), t.end());

      rep(i, 30) rep(j, 55) {
          dp[i][j] = INF;
      }
      int pre = 0;
      dp[pre][0] = 0;

      each(it, m) {
          int alpha = it->first;
          vector<int> id = it->second;

          rep(j, n) {
              if(dp[pre][j] == INF) continue;

              rep(k, id.size()) {
                  if(vmax[alpha] <= j) {
                      dp[alpha][id[k]] = min(dp[alpha][id[k]], dp[pre][j] + abs(j - vmin[alpha]) + abs(vmin[alpha] - id[k]) + (int)id.size());
                  } else if(j <= vmin[alpha]) {
                      dp[alpha][id[k]] = min(dp[alpha][id[k]], dp[pre][j] + abs(j - vmax[alpha]) + abs(vmax[alpha] - id[k]) + (int)id.size());
                  } else {
                      int left = 2 * abs(j - vmax[alpha]) + abs(j - vmin[alpha]) + abs(vmin[alpha] - id[k]) + id.size();
                      int right = 2 * abs(j - vmin[alpha]) + abs(j - vmax[alpha]) + abs(vmax[alpha] - id[k]) + id.size();
                      dp[alpha][id[k]] = min(dp[alpha][id[k]], dp[pre][j] + min(left, right));
                  }
              }
          }

          pre = alpha;
      }

      int ans = INF;
      int last = int(t[t.size()-1] - 'a' + 1);
      rep(i, m[last].size()) {
          int j = m[last][i];
          ans = min(ans, dp[last][j]);
      }

      return ans;
  }
};

ry0u_ydのblog

SRM321 D2H LexStringWriter

TopCoder Statistics - Problem Statement

Code