C++の練習を兼ねて, AtCoder Regular Contest 145 の 問題D (Non Arithmetic Progression Set) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 階差数列的なものを考えると, 制約から, はみ出してしまうが, 解説のように, 3進数で考えると, 制約を満たすものを探し出せることが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 145 解説 の 各リンク を ご覧下さい.
■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 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 |
// 解き直し. // https://atcoder.jp/contests/arc145/editorial/4227 // C++(GCC 9.2.1) #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 int main(){ // 1. 入力情報. int N; LL M; scanf("%d %lld", &N, &M); // 2. 3 の 冪乗. vl cPow3; cPow3.pb(1); while(cPow3.size() < 20){ // 2-1. 最大値 3倍. LL p = 3 * cPow3.back(); // 2-2. 保存. cPow3.pb(p); } // for(auto &p : cPow3) printf("%lld\n", p); // 3. 良い集合. // 3-1. 桁数. int n = 0, d = -1; while(n < N) n = 1 << (++d); // printf("n=%d d=%d\n", n, d); // 3-2. 良い整数. vl S; LL t = 0; rep(i, N){ LL cur = 0; rep(j, d + 1) if(i & (1 << j)) cur += cPow3[j + 1]; S.pb(cur); t += cur; } // for(auto &p : S) printf("%lld\n", p); // 4. 総和の制約を考慮. // 4-1. M との 差分. LL g = M - t; LL q = g / N; LL r = g % N; if(g < 0 && r != 0){ --q; r += N; } // 4-2. 平行移動. rep(i, N) S[i] += q; // 4-3. 下1桁調整. rep(i, r) ++S[i]; // 5. 出力. rep(i, N) printf("%lld%s", S[i], (i < N - 1) ? " " : "\n"); 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 |
[入力例] 3 9 [出力例] 1 2 6 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. -1 2 8 [入力例] 5 -15 [出力例] -15 -5 0 2 3 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. -13 -10 -4 -1 13 [入力例] 7 0 [出力例] -16 -13 -8 -5 10 13 19 [入力例] 20 2022 [出力例] 4 7 13 16 31 34 39 42 84 87 93 96 111 114 120 123 246 249 255 258 [入力例] 25 -123 [出力例] -140 -137 -131 -128 -113 -110 -104 -101 -59 -56 -50 -47 -32 -29 -23 -20 103 106 111 114 129 132 138 141 183 [入力例] 50 20220807 [出力例] 404009 404012 404018 404021 404036 404039 404045 404048 404090 404093 404099 404102 404117 404120 404126 404129 404252 404255 404261 404264 404279 404282 404288 404291 404333 404336 404342 404345 404359 404362 404368 404371 404737 404740 404746 404749 404764 404767 404773 404776 404818 404821 404827 404830 404845 404848 404854 404857 404980 404983 [入力例] 100 1234567 [出力例] 11122 11125 11131 11134 11149 11152 11158 11161 11203 11206 11212 11215 11230 11233 11239 11242 11365 11368 11374 11377 11392 11395 11401 11404 11446 11449 11455 11458 11473 11476 11482 11485 11851 11854 11860 11863 11878 11881 11887 11890 11932 11935 11941 11943 11958 11961 11967 11970 12093 12096 12102 12105 12120 12123 12129 12132 12174 12177 12183 12186 12201 12204 12210 12213 13308 13311 13317 13320 13335 13338 13344 13347 13389 13392 13398 13401 13416 13419 13425 13428 13551 13554 13560 13563 13578 13581 13587 13590 13632 13635 13641 13644 13659 13662 13668 13671 14037 14040 14046 14049 |
■参照サイト
AtCoder Regular Contest 145