Codeforces #543 Div1 B. Once in a casino

答え方が珍しい問題。
https://codeforces.com/contest/1120/problem/B

問題

２つの同じ長さの整数A,Bが与えられる
隣接する２つの桁を両方インクリメント、またはデクリメントすることができる。
ただしそれにより繰り下げ・繰上げが生じてはならない。

このとき、AをBにすることができるか。
できるならその最小操作回数を求め、先頭100000手までを述べよ。

解法

まず変換可能かどうかを求めよう。
どちらの処理も偶数桁と奇数桁を同じく操作するので、A,Bで偶数桁と奇数桁の差が等しくないといけない。
逆に等しければ必ず変換可能である。

次に操作回数を求めよう。
これは、各桁一時的に負の値や10以上の値を許容することを仮定すると、頭の桁から順にそろえていけばいずれAはBにそろう。

さて、この手順を並べ替えて操作の回数を増やさず条件を守る方法を考えよう。
頭から順に桁をそろえていくのだが、デクリメントすると次の桁が負になりそうな場合、次の桁を先にインクリメントする、またはその逆、ということを再帰的に行うだけでよい。

int N;
string SA,SB;
ll A[101010],B[101010];

vector<pair<int,int>> C;
ll ret=0;


void dec(int cur);
void inc(int cur) {
	if(A[cur+1]==9) dec(cur+1);
	C.push_back({cur+1,1});
	A[cur]++;
	A[cur+1]++;
	ret++;
}
void dec(int cur) {
	if(A[cur+1]==0) inc(cur+1);
	C.push_back({cur+1,-1});
	A[cur]--;
	A[cur+1]--;
	ret++;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>SA>>SB;
	int D[2]={};
	FOR(i,N) {
		A[i]=SA[i]-'0';
		B[i]=SB[i]-'0';
		if(i%2) D[0]+=A[i],D[1]+=B[i];
		else D[0]-=A[i],D[1]-=B[i];
	}
	if(D[0]!=D[1]) return _P("-1\n");
	
	FOR(i,N-1) {
		if(ret<100000) {
			while(A[i]<B[i]) inc(i);
			while(A[i]>B[i]) dec(i);
		}
		else {
			A[i+1]+=B[i]-A[i];
			ret+=abs(B[i]-A[i]);
		}
	}
	
	if(C.size()>100000) C.resize(100000);
	cout<<ret<<endl;
	FORR(c,C) cout<<c.first<<" "<<c.second<<endl;
	
	
}

まとめ

言われてみればシンプル。