SnackDown 2016 - Robot Walk

問題

ロボットに2×N+1回の命令が与えられます。
奇数回目:数字が与えられるので、ロボットは指定された数字だけ、今向いている方向に移動します。
偶数回目:LまたはRの文字が与えられるので、ロボットは指定された方向に90度回転します。
これを、原点からスタートしたときに、命令をすべて終えた後再び原点にいるように、命令の中身を変更したいです。LとRを逆にするコストは0とし、数字を1追加、および減らすことをコスト1としたとき、最小のコストを求めなさい、というものです(もし無理であればNOを出力します)。
これをT回繰り返します。

解法

まず、Nが2以下のときはNOとなります。一周することができないので、戻ってくることができません。
それ以外のときを考えます。
偶数回目の移動と奇数回目の移動で、それぞれ横と縦の移動に分離しています。なので、それぞれで最小のものを求めて、最後に合算します。ということでとりあえず縦について考えます。
数直線上で考えます。正に進む場合と負に進む場合は、コスト0で変更できるので、全ての場合を試したうちの、一番原点とのズレが近いものを選び、そのズレだけ修正すれば、コストが最小になります。
ある地点Xにいるときに、コスト0で移動できる場所は、その次の命令の移動するマスの数をDとすると、X＋DまたはX-Dのどちらかになります。
次に移動するときのマスの数をEとすると、先ほどのX+DおよびX-Dから、さらに+E、もしくは-Eだけ移動した場所の4通りになります。
ということで、これを高速に計算する手段を探すと、bitsetというものがあったので使います(存在は知っていましたが、実は初めて使いました)
最初は原点に1というビットを立てておき、他は0とします。
そして、次に移動するマスの数をDとしたとき、現在のbitsetを左にDシフトしたものと右にDシフトしたもののORをとれば、移動後にたどり着ける場所にのみビットが立っています。
あとは、処理が完了したら原点に近いものから順番に、1が立っている場所を探して、その差を最小コストとすればよいです。
これを、縦と横についてすべて行い、合算すれば答えとなります。
bitsetは結構直感的というか、ほかのデータ構造や演算子とそのままな部分が多かったので個人的にはかなり使いやすいと思いました。

以下が提出コードとなります。

#include <bits/stdc++.h>
using namespace std;

int t, n;

int solve();

int main() {
  cin >> t;
  while(t) {
    cin >> n;
    if(n <= 2) {
      solve();
      cout << "NO" << endl;
    }
    else
      cout << solve() << endl;
    --t;
  }
  return 0;
}

int solve() {
  char x;
  int i, a, k, now, ans = 0;
  bitset<(500 * 505)> bt[2];
  bt[0][500] = 1;
  bt[1][500] = 1;
  for(i = 0; i <= n; ++i) {
    cin >> a;
    if(i != n) cin >> x;
    now = i % 2;
    bt[now] = (bt[now] << a) | (bt[now] >> a);
  }
  for(k = 0; k < 2; ++k) {
    for(i = 0; i <= 500; ++i)
      if(bt[k][i + 500] || bt[k][-i + 500]) {
        ans += i;
        break;
      }
  }
  return ans;
}