C++の練習を兼ねて, AtCoder Grand Contest 013 の 問題A (Sorted Arrays) ~ 問題B (Hamiltonish Path) を解いてみた.
■感想.
1. 問題A は, 規則性が見つかったので, AC版に到達できたと思う.
2. 問題B は, 解答の方針が絞り込めなかったので, 解説を参照して, 実装したところ, AC版に到達できたので良かったと思う.
3. 個人的には, 問題B は, dequeの復習も出来て, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 013 解説 を ご覧下さい.
■C++版プログラム(問題A/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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int a[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); a[N] = a[N - 1]; // 番兵. // 2. 区切りの数をカウント. int ans = 1, bef = a[0], cur, f = 0; repx(i, 1, N + 1){ // 2-1. 今回分更新. cur = a[i]; // 2-2. f が 0 の 場合. if(f == 0){ if(cur > bef) f = 1; // 増加. if(cur < bef) f = 2; // 減少. // 前回分更新. bef = cur; // 次処理. continue; } // 2-3. 増加から減少に転じた場合. if(f == 1 && cur < bef) f = 0, ans++; // 2-4. 減少から増加に転じた場合. if(f == 2 && cur > bef) f = 0, ans++; // 2-5. 前回分更新. bef = cur; } // 3. 出力. printf("%d\n", ans); 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 |
[入力例] 6 1 2 3 2 2 1 [出力例] 2 ※AtCoderテストケースより [入力例] 9 1 2 1 2 1 2 1 2 1 [出力例] 5 ※AtCoderテストケースより [入力例] 7 1 2 3 2 1 999999999 1000000000 [出力例] 3 ※AtCoderテストケースより [入力例] 50 95 47 108 58 107 17 98 48 115 111 106 66 18 36 52 92 78 2 1 113 74 111 88 43 22 48 2 79 75 45 27 50 25 90 68 61 120 10 78 118 70 44 31 41 69 12 105 56 72 23 [出力例] 20 [入力例] 1200 99 828 1157 887 961 227 791 1021 749 417 1083 1220 220 414 514 589 885 397 904 804 1160 1109 827 897 166 741 571 1172 1213 579 514 1136 149 949 805 614 127 1140 390 482 1030 933 356 410 1034 1163 174 828 863 294 26 169 884 1073 247 164 771 841 74 1170 843 721 954 218 823 503 722 580 541 88 401 310 1169 665 1232 123 459 156 496 1031 1089 354 866 1076 790 53 156 1209 640 996 958 112 433 519 1203 125 132 789 85 457 210 183 61 295 611 1062 216 393 184 197 526 988 900 453 131 156 298 844 266 367 856 137 988 677 781 1041 1104 668 495 338 492 730 1137 938 554 786 373 459 1068 943 633 143 16 301 756 1116 905 380 1206 135 688 619 280 331 641 770 673 177 901 146 638 435 1223 86 1174 801 850 1088 864 139 863 458 244 1126 1016 449 16 532 526 797 1149 467 635 57 860 327 999 1089 402 1093 467 386 788 841 790 117 319 609 43 530 1001 1067 327 1222 896 226 814 673 696 303 1201 454 1046 89 1004 1087 560 124 786 863 539 180 363 158 1040 1210 630 359 29 1189 568 367 852 762 590 605 32 350 143 30 753 741 200 997 700 552 1124 259 465 470 431 193 216 453 570 1198 1178 955 1085 604 1065 556 307 409 364 975 347 55 863 18 799 815 807 767 180 165 492 1006 1028 976 592 518 591 1135 318 633 228 1170 1163 523 744 183 95 640 928 133 184 397 153 961 822 781 1012 41 568 979 1054 155 246 110 979 504 824 93 401 5 352 170 1091 912 510 51 623 531 249 748 985 991 534 430 975 135 406 190 72 840 202 1052 661 324 506 526 437 96 96 511 711 590 402 742 331 823 467 413 247 746 779 721 1180 710 1155 327 107 739 1074 1175 1098 1037 802 133 708 136 396 760 211 855 738 469 288 856 510 282 1173 681 1017 571 269 431 294 695 1090 1039 1004 178 1231 7 2 968 1122 629 1054 863 1049 692 324 1203 53 1098 523 208 199 1053 689 1109 123 733 412 317 105 967 803 722 394 745 1110 1087 118 880 1053 1125 158 398 453 600 294 1015 915 387 15 770 710 1187 81 104 258 252 108 1096 1187 248 222 321 498 530 1091 947 833 683 727 40 140 986 1222 351 1201 756 66 578 1230 302 1174 208 522 616 69 112 1017 198 893 692 1155 838 764 451 98 520 829 452 22 654 849 427 485 279 742 598 924 756 48 1004 455 314 836 1207 963 614 676 653 1005 1112 805 342 657 26 565 685 80 1015 729 1136 1087 44 51 1128 903 222 476 433 1076 5 1224 1099 5 570 905 675 546 228 951 746 481 937 654 353 103 987 1057 346 1179 66 138 603 597 278 1014 991 39 573 1213 290 503 501 383 61 429 1117 1228 483 718 1150 1179 354 1098 355 448 29 651 278 1222 1197 1194 980 849 340 1190 954 1008 1128 851 487 783 111 798 593 66 1136 183 967 377 740 1185 1121 778 662 773 998 157 1026 475 671 139 1143 767 374 130 467 56 178 896 728 885 697 1050 696 311 854 814 606 792 1120 493 61 29 574 1024 582 530 4 454 439 1160 183 686 1182 254 598 586 495 1168 730 975 649 530 665 685 1044 474 722 1174 790 113 949 372 1074 777 724 1148 245 122 259 588 300 511 368 254 627 80 337 736 392 155 342 719 434 1212 181 368 1075 655 575 133 50 94 1152 250 566 1233 657 458 342 390 938 22 429 767 505 78 1147 423 388 738 17 354 810 844 1207 971 735 371 924 1125 173 340 1082 97 1085 1128 449 747 1167 257 76 766 288 940 1004 600 326 445 1156 990 1167 720 677 962 1227 538 909 1176 216 595 1140 63 324 528 1051 845 829 284 837 778 1024 611 909 1029 577 779 347 655 1174 839 582 1137 230 1205 53 805 858 1201 1107 442 810 988 490 132 5 304 1063 505 918 393 1010 537 1038 246 4 883 178 608 458 137 834 727 953 570 407 277 39 65 549 86 841 964 993 151 276 934 994 750 1171 727 529 1185 1086 1116 1215 808 941 451 141 828 1057 387 277 1204 362 105 61 104 26 1151 143 32 957 128 1105 938 368 492 968 1182 608 651 677 545 586 1174 965 399 178 440 1180 1176 130 954 1133 1203 578 1151 966 312 139 391 69 553 1219 901 139 244 800 371 215 50 369 1191 695 1 973 1045 826 494 443 844 1204 344 943 436 234 869 874 566 1077 96 605 618 579 361 1029 278 232 665 949 366 911 1208 528 537 1039 276 232 4 677 1039 214 311 914 659 63 681 88 149 861 533 404 981 1117 1094 1141 968 226 568 973 181 319 1206 45 248 22 904 1039 913 165 982 193 399 219 1233 542 700 845 868 1166 840 883 982 397 282 162 418 1153 139 239 131 840 1234 882 283 52 1204 1172 968 1157 125 1195 952 1206 1134 1148 1074 1206 551 1187 143 208 29 960 593 752 571 216 431 67 880 607 647 631 722 245 690 1045 526 856 283 323 1133 110 534 294 1214 1007 401 11 960 46 1065 509 1010 160 772 13 411 879 276 1224 1224 122 824 935 362 1048 588 958 112 381 381 525 989 301 881 1226 136 1162 273 594 89 835 52 963 1169 632 799 926 691 724 141 11 38 75 84 1185 542 1232 527 369 1190 472 95 117 743 486 555 1225 426 1122 66 558 897 527 776 82 914 361 111 236 1067 490 683 56 345 49 1210 672 460 608 938 344 905 443 889 249 250 465 128 685 428 1194 204 1142 117 768 806 300 55 926 899 498 228 841 94 610 104 63 833 929 854 499 655 235 72 1061 365 258 264 260 1105 558 983 984 543 715 294 464 709 10 1078 630 518 920 459 1119 859 339 1196 418 816 1149 104 123 889 46 51 1193 606 51 811 808 531 568 1128 1154 950 245 466 255 689 740 572 156 178 1141 721 486 1155 963 170 1187 721 855 104 947 [出力例] 500 |
■C++版プログラム(問題B/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 |
// 解き直し. // https://img.atcoder.jp/agc013/editorial.pdf // 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--) #define pf push_front #define pb push_back int main(){ // 1. 入力情報. int N, M, a, b; scanf("%d %d", &N, &M); vvi G(N); deque<int> dq; int used[101010]; memset(used, 0, sizeof(used)); int s = -1, g = -1; rep(i, M){ scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); if(s == -1) s = a, dq.pf(a), used[a] = 1; // A地点. if(g == -1) g = b, dq.pb(b), used[b] = 1; // B地点. } // パスを伸ばしていく(解説通り). // 2. A地点側が条件を満たすかチェック. while(1){ // 2-1. 頂点を一つ取得. int a = dq.front(); used[a] = 1; // 2-2. 頂点 a の 隣接頂点 を 調べる. bool ok = true; for(auto &p : G[a]){ // 未訪問の頂点がある場合は, パスに含まれてないので, 訪問. if(!used[p]){ used[p] = 1; dq.pf(p); ok = false; break; } } // 2-3. 終了確認. if(ok) break; } // 3. B地点側が条件を満たすかチェック. while(1){ // 3-1. 頂点を一つ取得. int b = dq.back(); used[b] = 1; // 3-2. 頂点 b の 隣接頂点 を 調べる. bool ok = true; for(auto &p : G[b]){ // 未訪問の頂点がある場合は, パスに含まれてないので, 訪問. if(!used[p]){ used[p] = 1; dq.pb(p); ok = false; break; } } // 3-3. 終了確認. if(ok) break; } // 4. 出力. int l = dq.size(); printf("%d\n", l); rep(i, l){ printf("%d", dq[i] + 1); printf("%s", (i < l - 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 |
[入力例] 5 6 1 3 1 4 2 3 1 5 3 5 2 4 [出力例] 4 2 3 1 4 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 5 2 4 1 3 5 [入力例] 7 8 1 2 2 3 3 4 4 5 5 6 6 7 3 5 2 6 [出力例] 7 1 2 3 4 5 6 7 ※AtCoderテストケースより [入力例] 12 18 3 5 4 12 9 11 1 10 2 5 6 10 8 11 1 3 4 10 2 4 3 7 2 10 3 12 3 9 1 7 2 3 2 11 10 11 [出力例] 8 12 4 2 5 3 9 11 8 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 8 6 10 1 3 5 2 4 12 [入力例] 20 24 1 9 1 10 1 3 9 2 2 17 17 9 17 18 11 12 12 13 13 11 4 5 5 6 6 4 3 14 14 16 16 15 15 3 1 2 17 7 2 7 18 7 7 19 7 20 7 8 [出力例] 8 10 1 9 2 17 18 7 19 |
■参照サイト
AtCoder Grand Contest 013