[AtCoder] AGC 040 A – ><
問題
方針
条件を満たす整数列を作ります。まず初めに、\( a_i = 0 \ ( 1 \leq i \leq N) \) とします。次に、文字列の先頭から末尾に向かって、\( S_i = \) '<' ならば、\( a_{i + 1} = a_i + 1 \) と更新します。 次に、末尾から先頭に向かって、\( S_i = \) '>’ かつ \( a_{i+1} \geq a_i \) ならば、\( a_{i} = a_{i+1} + 1 \) と更新します。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { string S; cin >> S; int n = S.length(); ll a[n + 1]{}; ll ans = 0; int k = 0; for (int i = 0; i < n; i++) { if (S[i] == '<') { a[i + 1] = a[i] + 1; } } for (int i = n - 1; i >= 0; i--) { if (S[i] == '>') { if (a[i + 1] >= a[i]) { a[i] = a[i + 1] + 1; } } } for (ll i : a) { ans += i; } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません