🦁

AGC 040 | A - ><

1 min read

問題

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

考えたこと

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

入力例2で考える。

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

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

次にS_ii=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;
}

参考

Discussion

ログインするとコメントできます