C++の練習を兼ねて, AtCoder Beginner Contest 250 の 問題G (Stonks) を解いてみた.
■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 計算できる点が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 250 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題G／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 |
// 解き直し. // https://atcoder.jp/contests/abc250/editorial/3929 // C++(GCC 9.2.1) #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--) LL p[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &p[i]); // 2. 株式売買. multiset<LL> mst{p[0]}; LL ans = 0; repx(i, 1, N){ // 2-1. 多重集合の最小値 m よりも大きい. auto s = mst.begin(); if(p[i] > *s){ // 加算. ans += p[i] - *s; // m を 一つ削除. mst.erase(mst.find(*s)); // p[i] を 二つ追加. mst.insert(p[i]); mst.insert(p[i]); // 次へ. continue; } // 2-2. 上記以外. // p[i] を 一つ追加. mst.insert(p[i]); } // 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
[入力例] 8 2 5 4 3 7 1 8 6 [出力例] 16 ※AtCoderテストケースより [入力例] 5 10000 1000 100 10 1 [出力例] 0 ※AtCoderテストケースより [入力例] 15 300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000 [出力例] 2787595378 ※AtCoderテストケースより [入力例] 3 1 2 3 [出力例] 2 [入力例] 10 36 20 111 25 33 30 27 81 9 90 [出力例] 234 [入力例] 20 5 12 9 7 8 1 6 12 8 1 8 8 1 4 2 11 7 1 11 6 [出力例] 55 [入力例] 100 6690 7423 11902 3154 588 26 6624 10736 936 11162 10812 3451 8077 6682 332 11911 7566 1823 10226 8771 1821 2688 7867 688 3434 647 5539 2352 3853 5491 2200 7983 3677 8121 8989 10191 7285 8617 6973 5990 8029 6076 7992 21 2682 10838 5080 5987 11349 11797 9335 8847 6442 4158 8592 4701 12286 2214 11222 7583 8060 6700 9963 5903 12232 785 7842 8471 6665 2495 5977 1284 4888 71 1132 7018 5674 3170 10052 397 54 2534 9787 1634 3389 7259 530 8630 206 9697 9521 9159 11933 3273 1846 11222 836 4815 5777 7365 [出力例] 300000 |
■参照サイト
AtCoder Beginner Contest 250