Google Code Jam 2020 Round 3 : A. Naming Compromise

相変わらずRound3は難しく、完答はAだけ。でも順位的には自己ベスト。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019ff7e/00000000003774db

問題

2つの文字列A,Bの編集距離をf(A,B)と表すとする。
2つの文字列C,Jが与えられる。
空でない文字列Gのうち、f(C,G)+f(J,G)=f(C,J)かつ|f(C,G)-f(J,G)|≦1となるものを示せ。

解法

まずf(C,J)について、通常のメモ化再帰なりDPの手続きで2次元テーブルを埋めよう。
そのあと、2次元テーブルを復元していくのだが、その際CとJそれぞれから交互に編集距離が増えていくように復元する。
例えば今テーブルにおいてC[x]とJ[y]を比べるとき、「C[x]を消す」か「JにC[x]を挿入する」はそれぞれf(C,J)を1増す効果があるが、f(C,G)とf(J,G)を見るとどちらかが1増えるようになる。

途中Gが空文字になりかねないケースがあるが、C側とJ側どちらを先に編集距離を増やすか、両パターンやったらACできた。

string A,B;
int N,M;

int dp[61][61];
pair<int,int> nex[61][61];
int hoge(int x,int y) {
	if(dp[x][y]>=0) return dp[x][y];
	if(x==N&&y==M) return 0;
	dp[x][y]=101010;
	if(x<N) {
		if(dp[x][y]>1+hoge(x+1,y)) {
			dp[x][y]=min(dp[x][y],1+hoge(x+1,y));
			nex[x][y]={x+1,y};
		}
	}
	if(y<M) {
		if(dp[x][y]>1+hoge(x,y+1)) {
			dp[x][y]=min(dp[x][y],1+hoge(x,y+1));
			nex[x][y]={x,y+1};
		}
	}
	if(x<N&&y<M) {
		if(dp[x][y]>(A[x]!=B[y])+hoge(x+1,y+1)) {
			dp[x][y]=min(dp[x][y],(A[x]!=B[y])+hoge(x+1,y+1));
			nex[x][y]={x+1,y+1};
		}
	}
	return dp[x][y];
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>A>>B;
	N=A.size();
	M=B.size();
	MINUS(dp);
	hoge(0,0);
	int dif=0;
	x=y=0;
	string R[2];
	while(x<N||y<M) {
		
		if(nex[x][y].first==x+1 && nex[x][y].second==y+1) {
			if(A[x]==B[y]) {
				R[0]+=A[x];
				R[1]+=A[x];
			}
			else {
				if(dif==0) {
					R[0]+=B[y];
					R[1]+=A[x];
				}
				else {
					R[1]+=B[y];
					R[0]+=A[x];
				}
				dif^=1;
			}
			x++;
			y++;
		}
		else if(nex[x][y].first==x+1) {
			if(dif==0) {
				R[1]+=A[x];
			}
			else {
				R[0]+=A[x];
			}
			dif^=1;
			x++;
		}
		else {
			if(dif==0) {
				R[0]+=B[y];
			}
			else {
				R[1]+=B[y];
			}
			dif^=1;
			y++;
		}
	}
	
	if(R[0].empty()) swap(R[0],R[1]);
	_P("Case #%d: %s\n",_loop,R[0].c_str());
}

まとめ

割とてまどった。