[ABC326] F - Robot Rotation
[Q] https://atcoder.jp/contests/abc326/tasks/abc326_f
考察
1. N=80だけど、y軸移動に関するのは偶数ターン(0-indexed)の動きだけ。40ターン/40ターンに分けられる。y軸移動とx軸移動を独立させて考える。
2. 半分全列挙で、2^20 * 2^20は間に合う。
3. とりあえず目的地にたどり着けるかどうか判定する。
4. たどり着けると分かったときに、経路を復元したい。
5. 半分進んだ時点で、値がいくつになっていればよいかがわかっている。それを目指してもう一度半分全列挙。今度は経路を保存する。
6. +-の判定がわかるので、自分が向いている方向にあわせてLRをあてはめればいい。
実装
int main() {
cincout();
ll N, X, Y;
cin >> N >> X >> Y;
vector<ll> A, B; // AがY軸, BがX軸
rep(i, N) {
ll a;
cin >> a;
if (i % 2 == 0)
A.push_back(a);
else
B.push_back(a);
}
// 半分全列挙
auto get_st = [&](vector<ll> &A, ll s, ll t) {
set<ll> st;
st.insert(0);
for (ll i = s; i < t; ++i) {
set<ll> tmp;
rep(j, 2) {
for (auto s : st) {
if (j == 0)
tmp.insert(s + A[i]);
else
tmp.insert(s - A[i]);
}
}
swap(st, tmp);
}
return st;
};
vector<set<ll>> stA(2), stB(2);
stA[0] = get_st(A, 0, A.size() / 2);
stA[1] = get_st(A, A.size() / 2, A.size());
stB[0] = get_st(B, 0, B.size() / 2);
stB[1] = get_st(B, B.size() / 2, B.size());
vector<ll> valA(2), valB(2);
// 回答を満たす数字の取り方があるか確認
auto test = [&](vector<set<ll>> &stA, ll Y, vector<ll> &val) -> bool {
for (auto a0 : stA[0]) {
auto it = stA[1].lower_bound(Y - a0);
if (*it == Y - a0) {
val[0] = a0;
val[1] = *it;
return true;
}
}
return false;
};
if (!test(stA, Y, valA) || !test(stB, X, valB)) {
cout << "No" << endl;
return 0;
}
// 回答を満たす数字の取り方があるので、まず+-を復元
auto get_string = [&](vector<ll> &A, ll s, ll t, ll val) ->string{
rep(j, (1LL << (t - s))) {
ll sum = 0;
string res;
for (ll i = s; i < t; ++i) {
if (is_pop(j, i - s)){
sum += A[i];
res += '+';
}
else{
sum -= A[i];
res += '-';
}
}
if (sum == val){
return res;
}
}
return "";
};
string a, b, ans;
a = get_string(A, 0, A.size() / 2, valA[0]);
a += get_string(A, A.size() / 2, A.size(), valA[1]);
b = get_string(B, 0, B.size() / 2, valB[0]);
b += get_string(B, B.size() / 2, B.size(), valB[1]);
// 現在向いている向き。右上左下で0123
ll dir = 0;
rep(i, N){
if (i % 2 == 0){ // Y軸
if (a[i / 2] == '+'){
if (dir == 0){
ans += 'L';
}
else{
ans += 'R';
}
dir = 1; // +なら上を向く
}
else{
if (dir == 0){
ans += 'R';
}
else{
ans += 'L';
}
dir = 3; // -なら下を向く
}
}
else{
if (b[i / 2] == '+'){
if (dir == 1){
ans += 'R';
}
else{
ans += 'L';
}
dir = 0; // +なら右を向く
}
else{
if (dir == 1){
ans += 'L';
}
else{
ans += 'R';
}
dir = 2; // -なら左を向く
}
}
}
cout << "Yes" << endl << ans << endl;
}