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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題D (Differ by K bits) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説および解説プログラムを参考に実装して, AC版に到達出来た.
2. 但し, AC版に, なかなか到達できなかったため, 調査したところ, XOR基底の計算方法が, 誤っていたと推測し, XOR基底の計算部分は, 解説プログラムを参考にして, 差し替えた(※).
※ popcount が K となる Nbit整数を一つ取って来て, これを, 1bitずつスライドする方法は, 正しくないとのこと.
現象としては, 数列 b のサイズが, 期待した値よりも小さくなり, 数列 b の作成時に, 重複要素が発生することから推定した.
3. 個人的には, 特殊な性質を持つ数列を抽出するロジックが, 非常に面白く感じたとともに, XOR基底の計算方法について, 新たな知識が増えたと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc138/editorial/3741
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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 pb push_back

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. Gray code.
    // https://ja.wikipedia.org/wiki/グレイコード
    vi a;
    int n = 1 << N;
    rep(i, n) a.pb(i ^ (i >> 1));
    // for(auto &p : a) printf("%d ", p);
    // puts("");
    
    // 3. K = 1.
    if(K == 1){
        puts("Yes");
        rep(i, n) printf("%d%s", a[i], (i < n - 1) ? " " : "\n");
        return 0;
    }
    
    // 4. 例外(01-010.txt などのWA回避のため, ロジック修正).
    if(!(K & 1) || K == N){
        puts("No");
        return 0;
    }
    
    // 5. XOR基底.
    /*
    // 以下のロジック(1 bitずつスライド)では, N bit の XOR基底にならない, とのこと.
    int x = (1 << K) - 1;
    vi z;
    rep(i, N){
        z.pb(x);
        x <<= 1;
        x %= n;
        if(__builtin_popcount(x) < K) ++x;
    }
    */
    // 解説プログラム参照(01-015.txt などのWA回避のため, ロジック修正).
    // https://atcoder.jp/contests/arc138/submissions/30615329
    vi z;
    int m1 = (1 << (K + 1)) - 1;
    int m2 = (1 << (K - 1)) - 1;
    rep(i, N){
        if(i < K - 1) z.pb(m1 ^ (1 << i));
        else          z.pb(m2 ^ (1 << i));
    }
    // for(auto &p : z) printf("%d ", p);
    // puts("");
    
    // 6. 数列 b.
    vi b;
    set<int> st;
    for(auto &p : a){
        // 数列 a (Gray code) で, bit が 1 となっている位置を元に, 数列 b を 計算.
        int cur = 0;
        rep(j, N) if(p & (1 << (N - 1 - j))) cur ^= z[j];
        b.pb(cur);
        st.insert(cur);
    }
    // printf("st.size()=%d b.size()=%d\n", st.size(), b.size());
    
    // 7. 出力.
    puts("Yes");
    rep(i, n) printf("%d%s", b[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc138/editorial/3741

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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 pb push_back

int main(){

// 1. 入力情報.

int N, K;

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

// 2. Gray code.

// https://ja.wikipedia.org/wiki/グレイコード

vi a;

int n = 1 << N;

rep(i, n) a.pb(i ^ (i >> 1));

// for(auto &p : a) printf("%d ", p);

// puts("");

// 3. K = 1.

if(K == 1){

puts("Yes");

rep(i, n) printf("%d%s", a[i], (i < n - 1) ? " " : "\n");

return 0;

}

// 4. 例外(01-010.txt などのWA回避のため, ロジック修正).

if(!(K & 1) || K == N){

puts("No");

return 0;

}

// 5. XOR基底.

// 以下のロジック(1 bitずつスライド)では, N bit の XOR基底にならない, とのこと.

int x = (1 << K) - 1;

vi z;

rep(i, N){

z.pb(x);

x <<= 1;

x %= n;

if(__builtin_popcount(x) < K) ++x;

}

// 解説プログラム参照(01-015.txt などのWA回避のため, ロジック修正).

// https://atcoder.jp/contests/arc138/submissions/30615329

vi z;

int m1 = (1 << (K + 1)) - 1;

int m2 = (1 << (K - 1)) - 1;

rep(i, N){

if(i < K - 1) z.pb(m1 ^ (1 << i));

else z.pb(m2 ^ (1 << i));

}

// for(auto &p : z) printf("%d ", p);

// puts("");

// 6. 数列 b.

vi b;

set<int> st;

for(auto &p : a){

// 数列 a (Gray code) で, bit が 1 となっている位置を元に, 数列 b を計算.

int cur = 0;

rep(j, N) if(p & (1 << (N - 1 - j))) cur ^= z[j];

b.pb(cur);

st.insert(cur);

}

// printf("st.size()=%d b.size()=%d\n", st.size(), b.size());

// 7. 出力.

puts("Yes");

rep(i, n) printf("%d%s", b[i], (i < n - 1) ? " " : "\n");

return 0;

}

[入力例]
3 1

[出力例]
Yes
0 1 3 2 6 7 5 4
※AtCoderのテストケースより

[入力例]
2 2

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

[入力例]
5 3

[出力例]
Yes
0 19 24 11 12 31 20 7 10 25 18 1 6 21 30 13 3 16 27 8 15 28 23 4 9 26 17 2 5 22 29 14

[入力例]
5 4

[出力例]
No

[入力例]
7 5

[出力例]
Yes
0 79 96 47 48 127 80 31 40 103 72 7 24 87 120 55 12 67 108 35 60 115 92 19 36 107 68 11 20 91 116 59 6 73 102 41 54 121 86 25 46 97 78 1 30 81 126 49 10 69 106 37 58 117 90 21 34 109 66 13 18 93 114 61 3 76 99 44 51 124 83 28 43 100 75 4 27 84 123 52 15 64 111 32 63 112 95 16 39 104 71 8 23 88 119 56 5 74 101 42 53 122 85 26 45 98 77 2 29 82 125 50 9 70 105 38 57 118 89 22 33 110 65 14 17 94 113 62

[入力例]
10 7

[出力例]
Yes
0 575 768 319 384 959 640 191 192 767 960 511 320 895 576 127 160 671 928 415 288 799 544 31 96 607 864 351 480 991 736 223 48 527 816 271 432 911 688 143 240 719 1008 463 368 847 624 79 144 687 912 431 272 815 528 47 80 623 848 367 464 1007 720 239 24 551 792 295 408 935 664 167 216 743 984 487 344 871 600 103 184 647 952 391 312 775 568 7 120 583 888 327 504 967 760 199 40 535 808 279 424 919 680 151 232 727 1000 471 360 855 616 87 136 695 904 439 264 823 520 55 72 631 840 375 456 1015 712 247 12 563 780 307 396 947 652 179 204 755 972 499 332 883 588 115 172 659 940 403 300 787 556 19 108 595 876 339 492 979 748 211 60 515 828 259 444 899 700 131 252 707 1020 451 380 835 636 67 156 675 924 419 284 803 540 35 92 611 860 355 476 995 732 227 20 555 788 299 404 939 660 171 212 747 980 491 340 875 596 107 180 651 948 395 308 779 564 11 116 587 884 331 500 971 756 203 36 539 804 283 420 923 676 155 228 731 996 475 356 859 612 91 132 699 900 443 260 827 516 59 68 635 836 379 452 1019 708 251 6 569 774 313 390 953 646 185 198 761 966 505 326 889 582 121 166 665 934 409 294 793 550 25 102 601 870 345 486 985 742 217 54 521 822 265 438 905 694 137 246 713 1014 457 374 841 630 73 150 681 918 425 278 809 534 41 86 617 854 361 470 1001 726 233 30 545 798 289 414 929 670 161 222 737 990 481 350 865 606 97 190 641 958 385 318 769 574 1 126 577 894 321 510 961 766 193 46 529 814 273 430 913 686 145 238 721 1006 465 366 849 622 81 142 689 910 433 270 817 526 49 78 625 846 369 462 1009 718 241 10 565 778 309 394 949 650 181 202 757 970 501 330 885 586 117 170 661 938 405 298 789 554 21 106 597 874 341 490 981 746 213 58 517 826 261 442 901 698 133 250 709 1018 453 378 837 634 69 154 677 922 421 282 805 538 37 90 613 858 357 474 997 730 229 18 557 786 301 402 941 658 173 210 749 978 493 338 877 594 109 178 653 946 397 306 781 562 13 114 589 882 333 498 973 754 205 34 541 802 285 418 925 674 157 226 733 994 477 354 861 610 93 130 701 898 445 258 829 514 61 66 637 834 381 450 1021 706 253 3 572 771 316 387 956 643 188 195 764 963 508 323 892 579 124 163 668 931 412 291 796 547 28 99 604 867 348 483 988 739 220 51 524 819 268 435 908 691 140 243 716 1011 460 371 844 627 76 147 684 915 428 275 812 531 44 83 620 851 364 467 1004 723 236 27 548 795 292 411 932 667 164 219 740 987 484 347 868 603 100 187 644 955 388 315 772 571 4 123 580 891 324 507 964 763 196 43 532 811 276 427 916 683 148 235 724 1003 468 363 852 619 84 139 692 907 436 267 820 523 52 75 628 843 372 459 1012 715 244 15 560 783 304 399 944 655 176 207 752 975 496 335 880 591 112 175 656 943 400 303 784 559 16 111 592 879 336 495 976 751 208 63 512 831 256 447 896 703 128 255 704 1023 448 383 832 639 64 159 672 927 416 287 800 543 32 95 608 863 352 479 992 735 224 23 552 791 296 407 936 663 168 215 744 983 488 343 872 599 104 183 648 951 392 311 776 567 8 119 584 887 328 503 968 759 200 39 536 807 280 423 920 679 152 231 728 999 472 359 856 615 88 135 696 903 440 263 824 519 56 71 632 839 376 455 1016 711 248 5 570 773 314 389 954 645 186 197 762 965 506 325 890 581 122 165 666 933 410 293 794 549 26 101 602 869 346 485 986 741 218 53 522 821 266 437 906 693 138 245 714 1013 458 373 842 629 74 149 682 917 426 277 810 533 42 85 618 853 362 469 1002 725 234 29 546 797 290 413 930 669 162 221 738 989 482 349 866 605 98 189 642 957 386 317 770 573 2 125 578 893 322 509 962 765 194 45 530 813 274 429 914 685 146 237 722 1005 466 365 850 621 82 141 690 909 434 269 818 525 50 77 626 845 370 461 1010 717 242 9 566 777 310 393 950 649 182 201 758 969 502 329 886 585 118 169 662 937 406 297 790 553 22 105 598 873 342 489 982 745 214 57 518 825 262 441 902 697 134 249 710 1017 454 377 838 633 70 153 678 921 422 281 806 537 38 89 614 857 358 473 998 729 230 17 558 785 302 401 942 657 174 209 750 977 494 337 878 593 110 177 654 945 398 305 782 561 14 113 590 881 334 497 974 753 206 33 542 801 286 417 926 673 158 225 734 993 478 353 862 609 94 129 702 897 446 257 830 513 62 65 638 833 382 449 1022 705 254

[入力例]

3 1

[出力例]

Yes

0 1 3 2 6 7 5 4

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

5 3

[出力例]

Yes

0 19 24 11 12 31 20 7 10 25 18 1 6 21 30 13 3 16 27 8 15 28 23 4 9 26 17 2 5 22 29 14

[入力例]

5 4

[出力例]

[入力例]

7 5

[出力例]

Yes

0 79 96 47 48 127 80 31 40 103 72 7 24 87 120 55 12 67 108 35 60 115 92 19 36 107 68 11 20 91 116 59 6 73 102 41 54 121 86 25 46 97 78 1 30 81 126 49 10 69 106 37 58 117 90 21 34 109 66 13 18 93 114 61 3 76 99 44 51 124 83 28 43 100 75 4 27 84 123 52 15 64 111 32 63 112 95 16 39 104 71 8 23 88 119 56 5 74 101 42 53 122 85 26 45 98 77 2 29 82 125 50 9 70 105 38 57 118 89 22 33 110 65 14 17 94 113 62

[入力例]

10 7

[出力例]

Yes

0 575 768 319 384 959 640 191 192 767 960 511 320 895 576 127 160 671 928 415 288 799 544 31 96 607 864 351 480 991 736 223 48 527 816 271 432 911 688 143 240 719 1008 463 368 847 624 79 144 687 912 431 272 815 528 47 80 623 848 367 464 1007 720 239 24 551 792 295 408 935 664 167 216 743 984 487 344 871 600 103 184 647 952 391 312 775 568 7 120 583 888 327 504 967 760 199 40 535 808 279 424 919 680 151 232 727 1000 471 360 855 616 87 136 695 904 439 264 823 520 55 72 631 840 375 456 1015 712 247 12 563 780 307 396 947 652 179 204 755 972 499 332 883 588 115 172 659 940 403 300 787 556 19 108 595 876 339 492 979 748 211 60 515 828 259 444 899 700 131 252 707 1020 451 380 835 636 67 156 675 924 419 284 803 540 35 92 611 860 355 476 995 732 227 20 555 788 299 404 939 660 171 212 747 980 491 340 875 596 107 180 651 948 395 308 779 564 11 116 587 884 331 500 971 756 203 36 539 804 283 420 923 676 155 228 731 996 475 356 859 612 91 132 699 900 443 260 827 516 59 68 635 836 379 452 1019 708 251 6 569 774 313 390 953 646 185 198 761 966 505 326 889 582 121 166 665 934 409 294 793 550 25 102 601 870 345 486 985 742 217 54 521 822 265 438 905 694 137 246 713 1014 457 374 841 630 73 150 681 918 425 278 809 534 41 86 617 854 361 470 1001 726 233 30 545 798 289 414 929 670 161 222 737 990 481 350 865 606 97 190 641 958 385 318 769 574 1 126 577 894 321 510 961 766 193 46 529 814 273 430 913 686 145 238 721 1006 465 366 849 622 81 142 689 910 433 270 817 526 49 78 625 846 369 462 1009 718 241 10 565 778 309 394 949 650 181 202 757 970 501 330 885 586 117 170 661 938 405 298 789 554 21 106 597 874 341 490 981 746 213 58 517 826 261 442 901 698 133 250 709 1018 453 378 837 634 69 154 677 922 421 282 805 538 37 90 613 858 357 474 997 730 229 18 557 786 301 402 941 658 173 210 749 978 493 338 877 594 109 178 653 946 397 306 781 562 13 114 589 882 333 498 973 754 205 34 541 802 285 418 925 674 157 226 733 994 477 354 861 610 93 130 701 898 445 258 829 514 61 66 637 834 381 450 1021 706 253 3 572 771 316 387 956 643 188 195 764 963 508 323 892 579 124 163 668 931 412 291 796 547 28 99 604 867 348 483 988 739 220 51 524 819 268 435 908 691 140 243 716 1011 460 371 844 627 76 147 684 915 428 275 812 531 44 83 620 851 364 467 1004 723 236 27 548 795 292 411 932 667 164 219 740 987 484 347 868 603 100 187 644 955 388 315 772 571 4 123 580 891 324 507 964 763 196 43 532 811 276 427 916 683 148 235 724 1003 468 363 852 619 84 139 692 907 436 267 820 523 52 75 628 843 372 459 1012 715 244 15 560 783 304 399 944 655 176 207 752 975 496 335 880 591 112 175 656 943 400 303 784 559 16 111 592 879 336 495 976 751 208 63 512 831 256 447 896 703 128 255 704 1023 448 383 832 639 64 159 672 927 416 287 800 543 32 95 608 863 352 479 992 735 224 23 552 791 296 407 936 663 168 215 744 983 488 343 872 599 104 183 648 951 392 311 776 567 8 119 584 887 328 503 968 759 200 39 536 807 280 423 920 679 152 231 728 999 472 359 856 615 88 135 696 903 440 263 824 519 56 71 632 839 376 455 1016 711 248 5 570 773 314 389 954 645 186 197 762 965 506 325 890 581 122 165 666 933 410 293 794 549 26 101 602 869 346 485 986 741 218 53 522 821 266 437 906 693 138 245 714 1013 458 373 842 629 74 149 682 917 426 277 810 533 42 85 618 853 362 469 1002 725 234 29 546 797 290 413 930 669 162 221 738 989 482 349 866 605 98 189 642 957 386 317 770 573 2 125 578 893 322 509 962 765 194 45 530 813 274 429 914 685 146 237 722 1005 466 365 850 621 82 141 690 909 434 269 818 525 50 77 626 845 370 461 1010 717 242 9 566 777 310 393 950 649 182 201 758 969 502 329 886 585 118 169 662 937 406 297 790 553 22 105 598 873 342 489 982 745 214 57 518 825 262 441 902 697 134 249 710 1017 454 377 838 633 70 153 678 921 422 281 806 537 38 89 614 857 358 473 998 729 230 17 558 785 302 401 942 657 174 209 750 977 494 337 878 593 110 177 654 945 398 305 782 561 14 113 590 881 334 497 974 753 206 33 542 801 286 417 926 673 158 225 734 993 478 353 862 609 94 129 702 897 446 257 830 513 62 65 638 833 382 449 1022 705 254

■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)

C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題D (Differ by K bits) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題D (Differ by K bits) を解いてみた.

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