TopCoder SRM 712 Div1 Easy LR

これは本番思いついてよかったね。
https://community.topcoder.com/stat?c=problem_statement&pm=14569

問題

N要素の循環環整数列S,Tを考える。(A[N-1]の隣にA[0]があるとする)
Sに対し以下の処理を任意回数任意の順で行えるとき、Tを構成できるか。構成できるならその手順を答えよ。

• L : S[i]にS[i-1]を足しこむ、という処理を全i同時に行う
• R : S[i]にS[i+1]を足しこむ、という処理を全i同時に行う

解法

この処理で重要なことは、どちらの処理も生成されるSは同じだが、添え字が1ずれているということである。
さらにその派生として、LとRの順を逆にしても結果が同じ、1回処理を行うと全体の総和が倍になる、がある。

よって、LとRの回数だけ決めてしまえばよい。
最後の特性より、max(S)==0でない限りはlog(sum(T)/sum(S))回処理を行えばよいので、L,Rを総当たりしよう。

class LR {
	public:
	int N;
	string construct(vector<long long> s, vector<long long> t) {
		ll AS=0,AT=0;
		N=s.size();
		
		if(s==t) return "";
		FORR(a,s) AS+=a;
		FORR(a,t) AT+=a;
		
		if(AS==0 || AT%AS) return "No solution";
		int st=0;
		while(1LL<<st<AT/AS) st++;
		if(AS<<st != AT) return "No solution";

		int i,j;
		int LL,RR;
		FOR(LL,st+1) {
			RR=st-LL;
			vector<ll> f=s;
			string ret;
			FOR(i,LL) {
				ret+='L';
				vector<ll> v=f;
				FOR(j,N) v[j]+=f[(j+N-1)%N];
				f=v;
			}
			FOR(i,RR) {
				ret+='R';
				vector<ll> v=f;
				FOR(j,N) v[j]+=f[(j+1)%N];
				f=v;
			}
			
			if(t==f) return ret;
		}
		
		return "No solution";
		
		
	}
}

まとめ

終了直後、L,Rの順序を逆にしても結果は不変という点が重要という意見を見かけたけど、自分はL,Rどちらも同じ数列が生成されるという点が重要だと感じたな。