問題概要 (意訳)

[[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]

みたいな感じの文字列が与えられる。以下で定義されるような演算を実施していって、最後に残る数値を答えよ。

最初に、[a] となっているやつは b = (a+1)/2 として b で置き換えておく
それ以降は [a1, a2, ..., ak] は、a1, a2, ..., ak を小さい順に (k+1)/2 個とった総和を b として、b で置き換えるのを繰り返す

例

上の例では以下のような感じになる:

[[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]
↓
[[49, 30, 32, 43, 26][770, 3998, 234][26, 29, 40, 50, 2, 46, 30]]
↓
[88, 1004, 87]
↓
175

考えたこと

カッコ列の整合性を check する処理をちょっと変形すればできる感じ。広義のカッコ列問題だと言える。

vals[d] := 深さ d のところにある値たち ([13, 28, 11] 的なやつ) を一時的に格納しておく

という配列を用意しておいて、右カッコが来るたびにこれを全部 pop して、しかるべき値を計算してより浅いところに push していくことを繰り返す。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string S;
vector<long long> vals[100]; // 深さ d のところに一時格納する値たち

long long solve() {
  for (int i = 0; i < 100; ++i) vals[i].clear();
  int depth = 0;
  int val = 0;
  for (int i = 0; i < S.size(); ++i) {
    if (S[i] == '[') ++depth;
    else if (S[i] == ']') {
      if (val) vals[depth].push_back((val+1)/2);
      val = 0;
      sort(vals[depth].begin(), vals[depth].end());
      long long sum = 0;
      for (int j = 0; j*2 < vals[depth].size(); ++j) sum += vals[depth][j];
      vals[depth-1].push_back(sum);
      vals[depth].clear();
      --depth;
    }
    else {
      val *= 10;
      int c = (int)(S[i] - '0');
      val += c;
    }
  }
  return vals[0][0];
}

int main() {
  int N; cin >> N;
  for (int i = 0; i < N; ++i) {
    cin >> S;
    cout << solve() << endl;
  }
}