[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;
}

https://atcoder.jp/contests/abc326/submissions/47033050