Codeforces #645 Div2 F. Tasty Cookie

またCodeforcesの記事書くの2週間空いてしまった。
http://codeforces.com/contest/1358/problem/F

問題

N要素の整数列A,Bが与えられる。
Aに以下の手順を繰り返しBにしたい。

• Aを反転する
• AをAのprefix sumにする。

可能ならその手順を求めよ。

解法

AをBにするのではなく、BをAに戻すことを考えよう。
prefix sumの逆演算を行えるかどうかは、Bが昇順かどうかで容易に判断できるので、反転の必要性が容易に判定できる。

Aの初期値は最低1なので、prefix sumをk回取ると末尾がO(k^(N-1))とすごい勢いで増える。
よってNが3以上なら愚直にBをAにしていけばよい。
N=2の時は、コーナーケースに注意し、prefix sumの逆演算を複数回まとめてとることも考えて注意深くBをAにしよう。

int N;
vector<ll> A,B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	A.resize(N);
	B.resize(N);
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	if(A==B) {
		cout<<"SMALL"<<endl;
		cout<<"0"<<endl;
		cout<<endl;
		return;
	}
	
	if(N>=3) {
		string S;
		while(A!=B) {
			reverse(ALL(B));
			if(A==B) {
				S+="R";
				break;
			}
			reverse(ALL(B));
			FOR(i,N-1) if(B[i]>=B[i+1]) break;
			if(i<N-1) {
				reverse(ALL(B));
				S+="R";
			}
			FOR(i,N-1) if(B[i]>=B[i+1]) break;
			if(i<N-1) {
				cout<<"IMPOSSIBLE"<<endl;
				return;
			}
			S+="P";
			for(i=N-1;i>=1;i--) B[i]-=B[i-1];
		}
		reverse(ALL(S));
		int R=count(ALL(S),'P');
		if(R>200000) {
			cout<<"BIG"<<endl;
			cout<<R<<endl;
		}
		else {
			cout<<"SMALL"<<endl;
			cout<<S.size()<<endl;
			cout<<S<<endl;
		}
		return;
	}
	else if(N==2) {
		ll np=0;
		vector<pair<char,ll>> S;
		while(A!=B) {
			reverse(ALL(B));
			if(A==B) {
				S.push_back({'R',1});
				break;
			}
			reverse(ALL(B));
			if(B[0]>B[1]) {
				reverse(ALL(B));
				S.push_back({'R',1});
			}
			if(B[0]==B[1] || B[0]<min(A[0],A[1]) || B[1]<max(A[0],A[1])) {
				cout<<"IMPOSSIBLE"<<endl;
				return;
			}
			
			if(B[0]==min(A[0],A[1])) {
				if((B[1]-max(A[0],A[1]))%B[0]==0) {
					np+=(B[1]-max(A[0],A[1]))/B[0];
					S.push_back({'P',(B[1]-max(A[0],A[1]))/B[0]});
					B[1]=max(A[0],A[1]);
				}
				else {
					cout<<"IMPOSSIBLE"<<endl;
					return;
				}
			}
			else {
				np+=B[1]/B[0];
				S.push_back({'P',B[1]/B[0]});
				B[1]%=B[0];
			}
		}
		if(np>200000) {
			cout<<"BIG"<<endl;
			cout<<np<<endl;
		}
		else {
			string T;
			FORR(c,S) {
				FOR(x,c.second) T+=c.first;
			}
			reverse(ALL(T));
			cout<<"SMALL"<<endl;
			cout<<T.size()<<endl;
			cout<<T<<endl;
		}
		return;
	}
	cout<<"IMPOSSIBLE"<<endl;
}

まとめ

N=2が異様にめんどいな。