C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題C (Rotate and Play Game) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 個人的には, 解説のロジックで, cyclic-shift を 計算できることが, 非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 138 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
// 解き直し. // https://atcoder.jp/contests/arc138/editorial/3742 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<int, int>; using vp = vector<P>; using vi = vector<int>; #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 a first #define b second #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp a(N); rep(i, N){ int x; scanf("%d", &x); a[i].a = x; a[i].b = i; } // 2. sort. sort(all(a)); // 3. 数列 B. // -> スコアも計算. int n = N / 2; LL s = 0; vi b(N); rep(i, N){ // (N / 2)番目以内. if(i < n) b[a[i].b] = 1; // (N / 2)番目以降. if(i >= n){ b[a[i].b] = -1; s += (LL)a[i].a; } } // 4. 数列 C. // -> 最小値となるインデックスは？ int k = 0, c = 0, minC = 202020; rep(i, N){ // 最小値更新. if(c + b[i] < minC){ k = (i + 1) % N; minC = c + b[i]; } // 今回分更新. c += b[i]; } // 5. 出力. printf("%d %lld\n", k, s); 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 52 53 54 55 56 57 58 59 60 61 |
[入力例] 4 3 4 1 2 [出力例] 1 7 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 2 7 [入力例] 2 1 1 [出力例] 0 1 ※AtCoderのテストケースより [入力例] 10 716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694 [出力例] 7 3996409938 ※AtCoderのテストケースより [入力例] 6 1 2 3 4 5 6 [出力例] 0 15 [入力例] 12 1013 538 447 674 357 329 568 353 696 179 645 725 [出力例] 1 4321 [入力例] 20 753 884 884 330 396 725 80 764 1234 238 692 908 853 703 243 434 990 690 86 893 [出力例] 3 8888 [入力例] 50 14171 512 35734 81510 94315 101494 96412 47947 31037 35709 1912 62854 84105 88611 77352 66746 71920 4992 19770 72343 100939 6871 5426 7667 84424 121076 91207 97000 11428 84719 7528 11896 18788 85486 2310 95702 90159 85633 73139 34002 121751 9944 32220 39321 54771 80595 112730 26602 12880 25621 [出力例] 39 2222222 [入力例] 100 8105207 10037090 14275267 4568301 18687560 2454909 7415311 16233053 21981661 19339463 12971006 14994431 21267523 20377604 3500626 16887598 13295099 39219 19554687 20238813 19575053 12852952 11243842 6103085 5668456 13795830 6646141 1073694 630192 11113919 2432917 4263296 10570151 12088838 6970113 7371129 18602246 16466811 1815862 5243355 2988231 7869573 16094918 22824922 16286695 1965058 8662710 21405609 11243782 8013341 13680674 19343455 11621265 9165034 17780853 15688446 5221807 15029016 21234126 7720848 1543581 8785894 4855221 22097803 21326531 21644858 18338488 8907523 7847179 23223607 67424 18222629 6039054 23456724 13817234 3428852 12902509 1544292 21322070 13563115 8289581 9986151 8919649 18875876 17771885 9628056 6610780 17061539 15894359 17502701 13838430 6991829 11837503 11865139 22013613 2272876 18933803 135733 22361766 3433853 [出力例] 22 888888888 |
■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)