解法
移動自体は,\(i \in N\) 回目の操作について \(i\) mod 2 で座標軸ごとに独立に分けることができる. \(M := N/2\) なら,\(O(2^{M}\) は間に合う.
実装
簡単のため,\(N \equiv 0\) mod 4 となる様に \(A\) の末尾に \(0\) を追加する.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
vll solve(vll x,ll val ){
ll n2 = x.size();
ll n = n2/2;
vll xl(x.begin(), x.begin()+n);
vll xr(x.begin()+n, x.end());
x.clear();
vll res;
unordered_map<ll,vll> mp;
rep(ti,2){
rep(msk,1LL<<n){
vll s;
ll tot = 0;
rep(i,n){
if(msk>>i&1) s.push_back(+1), tot += xl[i];
else s.push_back(-1), tot -= xl[i];
}
if(ti==0) mp[tot] = s;
else {
auto it = mp.find(val - tot);
if(it != mp.end()){
return (*c);
}
}
}
swap(xl, xr);
}
return vll();
}
int main() {
ll n, x, y;
cin >> n >> x >> y;
vll a(n); rep(i,n) { cin >> a[i]; }
ll added = 0;
while(n%4) added++, n++, a.push_back(0);
vll vx,vy;
rep(i,n) {
if(i%2) vx.push_back(a[i]);
else vy.push_back(a[i]);
}
vll sx = solve(vx, x);
vll sy = solve(vy, y);
if(sx.size()*sy.size() == 0){
cout << "No" << endl;
return 0;
}
ll pre = 1;
string ans;
rep(i,n){
ll q = pre;
ll cu;
if(i%2){
cu = sx[i/2];
q *= cu;
pre = cu;
q *= -1;
}
else {
cu = sy[i/2];
q *= cu;
pre = cu;
}
if(q == 1) ans.push_back('L');
else ans.push_back('R');
}
rep(i,added) ans.pop_back();
cout << "Yes" << endl;
cout << ans << endl;
return 0;
}
*1:*it).second);
(*c).insert((*c).end(), all(s