C++の練習を兼ねて, AtCoder Grand Contest 040 の 問題A (A – ><) を解いてみた.
■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 解説と同様の方針で解答出来たので, 時間かかったが, 及第点は取れたと思う.
本家のサイトAGC040解説をご覧下さい.
■C++版プログラム(問題A／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <bits/stdc++.h> using namespace std; using LL = long long; LL increase[543210], decrease[543210], ans; int main(){ // 1. 入力情報. char c[543210]; scanf("%s", c); int l = strlen(c); // 2. 数列の増加時, 減少時を分けて集計. // 2-1. 増加時(※ i が 大きくなる方向で確認). for(int i = 0; i < l; i++) if(c[i] == '<') increase[i + 1] = increase[i] + 1; // 2-2. 減少時(※ i が 小さくなる方向で確認). for(int i = l - 1; i >= 0; i--) if(c[i] == '>') decrease[i] = decrease[i + 1] + 1; // 3. 良い非負整数列の要素の総和の最小値を計算. for(int i = 0; i <= l; i++) ans += max(increase[i], decrease[i]); // 4. 出力. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
[入力例] <>> [出力例] 3 ※AtCoderテストケースより [入力例] <>>><<><<<<<>>>< [出力例] 28 ※AtCoderテストケースより [入力例] >>>>>>>>><<<<<<<<>>>>>>><<<<<<>>>>><<<<>>><<> [出力例] 149 [入力例] <<<><<<<><<<<<>>>>>>>>><<>>>>>><<<<<>>> [出力例] 111 [入力例] <<<>>><<<><<<<<<<>><<>>>>>>><<><<><<<<<<<>>>>>><><<<<<><<<<<<<>><<>><<<<<<>>><<>>< [入力例] 200 |
■参照サイト
AtCoder Grand Contest 040