C++の練習を兼ねて, AtCoder Regular Contest 135 の 問題C (XOR to All) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 一括して数え上げるロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 135 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc135/editorial/3356 // 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 x[303030], d[33][2]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ scanf("%lld", &x[i + 1]); rep(j, 30){ if(x[i + 1] & (1 << j)) d[j][1]++; // 1 を カウント. else d[j][0]++; // 0 を カウント. } } // 2. 操作後の数列 B. LL ans = 0; rep(i, N + 1){ // 2-1. 各 x で 計算. LL cur = 0; rep(j, 30){ if(x[i] & (1 << j)) cur += (1LL << j) * d[j][0]; else cur += (1LL << j) * d[j][1]; } // 2-2. 最大値更新. ans = max(ans, cur); } // 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 |
[入力例] 5 1 2 3 4 5 [出力例] 19 ※AtCoderのテストケースより [入力例] 5 10 10 10 10 10 [出力例] 50 ※AtCoderのテストケースより [入力例] 5 3 1 4 1 5 [出力例] 18 ※AtCoderのテストケースより [入力例] 10 58 53 36 53 71 45 79 56 91 64 [出力例] 736 [入力例] 50 11359 6089 6053 5356 4815 2314 5214 1971 11222 11632 1480 5775 9135 6597 4431 1028 10270 4920 1892 538 4805 6507 3228 5494 7929 7504 9109 5981 7001 11330 10230 4253 8590 4103 7524 7037 4356 9942 8591 7956 2185 8932 6956 12166 3423 10070 11659 3761 8262 10990 [出力例] 475341 |
■参照サイト
AtCoder Regular Contest 135