2017-04-18

SRM 712 300 LR

22:28 |

長さ N の数列 s, t が与えられる。最初と最後はつながっている。
操作 L: 左の要素と現在の要素を足したものを新しい要素の値とする
操作 R: 右の要素と現在の要素を足したものを新しい要素の値とする
操作 L, R を最大 100 回行って s が t になるならその手順、ならなければ "No solution" を返せ。
2≦N≦50, 0≦要素≦10^15

1 0 0 0 から始めるとどうなるか? → 1 1 -> 1 2 1 -> 1 3 3 1 -> 二項係数になる。→特に発展せず
探索してくと意外とすぐ狭まるやつ? →どうもそうでもない
逆から考えると何か分かるか? →わからず
数列の合計は L, R どちらをやっても 2 倍に増える
なので 10^15≒2^50 ということで解があるなら 50 回くらいやれば十分。
う〜ん

(しばらくして)

紙上で A B C D E を LL LR RL RR してどうなるか見てみると LR RL が同じになりそう
実験くん
全部並びとしては同じで、適用結果はLL...LLL の結果を R の数だけ左回転したものになる
(気づくのが遅い)

Σt = 2^M*Σs のとき、s に L を M 回適用した後の並びを M 回以下の R 回左シフトしたものが t と一致したら R 個の 'R' と M-R 個の 'L' をつなげたやつが答え。

Challengeされる

🤔

Σs==0 のとき無条件に "No solution" にしていたorz orz
Σs==0 でも s==t なら "" を返すんだった。
せっかく思いついたのにもったいない.....
🤔

Accepted in practice

VI rot(const VI& a, char d) {
	int lr = d=='L' ? -1 : 1;
	int N = a.size();
	VI rv(N);
	REP(i, N) rv[i] = a[(i+lr+N)%N]+a[i];
	return rv;
}

VI rotN(const VI& a, string d) {
	VI rv(a);
	for(auto c : d) rv = rot(rv, c);
	return rv;
}

VI shiftL(const VI& a) {
	int N = a.size();
	VI rv(N);
	REP(i, N) rv[i] = a[(i+1)%N];
	return rv;
}

class LR {
	public:
	string construct(vector<long long> s, vector<long long> t) {
		ll ss = accumulate(ALL(s), 0LL);
		ll st = accumulate(ALL(t), 0LL);
		if(ss>st) return "No solution";
		if(ss==st) {
			return s==t ? "" : "No solution";
		}
		if(ss==0) return "No solution";
		int cnt = 0;
		{
			bool ok = false;
			while(ss<=st) {
				if(ss==st) {
					ok=true;
					break;
				}
				ss*=2;
				cnt++;
			}
			if(!ok) return "No solution";
		}
		VI w(s);
		REP(i, cnt) {
			w = rot(w, 'L');
		}
		bool ok = false;
		int R = 0;
		REP(i, s.size()) {
			if(w==t) {
				ok = true;
				break;
			}
			w = shiftL(w);
			R++;
		}
		if(ok && R<=cnt) {
			string ans(cnt, 'L');
			REP(i, R) ans[i] = 'R';
			assert(t==rotN(s, ans));
			return ans;
		}
		return "No solution";
	}
};

kojingharangの日記

2017-04-18

SRM 712 300 LR