C++の練習を兼ねて, AtCoder Beginner Contest 330 の 問題C (Minimize Abs 2) ～ 問題E (Mex and Update) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題E で, mex の 性質を復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 330 解説 の 各リンク を ご覧下さい.
■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 |
// C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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() const int MAX = 1414214; int main(){ // 1. 入力情報. LL D; scanf("%lld", &D); // 2. 平方数. vl sNum; rep(i, MAX) sNum.pb((LL)i * (LL)i); // 3. 最小値は？ LL ans = 202020202020202020; rep(i, MAX){ LL gap = D - sNum[i]; if(gap < 0) break; int at = lower_bound(all(sNum), gap) - sNum.begin(); if(at) ans = min(ans, abs(sNum[i] + sNum[at - 1] - D)); if(at < MAX) ans = min(ans, abs(sNum[i] + sNum[at] - D)); } // 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
[入力例] 21 [出力例] 1 ※AtCoderテストケースより [入力例] 998244353 [出力例] 0 ※AtCoderテストケースより [入力例] 264428617 [出力例] 32 ※AtCoderテストケースより [入力例] 12345 [出力例] 1 [入力例] 4092529 [出力例] 0 [入力例] 3703629658 [出力例] 7 [入力例] 202311252100 [出力例] 2 [入力例] 1987654321012 [出力例] 0 |
■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 |
// C++20(GCC 12.2) #include <bits/stdc++.h> using namespace std; using LL = long long; using vs = vector<string>; #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 rCum[2020][2020], cCum[2020][2020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vs v(N); rep(i, N){ char c[N + 1]; scanf("%s", c); string s(c); v[i] = s; } // 2. 累積和. rep(i, N) rep(j, N) rCum[i][j + 1] = rCum[i][j] + (v[i][j] == 'o'); rep(j, N) rep(i, N) cCum[i + 1][j] = cCum[i][j] + (v[i][j] == 'o'); // 3. 集計. LL ans = 0; rep(i, N) rep(j, N) if(v[i][j] == 'o') ans += (rCum[i][N] - 1) * (cCum[N][j] - 1); // 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 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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
[入力例] 3 ooo oxx xxo [出力例] 4 ※AtCoderテストケースより [入力例] 4 oxxx xoxx xxox xxxo [出力例] 0 ※AtCoderテストケースより [入力例] 15 xooxxooooxxxoox oxxoxoxxxoxoxxo oxxoxoxxxoxoxxx ooooxooooxxoxxx oxxoxoxxxoxoxxx oxxoxoxxxoxoxxo oxxoxooooxxxoox xxxxxxxxxxxxxxx xooxxxooxxxooox oxxoxoxxoxoxxxo xxxoxxxxoxoxxoo xooxxxooxxoxoxo xxxoxxxxoxooxxo oxxoxoxxoxoxxxo xooxxxooxxxooox [出力例] 2960 ※AtCoderテストケースより [入力例] 5 oxoxo xoxox oxoxo xoxox oxoxo [出力例] 40 [入力例] 20 xoxxoxxoxoxooxoooxox oooxoooxxoxooxooxoxx oooooxoxoooxooxooxxx xxoxxxxooxxooxxxoooo xoooxooxxxxooooxoxoo xoxxoxxooxooxxxxxoox oxooooooooxxxxooxoxx oxooooxxoxoxoxoxxxxo xxoooxxoxxxoxoxooooo xooxooxoxxxxoooxxxxo ooxoxoooxxxooxoxoxoo xooxoxoxoxooxoooxooo xxooxoooxooooooooxxx xxooxooxooooxoxxxxox oxxoxxxxoxxoxoxxxooo oxoxoxxxxoooxxoxoxoo ooxooooxooxoooxxxxoo ooxooxxoxoxxxxxxxoxo oxooooxxoxxxoxxoxxox xooxxoxooxoxxoxoxxxx [出力例] 20113 [入力例] 50 xooxoxoooxxxoooooxxxxooxoxoooxxxoooooxxxooxooxooox xxxooxxooxoooxoxooooxooxoxoooxxxoooooxxxoxxoxxoxox ooxooxxxxoxoxoxooxxxxooxoxoooxxxoooooxxxoooxxxooxo ooxxoxoxxoxoxoxoxoxxxooxoxoooxoxoooooxxxooxooxooox xxxxxooxoooxooxoxoooxooxoxoooxxxoooooxxxoooxxxooxo xoxxxxoxooxoooxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox xoooxoxoooooooxoooxxxooxoxoooxxxoooooxxxooxxxxooxo xxoxoxooxooxoooxxoxxxooxoxoooxxxoooooxxxooxooxooox xxooxxxoxoxxoxxxoxxoxooxoxoooxoxoooooxxxooxxoxooxo xxxoxxoxooxxoxxoxxooxooxoxoooxxxoooooxxxoooxxxooxo oxoxooooxxxxoxoxxxxoxooxoxoooxxxoooooxxxoxxooxoxox xxxxoxoxxxooxoxxooxxxooxoxoooxxxoooooxxxooxooxooox xoxoooooxxoxoooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo xoxooxooooxoooxoooxoxooxoxoooxxxoooooxxxoooxxxooxo oxoxxoxxoxxoxoxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox oooxoxoxoxxxxooxoxxoxooxoxoooxxxoxoooxxxooxxxxooxo xooxxooxxxoxxxoxxoooxooxoxoooxxxoooooxxxooxooxooox oxoxoxxoooooooxoxxxxxooxoxoooxxxoxoooxxxoxxoxxoxox xxxxoxxoxxxooxoxoxoxxooxoxoooxxxoooxoxoxoooxxxooxo xooxooxxooxoxooxxoxoxooxoxoooxxxoooooxxxooxooxooox oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxoxooxxxxooxo oooxoxoxoxxoxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo xooxoxoooxoxoooooxxxxooxoxoooxxxoooooxxoooxooxooox xxxooxxooxoooxoxooooxooxoxoooxxxoooooxxxoxxoxxoxox ooxooxxxxoxoxoxooxxxxooxoxoooxxxoooooxxxoooxxxooxo ooxxoxoxxoxoxoxoxoxoxooxoxoooxxxoooooxoxooxooxooox xxxxxooxoooxooxoxoooxooxoxoooxxxoooooxxxoooxxxooxo xoxoxxoxooxoooxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox xoooxoxoooooooxoooxxxooxoxoooxxxoooooxoxooxxxxooxo xxoxoxooxooxoooxxoxxxooxoxoooxxxoooooxxxooxooxooox xxooxxxoxoxxoxxxoxxoxooxoxoooxxxoooooxxoooxxxoooxo xxxoxxoxooxxoxxoxxooxooxoxoooxxxoooooxxxoooxxxooxo oxoxooooxxxxoxoxxxxoxooxoxoooxoxoooooxxxoxxoxxoxox xxxxoxoxxxooxoxxooxxxooxoxoooxxxoooooxxxooxooxoooo xoxoooooxxoxoooxoxxoxooxoxoooxxooooooxxxooxxxxooxo xoxooxooooxoooxoooxoxooxoxoooxxxoooooxxxoooxoxooxo oxoxxoxxoxxoxoxooxxoxooxoxoooxxxoooooxxxoxxoxxoxox oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo xooxxooxxxoxxxoxxoooxooxoxoooxxxoooooxxxooxooxooox oxoxoxxoooooooxoxxxxxooxoxoooxxxoooooxxxoxxoxxoxox xxxxoxxoxxxooxoxoxoxxooxoxoooxxxoooooxxxoooxxxooxo xooxooxxooxoxooxxoxoxooxoxoooxxxoooooxxxooxooxooox oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo oooxoxoxoxxxxooxoxxoxooxoxoooxxxoooooxxxooxxxxooxo [出力例] 1303146 |
■C++版プログラム(問題E／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 |
// 解き直し. // https://atcoder.jp/contests/abc330/editorial/7752 // C++20(GCC 12.2) #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 a[202020], bk[202020]; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); rep(i, N) scanf("%d", &a[i]); // 2. 初期化. set<int> st; rep(i, N) if(a[i] <= N) ++bk[a[i]]; rep(k, N + 1) if(bk[k] == 0) st.insert(k); // 3. クエリ回答(解説通り). rep(j, Q){ // 3-1. クエリ入力情報. int i, x; scanf("%d %d", &i, &x); --i; // 3-2. 出現回数更新(更新前a[i]). if(a[i] < N + 1){ --bk[a[i]]; if(bk[a[i]] == 0) st.insert(a[i]); } // 3-3. a[i]更新. a[i] = x; // 3-4. 出現回数更新(更新後a[i]). if(a[i] < N + 1){ if(bk[a[i]] == 0) st.erase(a[i]); ++bk[a[i]]; } // 3-5. 出力. printf("%d\n", *st.begin()); } 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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
[入力例] 8 5 2 0 2 2 1 1 2 5 4 3 4 4 6 3 8 1000000000 2 1 [出力例] 4 3 6 5 0 ※AtCoderテストケースより [入力例] 3 5 7 7 7 3 3 2 0 1 1 2 4 2 0 [出力例] 0 1 2 0 2 [入力例] 5 5 0 1 3 5 7 4 6 4 2 5 4 3 0 2 2 [出力例] 2 4 5 3 1 [入力例] 5 5 1000000000 1000000000 1000000000 1000000000 1000000000 4 6 4 2 5 4 3 0 2 2 [出力例] 0 0 0 1 1 [入力例] 10 7 1 0 3 5 4 3 7 8 12 15 1 0 2 1 1 1 3 0 9 2 8 6 6 9 [出力例] 1 2 0 2 6 8 3 [入力例] 20 25 1 9 2 0 4 16 2 4 8 9 0 3 2 0 3 4 8 7 10 10 9 25 8 5 20 6 2 0 16 1 7 2 17 2 4 0 10 8 8 23 8 9 3 13 16 5 2 8 1 3 20 9 13 14 6 1 20 7 18 1 4 12 19 6 19 2 1 6 13 8 [出力例] 5 6 11 11 11 11 8 8 9 5 5 5 11 11 1 1 1 6 6 6 6 10 6 10 10 |
■参照サイト
トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)