C++の練習を兼ねて, 競プロ典型 90 問 の 問題080 (Let’s Share Bit) を解いてみた.
■感想.
1. 問題080は, 方針が見えなかったので, (問題080 (Let’s Share Bit) 解説) を参考に実装したところ, AC版に到達出来た.
2. 包除原理に関する訓練が出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題080 を ご覧下さい.
■C++版プログラム(問題080／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 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/080.jpg // 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 a[22]; int main(){ // 1. 入力情報. int N, D; scanf("%d %d", &N, &D); rep(i, N) scanf("%lld", &a[i]); // 2. 条件を満たすものをカウント(解説通り). LL ans = 1LL << D; repx(bit, 1, 1 << N){ LL x = 0; repr(i, N - 1, 0) if(bit & (1 << i)) x |= a[i]; LL f = 1LL << (D - __builtin_popcountll(x)); ans += (1 & __builtin_popcount(bit)) ? -f : f; } // 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 |
[入力例] 4 3 1 3 4 5 [出力例] 2 ※AtCoderテストケースより [入力例] 5 21 1050624 32772 493952 144 869120 [出力例] 869120 ※AtCoderテストケースより [入力例] 20 60 216181578206878016 81348488767472704 26388280246272 281543729742896 72127981178847488 2199108462600 585610888171487234 22027813536776 567459673280576 146648462866649600 144484898860704776 576471786208755714 4398621196432 144141576657960976 81069330992726040 360851057582278674 17859112 11570646360064 144115206396936193 1702052723957760 [出力例] 977902973481140224 ※AtCoderテストケースより [入力例] 3 5 2 17 23 [出力例] 12 [入力例] 18 10 314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582 [出力例] 568 [入力例] 10 30 22275554 98136531 84288905 53485744 99268102 84582267 122830211 99671610 58981632 96084779 [出力例] 1068048752 |