今日は余り時間を掛けられず。
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…に置き換えることはすぐ考えたけど、そのあと細かいところが合わなかった。