C++の練習を兼ねて, AtCoder Beginner Contest 166 の 問題E (E – This Message Will Self-Destruct in 5s) を解いてみた.
■感想.
1. 式変形を使って, 数え上げの回数を減らすことが出来たので, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 166 解説をご覧下さい.
■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 |
#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 a[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. a[j] - j を 保存. // -> i < j と 仮定して, j - i = a[j] + a[i] とすると, // -(a[i] - i) - 2 * i = (a[j] - j) と 変形できる. map<LL, LL> m; rep(j, N){ LL b = a[j] - j; m[b]++; } // 3. 条件を満たすペアを検索. LL ans = 0; rep(i, N){ LL b = -(a[i] - i) - 2 * i; if(m.count(b)) ans += m[b]; } // 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 |
[入力例] 6 2 3 3 1 3 1 [出力例] 3 ※AtCoderテストケースより [入力例] 6 5 2 4 2 8 8 [出力例] 0 ※AtCoderテストケースより [入力例] 32 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 [出力例] 22 ※AtCoderテストケースより [入力例] 100 23 48 2 36 20 33 2 42 19 34 26 14 12 43 29 2 5 49 3 8 2 29 31 22 31 7 42 42 34 18 6 10 35 19 33 41 27 13 34 22 4 34 13 7 39 34 3 29 24 39 9 36 19 5 26 26 10 6 3 2 38 45 20 50 14 43 27 43 44 11 1 13 2 38 31 11 2 23 42 39 16 33 39 32 24 47 32 10 27 12 4 32 16 2 32 12 21 30 14 29 [出力例] 54 [入力例] 300 150 13 144 128 198 138 130 129 221 203 42 20 127 62 177 228 194 26 211 216 27 34 196 170 132 230 162 159 105 144 174 148 197 82 207 63 231 66 191 84 172 214 25 73 136 30 114 68 80 53 214 5 156 152 131 161 15 193 30 53 174 94 25 25 143 94 13 9 91 4 32 199 192 31 6 96 64 61 153 209 108 160 134 211 199 19 42 59 203 160 14 203 99 78 178 90 50 215 90 141 124 53 145 43 23 171 10 116 189 152 11 115 104 3 80 117 4 199 64 194 116 125 42 58 230 182 72 207 65 126 1 197 54 128 58 46 6 222 72 201 82 36 97 79 118 186 139 215 83 224 30 192 163 199 103 161 178 127 66 39 52 108 158 14 81 21 40 41 64 66 116 32 149 82 111 207 73 65 3 224 62 45 185 80 209 125 185 198 54 91 216 33 216 220 24 82 179 177 84 65 86 181 182 26 35 55 95 71 48 152 122 142 93 122 83 215 219 172 222 221 163 127 102 220 7 143 101 196 191 49 209 125 2 196 9 155 36 108 177 92 103 155 120 40 179 231 211 119 125 47 195 131 57 74 192 5 211 4 228 58 196 3 88 164 42 125 233 103 219 153 229 168 193 227 146 100 224 172 231 187 140 151 143 76 59 52 41 163 175 77 146 177 161 18 27 233 227 33 195 7 [出力例] 70 |
■参照サイト
AtCoder Beginner Contest 166