C++ の動作確認をしてみた（１１１）

C++の練習を兼ねて, AtCoder Beginner Contest 136 の問題E (E – Max GCD) を解いてみた.

■感想.
1. 操作を行っても, 和が変化しないこと, 及び, 答えの候補が, 和の約数であることまで, 予想出来たが, 具体的に, その後の処理が見えなかったので, 解答を参考に, 復習した.
2. 解説の方法で, 答えを見つけられることが, 非常に不思議に感じたものの, r の和が d の倍数となる性質を使っていることで, なるほどと感心した.

本家のサイトABC 136解説をご覧下さい.

■C++版プログラム(問題D／AC版).

// 解き直し.
// ABC 136解説
// https://img.atcoder.jp/abc136/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int N;
LL K, S, A[505], G;

// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数.
vector<LL> div(LL X){
    vector<LL> ret;
    ret.push_back(1);
    for(LL d = 2; d * d <= X; d++){
        if(X % d == 0){
            ret.push_back(d);
            if(d * d != X) ret.push_back(X / d);
        }
    }
    ret.push_back(X);
    sort(ret.begin(), ret.end());
    return ret;
}

int main(){

    // 1. 入力情報取得.
    scanf("%d %llu", &N, &K);
    for(int i = 0; i < N; i++){
        scanf("%llu", &A[i]);
        S += A[i];
        if(i == 0) G = A[i];
        else       G = __gcd(G, A[i]);
    }
    
    // 2. 解説通り.
    // S の 約数 を 計算.
    vector<LL> divisors = div(S);
    
    // 3. 各約数について, 操作の回数を計算.
    LL ans = G;
    for(auto &d : divisors){
        // 3-1. 各 A[i] を d で 割った余り を 確認.
        priority_queue<LL> r;
        for(int i = 0; i < N; i++) if(A[i] % d != 0) r.push(A[i] % d);
        
        // 3-2. d を 正にするもの, 負にするもの を 集計.
        int l = r.size();
        LL dPlus[l], dMinus[l];
        int index = 0;
        while(!r.empty()){
            // 余りを取得.
            LL v = r.top();
            r.pop();
            
            // d を 正 にする.
            dPlus[l - index - 1]  = d - v;
            // d を 負 にする.
            dMinus[l - index - 1] = -v;
            
            // index を increment.
            index++;
        }
        
        // 3-3. 前項で集計した結果の累積和を計算.
        // d を 正 にする.
        LL pCum[l];
        pCum[l - 1] = dPlus[l - 1];
        for(int i = l - 2; i >= 0; i--) pCum[i] = pCum[i + 1] + dPlus[i];
        
        // d を 負 にする.
        LL mCum[l];
        mCum[0] = dMinus[0];
        for(int i = 1; i < l; i++) mCum[i] = mCum[i - 1] + dMinus[i];
        
        // 3-4. 前項の累積和から, 操作回数が, K回以内で実現できるかをチェック.
        for(int i = 0; i < l - 1; i++){
            if(pCum[i + 1] + mCum[i] == 0 && pCum[i + 1] <= K){
                // 操作後の A の 全要素を割り切る正の整数について, 最大値を更新.
                ans = max(ans, d);
                break;
            }
        }
    }
    
    // 4. 出力 ～ 後処理.
    printf("%llu", ans);
    return 0;

}

// 解き直し.

// ABC 136解説

// https://img.atcoder.jp/abc136/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int N;

LL K, S, A[505], G;

// 与えられた正の整数のすべての約数を抽出.

// @param X: 約数を抽出したい正の整数.

// @return ret: すべての約数.

vector<LL> div(LL X){

vector<LL> ret;

ret.push_back(1);

for(LL d = 2; d * d <= X; d++){

if(X % d == 0){

ret.push_back(d);

if(d * d != X) ret.push_back(X / d);

}

ret.push_back(X);

sort(ret.begin(), ret.end());

return ret;

}

int main(){

// 1. 入力情報取得.

scanf("%d %llu", &N, &K);

for(int i = 0; i < N; i++){

scanf("%llu", &A[i]);

S += A[i];

if(i == 0) G = A[i];

else G = __gcd(G, A[i]);

}

// 2. 解説通り.

// S の約数を計算.

vector<LL> divisors = div(S);

// 3. 各約数について, 操作の回数を計算.

LL ans = G;

for(auto &d : divisors){

// 3-1. 各 A[i] を d で割った余りを確認.

priority_queue<LL> r;

for(int i = 0; i < N; i++) if(A[i] % d != 0) r.push(A[i] % d);

// 3-2. d を正にするもの, 負にするものを集計.

int l = r.size();

LL dPlus[l], dMinus[l];

int index = 0;

while(!r.empty()){

// 余りを取得.

LL v = r.top();

r.pop();

// d を正にする.

dPlus[l - index - 1] = d - v;

// d を負にする.

dMinus[l - index - 1] = -v;

// index を increment.

index++;

}

// 3-3. 前項で集計した結果の累積和を計算.

// d を正にする.

LL pCum[l];

pCum[l - 1] = dPlus[l - 1];

for(int i = l - 2; i >= 0; i--) pCum[i] = pCum[i + 1] + dPlus[i];

// d を負にする.

LL mCum[l];

mCum[0] = dMinus[0];

for(int i = 1; i < l; i++) mCum[i] = mCum[i - 1] + dMinus[i];

// 3-4. 前項の累積和から, 操作回数が, K回以内で実現できるかをチェック.

for(int i = 0; i < l - 1; i++){

if(pCum[i + 1] + mCum[i] == 0 && pCum[i + 1] <= K){

// 操作後の A の全要素を割り切る正の整数について, 最大値を更新.

ans = max(ans, d);

break;

}

// 4. 出力～後処理.

printf("%llu", ans);

return 0;

}

[入力例]
2 3
8 20

[出力例]
7
※AtCoderテストケースより

[入力例]
2 10
3 5

[出力例]
8
※AtCoderテストケースより

[入力例]
4 5
10 1 2 22

[出力例]
7
※AtCoderテストケースより

[入力例]
8 7
1 7 5 6 8 2 6 5

[出力例]
5
※AtCoderテストケースより

[入力例]
5 0
5 15 35 45 75

[出力例]
5

[入力例]
5 1
3 6 9 12 18

[出力例]
3

[入力例]
2 1
3 5

[出力例]
4

[入力例]
500 123456789
11 22 33 44 55 66 77 88 99 110 121 132 143 154 165 176 187 198 209 220 231 242 253 264 275 286 297 308 319 330 341 352 363 374 385 396 407 418 429 440 451 462 473 484 495 506 517 528 539 550 561 572 583 594 605 616 627 638 649 660 671 682 693 704 715 726 737 748 759 770 781 792 803 814 825 836 847 858 869 880 891 902 913 924 935 946 957 968 979 990 1001 1012 1023 1034 1045 1056 1067 1078 1089 1100 1111 1122 1133 1144 1155 1166 1177 1188 1199 1210 1221 1232 1243 1254 1265 1276 1287 1298 1309 1320 1331 1342 1353 1364 1375 1386 1397 1408 1419 1430 1441 1452 1463 1474 1485 1496 1507 1518 1529 1540 1551 1562 1573 1584 1595 1606 1617 1628 1639 1650 1661 1672 1683 1694 1705 1716 1727 1738 1749 1760 1771 1782 1793 1804 1815 1826 1837 1848 1859 1870 1881 1892 1903 1914 1925 1936 1947 1958 1969 1980 1991 2002 2013 2024 2035 2046 2057 2068 2079 2090 2101 2112 2123 2134 2145 2156 2167 2178 2189 2200 2211 2222 2233 2244 2255 2266 2277 2288 2299 2310 2321 2332 2343 2354 2365 2376 2387 2398 2409 2420 2431 2442 2453 2464 2475 2486 2497 2508 2519 2530 2541 2552 2563 2574 2585 2596 2607 2618 2629 2640 2651 2662 2673 2684 2695 2706 2717 2728 2739 2750 2761 2772 2783 2794 2805 2816 2827 2838 2849 2860 2871 2882 2893 2904 2915 2926 2937 2948 2959 2970 2981 2992 3003 3014 3025 3036 3047 3058 3069 3080 3091 3102 3113 3124 3135 3146 3157 3168 3179 3190 3201 3212 3223 3234 3245 3256 3267 3278 3289 3300 3311 3322 3333 3344 3355 3366 3377 3388 3399 3410 3421 3432 3443 3454 3465 3476 3487 3498 3509 3520 3531 3542 3553 3564 3575 3586 3597 3608 3619 3630 3641 3652 3663 3674 3685 3696 3707 3718 3729 3740 3751 3762 3773 3784 3795 3806 3817 3828 3839 3850 3861 3872 3883 3894 3905 3916 3927 3938 3949 3960 3971 3982 3993 4004 4015 4026 4037 4048 4059 4070 4081 4092 4103 4114 4125 4136 4147 4158 4169 4180 4191 4202 4213 4224 4235 4246 4257 4268 4279 4290 4301 4312 4323 4334 4345 4356 4367 4378 4389 4400 4411 4422 4433 4444 4455 4466 4477 4488 4499 4510 4521 4532 4543 4554 4565 4576 4587 4598 4609 4620 4631 4642 4653 4664 4675 4686 4697 4708 4719 4730 4741 4752 4763 4774 4785 4796 4807 4818 4829 4840 4851 4862 4873 4884 4895 4906 4917 4928 4939 4950 4961 4972 4983 4994 5005 5016 5027 5038 5049 5060 5071 5082 5093 5104 5115 5126 5137 5148 5159 5170 5181 5192 5203 5214 5225 5236 5247 5258 5269 5280 5291 5302 5313 5324 5335 5346 5357 5368 5379 5390 5401 5412 5423 5434 5445 5456 5467 5478 5489 5500
[出力例]
1377750

[入力例]
500 987654321
1001 2002 3003 4004 5005 6006 7007 8008 9009 10010 11011 12012 13013 14014 15015 16016 17017 18018 19019 20020 21021 22022 23023 24024 25025 26026 27027 28028 29029 30030 31031 32032 33033 34034 35035 36036 37037 38038 39039 40040 41041 42042 43043 44044 45045 46046 47047 48048 49049 50050 51051 52052 53053 54054 55055 56056 57057 58058 59059 60060 61061 62062 63063 64064 65065 66066 67067 68068 69069 70070 71071 72072 73073 74074 75075 76076 77077 78078 79079 80080 81081 82082 83083 84084 85085 86086 87087 88088 89089 90090 91091 92092 93093 94094 95095 96096 97097 98098 99099 100100 101101 102102 103103 104104 105105 106106 107107 108108 109109 110110 111111 112112 113113 114114 115115 116116 117117 118118 119119 120120 121121 122122 123123 124124 125125 126126 127127 128128 129129 130130 131131 132132 133133 134134 135135 136136 137137 138138 139139 140140 141141 142142 143143 144144 145145 146146 147147 148148 149149 150150 151151 152152 153153 154154 155155 156156 157157 158158 159159 160160 161161 162162 163163 164164 165165 166166 167167 168168 169169 170170 171171 172172 173173 174174 175175 176176 177177 178178 179179 180180 181181 182182 183183 184184 185185 186186 187187 188188 189189 190190 191191 192192 193193 194194 195195 196196 197197 198198 199199 200200 201201 202202 203203 204204 205205 206206 207207 208208 209209 210210 211211 212212 213213 214214 215215 216216 217217 218218 219219 220220 221221 222222 223223 224224 225225 226226 227227 228228 229229 230230 231231 232232 233233 234234 235235 236236 237237 238238 239239 240240 241241 242242 243243 244244 245245 246246 247247 248248 249249 250250 251251 252252 253253 254254 255255 256256 257257 258258 259259 260260 261261 262262 263263 264264 265265 266266 267267 268268 269269 270270 271271 272272 273273 274274 275275 276276 277277 278278 279279 280280 281281 282282 283283 284284 285285 286286 287287 288288 289289 290290 291291 292292 293293 294294 295295 296296 297297 298298 299299 300300 301301 302302 303303 304304 305305 306306 307307 308308 309309 310310 311311 312312 313313 314314 315315 316316 317317 318318 319319 320320 321321 322322 323323 324324 325325 326326 327327 328328 329329 330330 331331 332332 333333 334334 335335 336336 337337 338338 339339 340340 341341 342342 343343 344344 345345 346346 347347 348348 349349 350350 351351 352352 353353 354354 355355 356356 357357 358358 359359 360360 361361 362362 363363 364364 365365 366366 367367 368368 369369 370370 371371 372372 373373 374374 375375 376376 377377 378378 379379 380380 381381 382382 383383 384384 385385 386386 387387 388388 389389 390390 391391 392392 393393 394394 395395 396396 397397 398398 399399 400400 401401 402402 403403 404404 405405 406406 407407 408408 409409 410410 411411 412412 413413 414414 415415 416416 417417 418418 419419 420420 421421 422422 423423 424424 425425 426426 427427 428428 429429 430430 431431 432432 433433 434434 435435 436436 437437 438438 439439 440440 441441 442442 443443 444444 445445 446446 447447 448448 449449 450450 451451 452452 453453 454454 455455 456456 457457 458458 459459 460460 461461 462462 463463 464464 465465 466466 467467 468468 469469 470470 471471 472472 473473 474474 475475 476476 477477 478478 479479 480480 481481 482482 483483 484484 485485 486486 487487 488488 489489 490490 491491 492492 493493 494494 495495 496496 497497 498498 499499 500500

[出力例]
125375250

[入力例]

2 3

8 20

[出力例]

※AtCoderテストケースより

[入力例]

2 10

3 5

[出力例]

※AtCoderテストケースより

[入力例]

4 5

10 1 2 22

[出力例]

※AtCoderテストケースより

[入力例]

8 7

1 7 5 6 8 2 6 5

[出力例]

※AtCoderテストケースより

[入力例]

5 0

5 15 35 45 75

[出力例]

[入力例]

5 1

3 6 9 12 18

[出力例]

[入力例]

2 1

3 5

[出力例]

[入力例]

500 123456789

11 22 33 44 55 66 77 88 99 110 121 132 143 154 165 176 187 198 209 220 231 242 253 264 275 286 297 308 319 330 341 352 363 374 385 396 407 418 429 440 451 462 473 484 495 506 517 528 539 550 561 572 583 594 605 616 627 638 649 660 671 682 693 704 715 726 737 748 759 770 781 792 803 814 825 836 847 858 869 880 891 902 913 924 935 946 957 968 979 990 1001 1012 1023 1034 1045 1056 1067 1078 1089 1100 1111 1122 1133 1144 1155 1166 1177 1188 1199 1210 1221 1232 1243 1254 1265 1276 1287 1298 1309 1320 1331 1342 1353 1364 1375 1386 1397 1408 1419 1430 1441 1452 1463 1474 1485 1496 1507 1518 1529 1540 1551 1562 1573 1584 1595 1606 1617 1628 1639 1650 1661 1672 1683 1694 1705 1716 1727 1738 1749 1760 1771 1782 1793 1804 1815 1826 1837 1848 1859 1870 1881 1892 1903 1914 1925 1936 1947 1958 1969 1980 1991 2002 2013 2024 2035 2046 2057 2068 2079 2090 2101 2112 2123 2134 2145 2156 2167 2178 2189 2200 2211 2222 2233 2244 2255 2266 2277 2288 2299 2310 2321 2332 2343 2354 2365 2376 2387 2398 2409 2420 2431 2442 2453 2464 2475 2486 2497 2508 2519 2530 2541 2552 2563 2574 2585 2596 2607 2618 2629 2640 2651 2662 2673 2684 2695 2706 2717 2728 2739 2750 2761 2772 2783 2794 2805 2816 2827 2838 2849 2860 2871 2882 2893 2904 2915 2926 2937 2948 2959 2970 2981 2992 3003 3014 3025 3036 3047 3058 3069 3080 3091 3102 3113 3124 3135 3146 3157 3168 3179 3190 3201 3212 3223 3234 3245 3256 3267 3278 3289 3300 3311 3322 3333 3344 3355 3366 3377 3388 3399 3410 3421 3432 3443 3454 3465 3476 3487 3498 3509 3520 3531 3542 3553 3564 3575 3586 3597 3608 3619 3630 3641 3652 3663 3674 3685 3696 3707 3718 3729 3740 3751 3762 3773 3784 3795 3806 3817 3828 3839 3850 3861 3872 3883 3894 3905 3916 3927 3938 3949 3960 3971 3982 3993 4004 4015 4026 4037 4048 4059 4070 4081 4092 4103 4114 4125 4136 4147 4158 4169 4180 4191 4202 4213 4224 4235 4246 4257 4268 4279 4290 4301 4312 4323 4334 4345 4356 4367 4378 4389 4400 4411 4422 4433 4444 4455 4466 4477 4488 4499 4510 4521 4532 4543 4554 4565 4576 4587 4598 4609 4620 4631 4642 4653 4664 4675 4686 4697 4708 4719 4730 4741 4752 4763 4774 4785 4796 4807 4818 4829 4840 4851 4862 4873 4884 4895 4906 4917 4928 4939 4950 4961 4972 4983 4994 5005 5016 5027 5038 5049 5060 5071 5082 5093 5104 5115 5126 5137 5148 5159 5170 5181 5192 5203 5214 5225 5236 5247 5258 5269 5280 5291 5302 5313 5324 5335 5346 5357 5368 5379 5390 5401 5412 5423 5434 5445 5456 5467 5478 5489 5500

[出力例]

1377750

[入力例]

500 987654321

1001 2002 3003 4004 5005 6006 7007 8008 9009 10010 11011 12012 13013 14014 15015 16016 17017 18018 19019 20020 21021 22022 23023 24024 25025 26026 27027 28028 29029 30030 31031 32032 33033 34034 35035 36036 37037 38038 39039 40040 41041 42042 43043 44044 45045 46046 47047 48048 49049 50050 51051 52052 53053 54054 55055 56056 57057 58058 59059 60060 61061 62062 63063 64064 65065 66066 67067 68068 69069 70070 71071 72072 73073 74074 75075 76076 77077 78078 79079 80080 81081 82082 83083 84084 85085 86086 87087 88088 89089 90090 91091 92092 93093 94094 95095 96096 97097 98098 99099 100100 101101 102102 103103 104104 105105 106106 107107 108108 109109 110110 111111 112112 113113 114114 115115 116116 117117 118118 119119 120120 121121 122122 123123 124124 125125 126126 127127 128128 129129 130130 131131 132132 133133 134134 135135 136136 137137 138138 139139 140140 141141 142142 143143 144144 145145 146146 147147 148148 149149 150150 151151 152152 153153 154154 155155 156156 157157 158158 159159 160160 161161 162162 163163 164164 165165 166166 167167 168168 169169 170170 171171 172172 173173 174174 175175 176176 177177 178178 179179 180180 181181 182182 183183 184184 185185 186186 187187 188188 189189 190190 191191 192192 193193 194194 195195 196196 197197 198198 199199 200200 201201 202202 203203 204204 205205 206206 207207 208208 209209 210210 211211 212212 213213 214214 215215 216216 217217 218218 219219 220220 221221 222222 223223 224224 225225 226226 227227 228228 229229 230230 231231 232232 233233 234234 235235 236236 237237 238238 239239 240240 241241 242242 243243 244244 245245 246246 247247 248248 249249 250250 251251 252252 253253 254254 255255 256256 257257 258258 259259 260260 261261 262262 263263 264264 265265 266266 267267 268268 269269 270270 271271 272272 273273 274274 275275 276276 277277 278278 279279 280280 281281 282282 283283 284284 285285 286286 287287 288288 289289 290290 291291 292292 293293 294294 295295 296296 297297 298298 299299 300300 301301 302302 303303 304304 305305 306306 307307 308308 309309 310310 311311 312312 313313 314314 315315 316316 317317 318318 319319 320320 321321 322322 323323 324324 325325 326326 327327 328328 329329 330330 331331 332332 333333 334334 335335 336336 337337 338338 339339 340340 341341 342342 343343 344344 345345 346346 347347 348348 349349 350350 351351 352352 353353 354354 355355 356356 357357 358358 359359 360360 361361 362362 363363 364364 365365 366366 367367 368368 369369 370370 371371 372372 373373 374374 375375 376376 377377 378378 379379 380380 381381 382382 383383 384384 385385 386386 387387 388388 389389 390390 391391 392392 393393 394394 395395 396396 397397 398398 399399 400400 401401 402402 403403 404404 405405 406406 407407 408408 409409 410410 411411 412412 413413 414414 415415 416416 417417 418418 419419 420420 421421 422422 423423 424424 425425 426426 427427 428428 429429 430430 431431 432432 433433 434434 435435 436436 437437 438438 439439 440440 441441 442442 443443 444444 445445 446446 447447 448448 449449 450450 451451 452452 453453 454454 455455 456456 457457 458458 459459 460460 461461 462462 463463 464464 465465 466466 467467 468468 469469 470470 471471 472472 473473 474474 475475 476476 477477 478478 479479 480480 481481 482482 483483 484484 485485 486486 487487 488488 489489 490490 491491 492492 493493 494494 495495 496496 497497 498498 499499 500500

[出力例]

125375250

■参照サイト
AtCoder Beginner Contest 136

C++の練習を兼ねて, AtCoder Beginner Contest 136 の 問題E (E – Max GCD) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 136 の問題E (E – Max GCD) を解いてみた.

コメントを残すコメントをキャンセル