kmjp's blog

競技プログラミング参加記です

yukicoder : No.1818 6 Operations

今日は余り時間を掛けられず。
https://yukicoder.me/problems/no/1818

問題

整数列Aに対し、以下の処理を行う。

  • 1要素をインクリメントする
  • 1要素をデクリメントする
  • 隣接する2要素を、その和をとる1要素に差し替える
  • 隣接する2要素を、その和+1をとる1要素に差し替える
  • 1要素を、2つの要素に差し替える。2要素の和は、元の要素である。
  • 1要素を、2つの要素に差し替える。2要素の和は、元の要素-1である。

AをBに一致させるには、最小何回処理を行う必要があるか。

解法

A,Bに対応し、以下のように文字列を生成する。
各要素xに対し、0のあとに1をxをくっ付けた文字列を対応させ、それぞれ連結する。
そうすると、上記処理は下記のように対応づく。

  • 1を1個挿入する
  • 1を1個削除する
  • 0を1個削除する
  • 0を1に置き換える
  • 0を1個挿入する
  • 1を0に置き換える

こう考えると、結局AとBに対応づく文字列の編集距離が解となる。

int dp[4030][4030];
int N,M;
vector<int> A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		A.push_back(0);
		FOR(j,x) A.push_back(1);
	}
	N=A.size();
	FOR(i,M) {
		cin>>x;
		B.push_back(0);
		FOR(j,x) B.push_back(1);
	}
	M=B.size();
	
	FOR(x,N+2) FOR(y,M+2) dp[x][y]=1<<30;
	dp[0][0]=0;
	FOR(x,N+1) FOR(y,M+1) if(dp[x][y]<1<<30) {
		int r=dp[x][y];
		chmin(dp[x+1][y],r+1);
		chmin(dp[x][y+1],r+1);
		chmin(dp[x+1][y+1],r+1);
		if(x<N&&y<M&&A[x]==B[y]) chmin(dp[x+1][y+1],r);
	}
	cout<<dp[N][M]<<endl;
	
}

まとめ

01111…に置き換えることはすぐ考えたけど、そのあと細かいところが合わなかった。