提出 #577452

---

ソースコード 拡げる

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

#define F first
#define S second
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define rep REP
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;

int solve(const string &s){
  vector<int> L(s.size() + 1);
  vector<int> R(s.size() + 1);
  L[0] = 0;
  R[0] = 0;
  REP(i, s.size()){
    if (s[i] == '<'){
      L[i + 1] = L[i] + 1;
      R[i + 1] = R[i];
    } else {
      L[i + 1] = L[i];
      R[i + 1] = R[i] + 1;
    }
  }

  int res = 0;
  REP(i, s.size()) if (s[i] == '>'){
    int l = R[i + 1];           // '>'
    int r = L[s.size()] - L[i + 1]; // '<'
    int d = min(l, r);
    if (r >= l){
      int lb = i + 1;
      int ub = s.size();
      
      // cout << s << " " << i << " " << d << " " << L[6] - L[i + 1] <<endl;
      while (ub - lb > 1){
        int mb = (lb + ub) >> 1;
        if (L[mb] - L[i + 1] >= d){
          ub = mb;
        } else {
          lb = mb;
        }
      }
      res = max(res, ub);
    } else {
      int lb = 0;
      int ub = i + 1;
      int d = l - r;
      while (ub - lb > 1){
        int mb = (ub + lb) >> 1;
        if (R[mb] >= d) ub = mb;
        else lb = mb;
      }
      res = max(res, (int)s.size() - lb);
    }
  }
  return res;
}

int naive(string s){
  int ans = 0;
  rep(i, SZ(s)){
    vector<bool> use(SZ(s));
    int cur = i;
    int dir = s[i] == '<' ? -1 : 1;
    int cnt = 0;
    while(cur >= 0 && cur < SZ(s)){
      if(use[cur]){
        cur += dir;
        continue;
      }
      use[cur] = true;
      ++cnt;
      dir = s[cur] == '<' ? -1 : 1;
    }
    ans = max(ans, cnt);
  }
  return ans;
}

int main(int argc, char **argv){
  int n;
  string s;
  while (cin >> n >> s){
    int res = solve(s);
    // int na  = naive(s);
    reverse(ALL(s));
    for (auto &c : s) {
      if (c == '>') c = '<';
      else c = '>';
    }
    // cout << s << endl;
    res = max(res, solve(s));
    // if(naive(s) != res || na != naive(s)){
    //   cout << na << endl;
    //   cout << "naive " << naive(s) << endl;
    //   cout << res << endl;
    //   cout << s << endl;
    //   exit(1);
    // }
    cout << res << endl;
  }
}

提出情報

ジャッジ結果