AGC 040 | A - ><

問題

https://atcoder.jp/contests/agc040/tasks/agc040_a

考えたこと

(ほとんど解説動画と同じなのでそっちを見たほうがよい)

入力例2で考える。

$a_i$は非負整数なので$a_1,a_2,\cdots,a_N$を最小値である0で初期化する。

$S_i$を$i=0$から$i={N-2}$まで走査する。$S_i$において$<$があれば必ず$a_{i+1}$が$a_i$より大きいので最低限の増加である1をたし、$a_{i+1}=a_i+1$とする。

次に$S_i$を$i=N-2$から$i=0$まで走査する。$S_i$において$>$があれば必ず$a_{i}$は$a_{i+1}$より大きいので既存の$a_{I}$と比べて、$a_i = max(a_i,a_{i+1}+1)$とする。

それで総和が一番小さい数列ができた。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  string s;
  cin >> s;
  const int n = s.size() + 1;
  vector<ll> a(n);
  ll m = 0;  // minimum
        
  // check <
  for (int i = 0; i < n - 1; i++) {
    char c = s[i];
    if (c == '<') {
      a[i + 1] = a[i] + 1;
    }
  }
  // check >
  for (int i = n - 2; i >= 0; i--) {
    char c = s[i];
    if (c == '>') {
      a[i] = max(a[i], a[i + 1] + 1);
    }
  }
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += a[i];
  }
  cout << ans << endl;
}

参考

• https://atcoder.jp/contests/agc040/tasks/agc040_a/editorial