C++の練習を兼ねて, AtCoder Regular Contest 149 の 問題C (Avoid Prime Sum) を解いてみた.
■感想.
1. 問題Cは, 解法の糸口を見つけることが出来たので, AC版に到達できた.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 149 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #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--) const int MAX = 2 * 1010 * 1010 + 1; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 素数を用意. vi p(MAX); repx(i, 2, MAX){ if(p[i]) continue; repex(j, i * 2, MAX, i) ++p[j]; } // 3. 評価関数. auto f = [&](vvi &a, int n) -> bool { // 3-1. 隣接二マス合計が, 素数ではない. rep(i, n){ rep(j, n){ // 現在地点. int cur = a[i][j]; // 上. if(i && !p[cur + a[i - 1][j]]) return false; // 下. if(i < n - 1 && !p[cur + a[i + 1][j]]) return false; // 左. if(j && !p[cur + a[i][j - 1]]) return false; // 右. if(j < n - 1 && !p[cur + a[i][j + 1]]) return false; } } // 3-2. N * N 以下の正整数が, 一回ずつ出現する. set<int> st; rep(i, n) rep(j, n) st.insert(a[i][j]); if(st.size() != n * n) return false; // 3-3. 制約を満たしている. return true; }; // 4. N = 3 の 場合. vvi ans(N, vi(N, 0)); if(N == 3){ // 1 行目. ans[0][0] = 5; ans[0][1] = 9; ans[0][2] = 1; // 2 行目. ans[1][0] = 3; ans[1][1] = 7; ans[1][2] = 8; // 3 行目. ans[2][0] = 6; ans[2][1] = 2; ans[2][2] = 4; } // 5. N = 5 の 場合. if(N == 5){ // 1 行目. ans[0][0] = 11; ans[0][1] = 13; ans[0][2] = 15; ans[0][3] = 17; ans[0][4] = 19; // 2 行目. ans[1][0] = 21; ans[1][1] = 23; ans[1][2] = 25; ans[1][3] = 3; ans[1][4] = 5; // 3 行目. ans[2][0] = 7; ans[2][1] = 9; ans[2][2] = 1; ans[2][3] = 24; ans[2][4] = 10; // 4 行目. ans[3][0] = 8; ans[3][1] = 6; ans[3][2] = 14; ans[3][3] = 2; ans[3][4] = 4; // 5 行目. ans[4][0] = 12; ans[4][1] = 16; ans[4][2] = 18; ans[4][3] = 20; ans[4][4] = 22; } // 6. N が 偶数. if(!(N & 1)){ int n = 0; set<int> e; rep(i, N * N) if(i & 1) e.insert(i + 1); // 1 と 隣接しても, 素数にならない偶数は？ repex(i, 2 * N, N * N + 1, 2){ if(p[i + 1]){ n = i + 1; break; } } // 上半分(奇数). int cur = -1; rep(j, N) ans[N / 2 - 1][j] = (++cur) * 2 + 1; rep(i, N / 2 - 1) rep(j, N) ans[i][j] = (++cur) * 2 + 1; // 下半分(偶数). rep(j, N){ ans[N / 2][j] = n - ans[N / 2 - 1][j]; e.erase(ans[N / 2][j]); } repx(i, N / 2 + 1, N){ rep(j, N){ ans[i][j] = *e.begin(); e.erase(ans[i][j]); } } } // 7. N が 5 より大きい奇数. if(N > 5 && (N & 1)){ int n1 = 0, n2 = 0; set<int> e; rep(i, N * N) if(i & 1) e.insert(i + 1); // 1, 3 と 隣接しても, 素数にならない偶数は？ repex(i, 2, N * N + 1, 2){ if(p[i + 1] && p[i + 3]){ n1 = i; break; } } // (n1 + 2 * N) 以上 で, 5 と 隣接しても, 素数にならない偶数は？ repex(i, n1 + 2 * N, N * N + 1, 2){ if(p[i + 5]){ n2 = i + 5; break; } } // 上半分(奇数). int cur = -1; ans[N / 2][N / 2] = (++cur) * 2 + 1; repx(j, N / 2 + 1, N) ans[N / 2 - 1][j] = (++cur) * 2 + 1; rep(j, N / 2) ans[N / 2][j] = (++cur) * 2 + 1; rep(i, N / 2 - 1) rep(j, N) ans[i][j] = (++cur) * 2 + 1; rep(j, N / 2 + 1) ans[N / 2 - 1][j] = (++cur) * 2 + 1; // 下半分(偶数). ans[N / 2][N / 2 + 1] = n1; e.erase(ans[N / 2][N / 2 + 1]); repx(j, N / 2 + 2, N){ ans[N / 2][j] = n2 - ans[N / 2 - 1][j]; e.erase(ans[N / 2][j]); } rep(j, N){ ans[N / 2 + 1][j] = (j <= N / 2) ? (n2 - ans[N / 2][j]) : *e.begin(); e.erase(ans[N / 2 + 1][j]); } repx(i, N / 2 + 2, N){ rep(j, N){ ans[i][j] = *e.begin(); e.erase(ans[i][j]); } } } // 8. 制約チェック. assert(f(ans, N)); // 9. 出力. rep(i, N) rep(j, N) printf("%d%s", ans[i][j], (j < 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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
[入力例] 4 [出力例] 15 11 16 12 13 3 6 9 14 7 8 1 4 2 10 5 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 9 11 13 15 1 3 5 7 8 6 4 2 10 12 14 16 [入力例] 3 [出力例] 5 9 1 3 7 8 6 2 4 [入力例] 5 [出力例] 11 13 15 17 19 21 23 25 3 5 7 9 1 24 10 8 6 14 2 4 12 16 18 20 22 [入力例] 6 [出力例] 13 15 17 19 21 23 25 27 29 31 33 35 1 3 5 7 9 11 14 12 10 8 6 4 2 16 18 20 22 24 26 28 30 32 34 36 [入力例] 7 [出力例] 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 3 5 7 9 11 13 1 24 40 38 36 34 32 44 2 4 6 8 10 12 14 16 18 20 22 26 28 30 42 46 48 [入力例] 10 [出力例] 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 1 3 5 7 9 11 13 15 17 19 20 18 16 14 12 10 8 6 4 2 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 [入力例] 33 [出力例] 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197 199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 303 305 307 309 311 313 315 317 319 321 323 325 327 329 331 333 335 337 339 341 343 345 347 349 351 353 355 357 359 361 363 365 367 369 371 373 375 377 379 381 383 385 387 389 391 393 395 397 399 401 403 405 407 409 411 413 415 417 419 421 423 425 427 429 431 433 435 437 439 441 443 445 447 449 451 453 455 457 459 461 463 465 467 469 471 473 475 477 479 481 483 485 487 489 491 493 495 497 499 501 503 505 507 509 511 513 515 517 519 521 523 525 527 529 531 533 535 537 539 541 543 545 547 549 551 553 555 557 559 561 563 565 567 569 571 573 575 577 579 581 583 585 587 589 591 593 595 597 599 601 603 605 607 609 611 613 615 617 619 621 623 625 627 629 631 633 635 637 639 641 643 645 647 649 651 653 655 657 659 661 663 665 667 669 671 673 675 677 679 681 683 685 687 689 691 693 695 697 699 701 703 705 707 709 711 713 715 717 719 721 723 725 727 729 731 733 735 737 739 741 743 745 747 749 751 753 755 757 759 761 763 765 767 769 771 773 775 777 779 781 783 785 787 789 791 793 795 797 799 801 803 805 807 809 811 813 815 817 819 821 823 825 827 829 831 833 835 837 839 841 843 845 847 849 851 853 855 857 859 861 863 865 867 869 871 873 875 877 879 881 883 885 887 889 891 893 895 897 899 901 903 905 907 909 911 913 915 917 919 921 923 925 927 929 931 933 935 937 939 941 943 945 947 949 951 953 955 957 959 961 963 965 967 969 971 973 975 977 979 981 983 985 987 989 991 993 995 997 999 1001 1003 1005 1007 1009 1011 1013 1015 1017 1019 1021 1023 1025 1027 1029 1031 1033 1035 1037 1039 1041 1043 1045 1047 1049 1051 1053 1055 1057 1059 1061 1063 1065 1067 1069 1071 1073 1075 1077 1079 1081 1083 1085 1087 1089 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 1 24 90 88 86 84 82 80 78 76 74 72 70 68 66 64 62 60 58 56 54 52 50 48 46 44 42 40 38 36 34 32 30 94 2 4 6 8 10 12 14 16 18 20 22 26 28 92 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 178 180 182 184 186 188 190 192 194 196 198 200 202 204 206 208 210 212 214 216 218 220 222 224 226 228 230 232 234 236 238 240 242 244 246 248 250 252 254 256 258 260 262 264 266 268 270 272 274 276 278 280 282 284 286 288 290 292 294 296 298 300 302 304 306 308 310 312 314 316 318 320 322 324 326 328 330 332 334 336 338 340 342 344 346 348 350 352 354 356 358 360 362 364 366 368 370 372 374 376 378 380 382 384 386 388 390 392 394 396 398 400 402 404 406 408 410 412 414 416 418 420 422 424 426 428 430 432 434 436 438 440 442 444 446 448 450 452 454 456 458 460 462 464 466 468 470 472 474 476 478 480 482 484 486 488 490 492 494 496 498 500 502 504 506 508 510 512 514 516 518 520 522 524 526 528 530 532 534 536 538 540 542 544 546 548 550 552 554 556 558 560 562 564 566 568 570 572 574 576 578 580 582 584 586 588 590 592 594 596 598 600 602 604 606 608 610 612 614 616 618 620 622 624 626 628 630 632 634 636 638 640 642 644 646 648 650 652 654 656 658 660 662 664 666 668 670 672 674 676 678 680 682 684 686 688 690 692 694 696 698 700 702 704 706 708 710 712 714 716 718 720 722 724 726 728 730 732 734 736 738 740 742 744 746 748 750 752 754 756 758 760 762 764 766 768 770 772 774 776 778 780 782 784 786 788 790 792 794 796 798 800 802 804 806 808 810 812 814 816 818 820 822 824 826 828 830 832 834 836 838 840 842 844 846 848 850 852 854 856 858 860 862 864 866 868 870 872 874 876 878 880 882 884 886 888 890 892 894 896 898 900 902 904 906 908 910 912 914 916 918 920 922 924 926 928 930 932 934 936 938 940 942 944 946 948 950 952 954 956 958 960 962 964 966 968 970 972 974 976 978 980 982 984 986 988 990 992 994 996 998 1000 1002 1004 1006 1008 1010 1012 1014 1016 1018 1020 1022 1024 1026 1028 1030 1032 1034 1036 1038 1040 1042 1044 1046 1048 1050 1052 1054 1056 1058 1060 1062 1064 1066 1068 1070 1072 1074 1076 1078 1080 1082 1084 1086 1088 |
■参照サイト
AtCoder Regular Contest 149