C++ の動作確認をしてみた（６３８）

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題F (Spices) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 計算できることについて, 非常に, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 236 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc236/editorial/3287
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vp = vector<P>;
using vi = vector<int>;
#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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()
int b[1 << 16], c[1 << 16];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v;
    repx(i, 1, 1 << N){
        scanf("%d", &c[i]);
        v.pb({c[i], i});
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 貪欲アルゴリズム(解説通り).
    vi S;
    b[0] = 1;
    for(auto &p : v){
        // S の 要素から, 辛さ p.b を 作れる場合.
        if(b[p.b]) continue;
        
        // S の 要素から, 辛さ p.b を 作れない場合. 
        // -> S に 要素を追加し, フラグ b を 更新.
        S.pb(p.b);
        rep(i, 1 << N) if(b[i]) b[i ^ p.b] = 1;
    }
    
    // 4. 集計.
    LL ans = 0;
    for(auto &p : S) ans += (LL)c[p];
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc236/editorial/3287

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector<P>;

using vi = vector<int>;

#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 a first

#define b second

#define pb push_back

#define all(x) x.begin(), x.end()

int b[1 << 16], c[1 << 16];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v;

repx(i, 1, 1 << N){

scanf("%d", &c[i]);

v.pb({c[i], i});

}

// 2. sort.

sort(all(v));

// 3. 貪欲アルゴリズム(解説通り).

vi S;

b[0] = 1;

for(auto &p : v){

// S の要素から, 辛さ p.b を作れる場合.

if(b[p.b]) continue;

// S の要素から, 辛さ p.b を作れない場合.

// -> S に要素を追加し, フラグ b を更新.

S.pb(p.b);

rep(i, 1 << N) if(b[i]) b[i ^ p.b] = 1;

}

// 4. 集計.

LL ans = 0;

for(auto &p : S) ans += (LL)c[p];

// 5. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
2
4 5 3

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

[入力例]
4
9 7 9 7 10 4 3 9 4 8 10 5 6 3 8

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

[入力例]
1
10

[出力例]
10

[入力例]
3
16 30 26 6 33 18 27

[出力例]
40

[入力例]
7
129 290 138 144 521 138 541 413 255 462 202 497 245 7 414 246 529 547 342 366 442 348 509 166 67 140 40 115 129 34 476 62 312 390 461 194 352 518 21 436 426 146 220 403 207 152 309 44 472 293 50 133 322 374 544 311 553 499 549 90 293 59 109 279 338 475 307 162 527 404 282 498 258 220 126 268 341 355 160 301 480 331 263 289 393 187 528 182 285 471 345 395 454 209 419 551 137 242 282 186 466 361 63 358 199 209 308 371 31 369 141 534 213 515 262 335 56 103 153 284 218 518 541 15 418 190 435

[出力例]
192

[入力例]
10
858 582 452 236 475 298 137 74 213 307 808 73 141 585 5 561 770 524 416 663 180 822 70 769 248 730 254 363 19 667 280 235 328 715 291 404 668 496 202 862 56 230 664 582 428 793 559 795 71 891 532 902 582 341 216 519 819 899 968 380 402 405 828 66 472 959 224 204 599 711 651 962 414 33 412 654 689 370 528 512 570 140 114 407 779 945 271 48 168 856 221 279 737 307 957 994 646 214 336 25 760 968 934 318 341 42 780 863 941 507 64 179 315 379 411 612 610 48 831 533 938 525 344 695 420 363 176 824 354 180 787 324 13 729 504 456 996 631 250 840 708 161 620 595 689 316 761 458 60 127 703 701 90 539 156 432 483 540 274 845 416 259 55 133 143 786 969 826 853 195 757 171 963 316 842 744 84 465 281 432 527 146 896 897 507 960 312 997 941 584 524 526 11 663 148 344 53 315 838 486 708 555 273 830 820 346 506 37 485 133 159 417 394 211 73 862 886 930 550 446 550 626 145 624 854 615 624 598 840 895 817 646 640 425 628 434 831 165 993 434 897 248 427 646 936 349 270 512 683 921 961 699 823 79 570 507 923 105 56 826 23 768 562 705 976 25 481 653 511 682 313 945 472 174 858 137 760 540 59 546 983 6 940 236 657 877 863 457 374 791 153 839 709 688 871 333 634 395 66 443 397 659 12 696 993 661 452 795 606 407 582 439 756 31 651 738 858 151 451 565 193 677 112 590 736 734 53 537 192 862 870 352 725 349 936 988 388 639 96 356 156 938 708 335 323 937 986 621 950 33 837 571 958 333 374 873 222 892 96 819 980 542 748 231 161 786 244 441 639 358 843 734 102 802 249 42 222 407 142 564 54 876 430 278 592 498 119 125 451 317 678 814 150 927 887 10 93 916 708 729 669 724 296 733 533 834 412 940 488 529 887 982 915 958 769 977 432 800 995 443 76 164 182 653 40 631 737 249 863 955 199 545 288 396 454 129 905 908 130 389 173 474 257 997 164 74 444 171 465 363 848 689 225 30 26 515 185 477 141 47 293 199 515 362 752 875 500 513 397 602 468 834 758 832 129 878 82 510 651 23 28 369 224 227 962 201 779 596 270 247 328 749 910 803 14 563 561 344 49 3 869 742 874 800 448 109 659 231 986 792 183 831 920 575 460 311 99 306 762 696 370 58 35 306 534 731 128 446 187 113 143 547 149 404 613 816 567 785 367 702 703 881 494 37 931 579 572 572 387 294 74 54 283 265 356 764 364 124 66 202 287 609 350 40 680 344 272 763 311 447 276 782 975 637 98 660 260 545 834 678 865 563 701 773 837 380 592 22 441 608 554 87 421 13 261 48 959 409 955 763 672 438 284 77 86 112 886 528 464 484 801 188 161 301 140 296 252 35 655 115 89 673 915 860 911 980 271 493 876 183 806 719 568 62 187 211 145 66 895 50 13 992 758 710 832 221 949 645 874 86 745 953 369 730 715 389 427 725 633 15 950 318 160 248 290 979 225 550 285 139 231 414 673 853 264 219 33 352 823 430 526 679 489 855 998 638 148 345 976 189 668 336 938 880 567 90 481 847 189 952 151 55 702 956 23 550 647 125 7 276 721 961 556 498 774 448 794 333 100 705 156 714 414 259 534 645 356 140 767 54 691 827 716 742 824 77 694 701 336 212 366 285 148 871 531 487 920 936 442 778 960 928 524 642 460 163 795 334 793 644 890 392 180 683 464 490 397 776 20 718 668 344 408 890 714 399 627 775 276 612 460 336 772 634 302 257 944 695 636 995 116 709 183 397 40 694 101 564 598 720 457 439 56 904 657 161 471 625 262 68 437 883 833 443 758 883 660 435 693 618 21 456 163 238 16 568 173 28 548 844 608 814 69 842 917 788 774 106 585 704 950 115 802 56 457 135 496 193 658 687 355 912 573 91 515 976 182 764 510 505 461 216 376 474 886 731 460 934 520 503 202 331 82 178 752 559 177 787 657 911 877 687 644 636 440 862 139 835 200 399 769 455 109 752 742 412 20 636 418 211 523 758 798 163 329 906 789 282 748 992 322 531 15 761 478 522 610 859 206 893 738 81 229 305 788 775 45 514 505 1 854 699 916 320 476 239 736 815 856 745 215 91 502 962 232 154 287 258 354 133 476 101 540 784 104 489 459 589 984 198 907 958 721 183 529 243 306 184 420 533 334 916 410 192 603 919 348 133 575 337 697 325 718 279 533 117 362 324 320 531 862 668 109 883 225 57 735 62 313 229 641 943 402 488 9 242 415 202 906 412 624 149 584 265 321 40 554 299 453 392 205 72 99

[出力例]
77

[入力例]

4 5 3

[出力例]

※AtCoderテストケースより

[入力例]

9 7 9 7 10 4 3 9 4 8 10 5 6 3 8

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

16 30 26 6 33 18 27

[出力例]

[入力例]

129 290 138 144 521 138 541 413 255 462 202 497 245 7 414 246 529 547 342 366 442 348 509 166 67 140 40 115 129 34 476 62 312 390 461 194 352 518 21 436 426 146 220 403 207 152 309 44 472 293 50 133 322 374 544 311 553 499 549 90 293 59 109 279 338 475 307 162 527 404 282 498 258 220 126 268 341 355 160 301 480 331 263 289 393 187 528 182 285 471 345 395 454 209 419 551 137 242 282 186 466 361 63 358 199 209 308 371 31 369 141 534 213 515 262 335 56 103 153 284 218 518 541 15 418 190 435

[出力例]

192

[入力例]

858 582 452 236 475 298 137 74 213 307 808 73 141 585 5 561 770 524 416 663 180 822 70 769 248 730 254 363 19 667 280 235 328 715 291 404 668 496 202 862 56 230 664 582 428 793 559 795 71 891 532 902 582 341 216 519 819 899 968 380 402 405 828 66 472 959 224 204 599 711 651 962 414 33 412 654 689 370 528 512 570 140 114 407 779 945 271 48 168 856 221 279 737 307 957 994 646 214 336 25 760 968 934 318 341 42 780 863 941 507 64 179 315 379 411 612 610 48 831 533 938 525 344 695 420 363 176 824 354 180 787 324 13 729 504 456 996 631 250 840 708 161 620 595 689 316 761 458 60 127 703 701 90 539 156 432 483 540 274 845 416 259 55 133 143 786 969 826 853 195 757 171 963 316 842 744 84 465 281 432 527 146 896 897 507 960 312 997 941 584 524 526 11 663 148 344 53 315 838 486 708 555 273 830 820 346 506 37 485 133 159 417 394 211 73 862 886 930 550 446 550 626 145 624 854 615 624 598 840 895 817 646 640 425 628 434 831 165 993 434 897 248 427 646 936 349 270 512 683 921 961 699 823 79 570 507 923 105 56 826 23 768 562 705 976 25 481 653 511 682 313 945 472 174 858 137 760 540 59 546 983 6 940 236 657 877 863 457 374 791 153 839 709 688 871 333 634 395 66 443 397 659 12 696 993 661 452 795 606 407 582 439 756 31 651 738 858 151 451 565 193 677 112 590 736 734 53 537 192 862 870 352 725 349 936 988 388 639 96 356 156 938 708 335 323 937 986 621 950 33 837 571 958 333 374 873 222 892 96 819 980 542 748 231 161 786 244 441 639 358 843 734 102 802 249 42 222 407 142 564 54 876 430 278 592 498 119 125 451 317 678 814 150 927 887 10 93 916 708 729 669 724 296 733 533 834 412 940 488 529 887 982 915 958 769 977 432 800 995 443 76 164 182 653 40 631 737 249 863 955 199 545 288 396 454 129 905 908 130 389 173 474 257 997 164 74 444 171 465 363 848 689 225 30 26 515 185 477 141 47 293 199 515 362 752 875 500 513 397 602 468 834 758 832 129 878 82 510 651 23 28 369 224 227 962 201 779 596 270 247 328 749 910 803 14 563 561 344 49 3 869 742 874 800 448 109 659 231 986 792 183 831 920 575 460 311 99 306 762 696 370 58 35 306 534 731 128 446 187 113 143 547 149 404 613 816 567 785 367 702 703 881 494 37 931 579 572 572 387 294 74 54 283 265 356 764 364 124 66 202 287 609 350 40 680 344 272 763 311 447 276 782 975 637 98 660 260 545 834 678 865 563 701 773 837 380 592 22 441 608 554 87 421 13 261 48 959 409 955 763 672 438 284 77 86 112 886 528 464 484 801 188 161 301 140 296 252 35 655 115 89 673 915 860 911 980 271 493 876 183 806 719 568 62 187 211 145 66 895 50 13 992 758 710 832 221 949 645 874 86 745 953 369 730 715 389 427 725 633 15 950 318 160 248 290 979 225 550 285 139 231 414 673 853 264 219 33 352 823 430 526 679 489 855 998 638 148 345 976 189 668 336 938 880 567 90 481 847 189 952 151 55 702 956 23 550 647 125 7 276 721 961 556 498 774 448 794 333 100 705 156 714 414 259 534 645 356 140 767 54 691 827 716 742 824 77 694 701 336 212 366 285 148 871 531 487 920 936 442 778 960 928 524 642 460 163 795 334 793 644 890 392 180 683 464 490 397 776 20 718 668 344 408 890 714 399 627 775 276 612 460 336 772 634 302 257 944 695 636 995 116 709 183 397 40 694 101 564 598 720 457 439 56 904 657 161 471 625 262 68 437 883 833 443 758 883 660 435 693 618 21 456 163 238 16 568 173 28 548 844 608 814 69 842 917 788 774 106 585 704 950 115 802 56 457 135 496 193 658 687 355 912 573 91 515 976 182 764 510 505 461 216 376 474 886 731 460 934 520 503 202 331 82 178 752 559 177 787 657 911 877 687 644 636 440 862 139 835 200 399 769 455 109 752 742 412 20 636 418 211 523 758 798 163 329 906 789 282 748 992 322 531 15 761 478 522 610 859 206 893 738 81 229 305 788 775 45 514 505 1 854 699 916 320 476 239 736 815 856 745 215 91 502 962 232 154 287 258 354 133 476 101 540 784 104 489 459 589 984 198 907 958 721 183 529 243 306 184 420 533 334 916 410 192 603 919 348 133 575 337 697 325 718 279 533 117 362 324 320 531 862 668 109 883 225 57 735 62 313 229 641 943 402 488 9 242 415 202 906 412 624 149 584 265 321 40 554 299 453 392 205 72 99

[出力例]

■参照サイト
AtCoder Beginner Contest 236

C++の練習を兼ねて, AtCoder Beginner Contest 236 の 問題F (Spices) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題F (Spices) を解いてみた.

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