C++の練習を兼ねて, AtCoder Grand Contest 005 の 問題A (STring) ～ 問題B (Minimum Sum) を解いてみた.
■感想.
1. 問題B は 方針が見えなかったので, 解説を参照して実装したところ, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAGC 005 解説をご覧下さい.
■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 28 29 30 31 32 |
#include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int main(){ // 1. 入力情報. char X[202020]; scanf("%s", X); int l = strlen(X); // 2. 'T' が 来たら, stack から 'S' を 取り除く. stack<char> st; rep(i, l){ char c = X[i]; if(st.empty()){ st.push(c); continue; } char t = st.top(); if(c == 'T' && t == 'S') st.pop(); else st.push(c); } // 3. 出力. printf("%d\n", st.size()); 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 32 |
[入力例] TSTTSS [出力例] 4 ※AtCoderテストケースより [入力例] SSTTST [出力例] 0 ※AtCoderテストケースより [入力例] TSSTTTSS [出力例] 4 ※AtCoderテストケースより [入力例] TSSSTSTSTSTTSSSTTTTS [出力例] 2 [入力例] TTTTSSTSTSSTTSTTSTSTSSSTSSTSSSTSTSTSTSSTTSTSTSTTTTSSSSSTTTST [出力例] 8 |
■C++版プログラム(問題B／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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
// 解き直し. // http://agc005.contest.atcoder.jp/data/agc/005/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int io[202020], oi[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ scanf("%d", &io[i]); oi[io[i]] = i + 1; } // 2. l, r を 計算(※解説参照). LL ans = 0; set<int> s; s.insert(0); s.insert(N + 1); // ※ 解説上, N, N - 1, N - 2, ... の 順で, l, r を 求めていくと説明されているが, // 上手く行かなかったので, 1, 2, ... の 順で, l, r を 求めていくように実装している. repx(i, 1, N + 1){ // i の 出現位置. int at = oi[i]; // 検索. set<int>::iterator it; it = s.lower_bound(at); int r = *it; int l = *(--it); // printf("at=%d l=%d r=%d\n", at, l, r); // 加算. ans += (LL)io[at - 1] * (LL)(at - l) * (LL)(r - at); // 登録. s.insert(at); } // 3. 出力. 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 32 33 34 35 36 37 |
[入力例] 3 2 1 3 [出力例] 9 ※AtCoderテストケースより [入力例] 4 1 3 2 4 [出力例] 19 ※AtCoderテストケースより [入力例] 8 5 4 8 1 2 6 7 3 [出力例] 85 ※AtCoderテストケースより [入力例] 32 15 28 29 12 25 13 2 14 1 26 30 3 20 21 22 4 5 6 7 18 31 19 8 9 32 23 10 24 11 16 17 27 [出力例] 2521 [入力例] 50 9 10 37 27 5 17 49 35 3 8 46 45 20 24 28 39 16 30 29 22 14 7 1 12 31 2 41 32 26 36 38 47 34 33 40 18 48 25 19 44 50 13 6 4 42 15 43 11 23 21 [出力例] 7171 |
■参照サイト
AtCoder Grand Contest 005