解いた問題のソースコードと解説など。


Members SRM 461 Div2 Hard NameInput

問題

これは入力カーソルを使用して文字列を入力する問題である。
文字列を含んだvector < string > predictionSequence と name が与えられる。 これらをそれぞれについて結合した文字列をS,Tとする。入力カーソルが最初Sの先頭に来ているものとして、カーソルはSの文字列上で右か左に一つ動かすことができ、これで一回の移動とする(カーソルがSの左端に来ている時に左に移動するならカーソルは右端に移動する。右端に来ている時に右に移動するなら左端に移動する)。
入力したい文字にカーソル来ている時にエンターを押して入力する。エンターを押す動作はカウントしない。このシステムを使用してTを入力するために必要な最短移動回数はいくらか?

やりかた

幅優先探索で間に合う。
一回移動するたびに移動回数を+1してキューに突っ込んでいく。ただし、なんども同じ状態に訪れないようにその状態に訪れた最小移動回数を記録しておき、それより多い手順で訪れようとしている時にはキューに突っ込まないようにして、探索をしないようにする。状態の保持の仕方は

dp[i][j] :=(文字列Sのi番目の文字にカーソルがある状態から文字列Tのj番目の文字を入力するための最小手順回数)

として持っておく。

以下ソース。

int dp[2501][2501];

class NameInput {
public:
  int countUpDownKeyPresses(vector <string> predictionSequence, vector <string> name) {
    string ps, na;
    for(int i = 0; i < (int)predictionSequence.size(); i++)
      ps += predictionSequence[i];
    for(int i = 0; i < (int)name.size(); i++)
      na += name[i];

    int L = ps.length();

    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    int result = INF;
    queue<pair<int, int> > Q;
    Q.push(make_pair(0, 0));
    while(!Q.empty()){
      int i = Q.front().first;
      int j = Q.front().second;
      Q.pop();
      
      //文字列を入力し終わった
      if(j == (int)na.length()){
	result = min(result, dp[i][j]);
	continue;
      }
      
      //Sのi番目とTのj番目の文字が合致したらTの次の文字の入力を頑張る
      if(ps[i] == na[j]){
	if(dp[i][j + 1] < 0){
	  dp[i][j + 1] = dp[i][j];
	  Q.push(make_pair(i, j + 1));
	}
      }
      
      //右に動く
      int t = (i + 1) % L;
      if(dp[t][j] < 0){
	dp[t][j] = dp[i][j] + 1;
	Q.push(make_pair(t, j));
      }

      //左に動く
      t = (i - 1 + L) % L;
      if(dp[t][j] < 0){
	dp[t][j] = dp[i][j] + 1;
	Q.push(make_pair(t, j));
      }
    }
    return result == INF ? -1 : result;
  }

同じ文字に何度か訪れるため、そこをうまく弁別してやればダイクストラでもやれるかなと思ったが、すごく面倒になってしまうため、断念した。

しょげないでよBaby 眠れば治る