C++の練習を兼ねて, AtCoder Beginner Contest 027 の 問題D (D – ロボット) を解いてみた.
■感想.
1. 方針が全く見えなかったので, 解説を確認して, 実装した.
2. 個人的には, 非常に摩訶不思議な解法に見えたとともに, アルゴリズムの奥深さに驚いた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 027解説をご覧下さい.
■C++版プログラム(問題D/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 |
// 解き直し. // https://www.slideshare.net/chokudai/abc027 #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--) #define pb push_back #define all(x) x.begin(), x.end() LL p[101010]; // i番目より右側にある '+' の 個数. LL m[101010]; // i番目より右側にある '-' の 個数. int main(){ // 1. 入力情報. char c[101010]; scanf("%s", c); // 2. i番目よりも右側にある '+', '-' を 集計(解説通り). int l = strlen(c); rep(i, l){ p[i + 1] = p[i]; m[i + 1] = m[i]; if(c[i] == '+') p[i + 1]++; if(c[i] == '-') m[i + 1]++; } // rep(i, l + 1) printf("p[%d]=%lld m[%d]=%lld\n", i, p[i], i, m[i]); // 3. 幸福度の変化量(解説通り). vector<LL> dx; // (i番目より右側の '+' の個数) - (i番目より右側の '-' の個数) int mCount = 0; rep(i, l) if(c[i] == 'M') dx.pb({p[i + 1] - m[i + 1]}), mCount++; // 4. sort(解説通り). sort(all(dx)); // 5. 後半 - 前半 を 計算(解説通り). LL ans = 0; rep(i, mCount / 2) ans -= dx[i]; // 前半. repx(i, mCount / 2, mCount) ans += dx[i]; // 後半. // 6. 出力. 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 38 39 40 41 42 43 44 45 46 |
[入力例] M+MM-M [出力例] 2 ※AtCoderテストケースより [入力例] MMM+M [出力例] 1 ※AtCoderテストケースより [入力例] MMM+--MMM [出力例] 3 ※AtCoderテストケースより [入力例] + [出力例] 0 ※AtCoderテストケースより [入力例] M--M-M+M+ [出力例] 3 ※AtCoder解説例より [入力例] M--M-+M++-MM+++-M---M+--M-+---M++---M+--MM---M-M-MMM+M-M---+--M-M----M---M-MMM+-M+++-M-+MMMM-+--M+M++-M--+MM-+-++-+-M---M-M+++M-+--++-M------+M-MM++M-MM-++-M-M+-MM-+-+--M-M-+M---+-++-M++--+---+++MMMM- [出力例] 555 [入力例] M+MMMM++MM-++-+MMM+-M--M+M-+-MMM+-MM---++M-+MMMM+--+MMMM+-M+M-M-+-+M+MMM---+M+MMMM+++MMM-++M-M-M+-MM+M-MM+MMM-+M+M-MMMMMMMMMMM+M+-+MM+M++++M+M+M++MM-++M-MM-M+MMM+-MMM-MMMMMMMMM+MMM-MMM--MM-M+-MMM++M-MMM-MMMMM-+M-MM++MM-M+--+MM+-MM--+-+++M-MMMMMMMMM+M-M-+MM+MM--MMMMMMMM---MM+-++-MM+MMMMMM+MMMM-+MM++--M+++MM-M---MMMMMMMM-+-M-MMM++M+-+-MM+M-M-M+MMM+M+M-+-MM-M-M++M-+---+-MMMMMM++-MM-M-+MMM-+M-M-+-M++M-+MMMM--MM-MM-+M+MM-++MM++--+MMM----++MMM+++M-MMMM-MMM--M-MM-M+++MM-M+-MM-MMMMMMMM+MM+MM+-MMMM+M+M-+MMMM-MMMM+MMMM-M+--M++M+MMM-++-MM+M-+M-+M-++M+MM++-M-+-M--M+MM-MMM-++-M-M+M--MM++--MM-MM-MM++-+M+-+MM-M-+M+MM++M-MMMMM-MMMM+M+-MM+-+M-M+-M-M++M++-+MMMMM-MMM+--MMM-MM-+M+++M-M-MM+-M-MM-MM++M+M-+-MMMMMMMMMM+M+M++-MM-MMMM-+MMMM+MMM+MM--+M+M--++MMM+MM+MM+MM--M+-+-MM+M-M-+M--MMM++M-MMM+-M++MM-MMM+-++-M--M+M++MM++-M+M+MM--+-+MMMMMMM+-MMMM+-M++-++MM+MM+-M----M-MMMM--M+-MM--+-M---MMMM+MMMM+M+M--M++M++M---+-M-MMMMMM+--M+MMMMM+-M+M++M+-MM++--MMMM+M+MMMMM-MMMMM-++MM+M+MMM-+-+-+M-MMM---++M-M+M--MMM+M-++-+M+ [出力例] 2015 |
■参照サイト
AtCoder Beginner Contest 027