保存されている過去のバージョンの一覧

2017年03月26日10時43分01秒

「みんなのプロコン」本選 A問題 - YahooYahooYahoo

Source

「みんなのプロコン」本選
「みんなのプロコン」本選 オープンコンテスト
問題文

問題概要

文字列 $S$ が与えられるので，$\verb|yahoo|$ の繰り返しの文字列に変換するための最小の編集距離を求める問題．
つまり，コスト $1$ で，$1$ 文字削除，$1$ 文字追加，$1$ 文字を置き換えるという操作ができるので，
空文字，$\verb|yahoo|$，$\verb|yahooyahoo|$，…
のどれかに一致させるまでの最小コストを求める問題．

解法

DPする．
$\verb|dp[i][k]|$ を $S$ の最初の $\verb|i|$ 文字を（$\verb|yahoo|$ の繰り返し + $\verb|yahoo|$ の最初 $k$ 文字）に一致させるための最小コストとして計算していけば良い．
つまり，$\verb|dp[i][2]|$ は $\verb|yahoo...yahooya|$ に一致させるコスト．
実際には $S$ の $1$ 文字目から順番に処理していけば，$1$ 次元配列で十分．
時間計算量は $O(|S|)$ 程度（以下の実装だと，$\verb|yahoo|$ の文字数を $c$ として $O(c^2 |S|)$ 時間）．
以下の実装では，DPの添字は最後に対応させたのは $\verb|yahoo|$ の何文字目か，としているので上の説明と添字が1つズレている．

cLay（version 20170326-2）のコード

C++に変換後のコードはこちら

int N;
char S[100002];
char y[] = "yahoo";
int dp[5], nx[5];

{
  int i, j, k;

  rd(S);
  N = strlen(S);

  dp[0..3] = int_inf;
  dp[4] = 0;
  
  rep(k,N){
    nx[0..4] = dp[0..4] + 1;
    rep(i,5) if(y[i]==S[k]) rep(j,5) nx[i] <?= dp[j] + (9+i-j)%5;
    rep(i,5) if(y[i]!=S[k]) rep(j,5) nx[i] <?= dp[j] + 1 + (9+i-j)%5;
    dp[0..4] = nx[0..4];
  }

  wt(dp[4]);
}

Current time: 2024年04月23日21時53分16秒
Last modified: 2017年03月26日10時43分01秒 (by laycrs)
Tags: Competitive_Programming AtCoder yahoo-procon2017-final
トップページに戻る

Logged in as: unknown user (not login)

ログイン：