C++の練習を兼ねて, AtCoder Beginner Contest 281 の 問題F (Xor Minimization) を解いてみた.
■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 問題F で, 再帰処理 の 訓練が積めたので, 非常に, 良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 281 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc281/editorial/5367 // 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; scanf("%d", &N); vi a(N); rep(i, N) scanf("%d", &a[i]); // 2. dfs. // https://ja.wikipedia.org/wiki/深さ優先探索 auto dfs = [&](auto&& self, int m, vi& ca, int d) -> int { // 終了条件. if(!ca.size() || d == -1) return m; // d 桁目. vi s, t; for(auto &p : ca){ if(p & (1 << d)) t.pb(p); else s.pb(p); } // 集合 S が 空(d 桁目は, 0). if(!s.size()) return self(self, m, t, d - 1); // 集合 T が 空(d 桁目は, 0). if(!t.size()) return self(self, m, s, d - 1); // 集合 S, T が 空でない(d 桁目は, 1). return min(self(self, m + (1 << d), t, d - 1), self(self, m + (1 << d), s, d - 1)); }; // 3. 出力. printf("%d\n", dfs(dfs, 0, a, 30)); 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 |
[入力例] 3 12 18 11 [出力例] 16 ※AtCoderテストケースより [入力例] 10 0 0 0 0 0 0 0 0 0 0 [出力例] 0 ※AtCoderテストケースより [入力例] 5 324097321 555675086 304655177 991244276 9980291 [出力例] 805306368 ※AtCoderテストケースより [入力例] 5 10 7 3 13 2 [出力例] 12 [入力例] 8 10 9 13 15 4 3 8 5 [出力例] 12 [入力例] 10 70 61 15 88 105 18 33 121 36 79 [出力例] 112 [入力例] 50 6891 6298 5053 6323 6042 6655 5783 5991 7339 5310 7118 5565 5284 7006 6330 5662 5076 7133 6397 6750 6200 6016 5993 5313 5955 7260 6804 5918 6068 5399 5714 5000 6160 6415 6138 6541 6179 7152 6255 6404 5134 6886 5828 6079 5763 5596 5740 7161 5294 6549 [出力例] 3136 [入力例] 1000 983416 585352 1514003 1368537 628064 911914 852445 982631 1693264 1361091 737487 785615 781739 1185733 931554 1260586 563653 1285736 980567 1276610 542170 1077277 1114263 728838 616468 562931 1725756 1634694 672414 1060936 1292963 1177298 755917 1594473 707707 910290 948009 1325922 1221078 1479813 1294760 1172099 1641627 872866 1072574 1473997 1076895 1034100 744153 1262289 1533736 1324906 1038768 778896 1710597 1237965 855432 1488449 749075 825760 1081769 1727737 1143983 924439 908693 919781 1431951 741219 1076844 910410 879026 1183673 1392139 1477801 1328296 608659 1698782 733672 1591460 1609047 1700774 1673479 663875 910323 961351 898437 1290098 943939 570831 1519890 1510777 574038 1202544 822785 1678814 963797 1353459 608025 740323 1197190 1066108 1041366 1346662 759977 742769 1003010 1212186 691366 1487334 1207565 1623128 592368 1333753 808206 1147178 582467 1549749 1249085 1106388 1014022 1490996 719387 1687600 908056 966861 691388 853561 1436926 1357853 776927 1650304 627724 724605 1472979 878040 1729693 1567007 646237 522055 1003464 775690 917899 1634841 874818 793981 1128783 984634 1602266 1611244 1446130 1334701 1146127 761298 1114100 1709548 1154834 1399373 1344416 1098500 906520 916937 1452298 558143 1275907 1384928 1282163 940375 1393104 1119685 1708259 1091628 1649039 1421195 712586 1215532 1294831 981186 1203012 1710922 918264 1043072 1062496 1553728 1707387 1679920 932616 1527549 934318 502752 948819 614657 1722344 1143717 1410262 1309428 977796 1000454 900387 630260 715472 841628 523619 591036 1447406 1505193 680814 1595274 577501 1264036 1408642 1731624 881817 1113097 620604 1675387 1498398 1541302 610660 1281241 1568924 917296 1339673 1506762 1027640 1276060 625298 993041 1250344 1570929 926371 1339385 1027619 572102 792486 1721781 1180346 523433 1327957 501425 1674301 1594504 1052839 886843 1176682 1379631 599408 567522 1475706 977058 871550 834591 1524172 1074068 831014 1062927 842688 1458822 999255 515184 1581908 1147764 1001192 1587982 1148463 1219656 1187186 1255179 1724131 636036 609462 756729 913071 1242734 977876 1689974 885843 1417044 1272653 610327 765544 1207198 1065033 1273496 1500218 1258206 1166552 693238 707318 990762 1102785 589450 1024800 1390004 794298 1135495 1705148 1672313 896231 1010256 1013690 844637 1606162 1019861 1070515 1280961 932971 705239 1116011 1210134 603795 1569111 1031562 1313016 972400 981734 721353 1635394 1280633 904305 903156 945272 635857 1716128 1394821 1392790 835131 1615934 1484725 1037344 550375 1265608 1546394 1629639 1323872 1624597 1510289 1129836 1715819 882041 1648866 1315204 617024 1256136 1252701 855799 1009486 1260492 1717634 1579134 659884 535675 939980 1429725 1717878 558554 1453666 1666314 1181581 1457079 1652944 873479 1425264 1690676 848435 861744 1544194 994752 571427 1206999 1456648 1126576 1266595 1220349 935434 1351714 1485038 843940 1609479 1154589 604605 1078542 527303 1208152 1297267 1004356 1515926 663932 1464629 1622408 1353081 1686717 1272569 553734 1556424 1516071 1077974 1419726 1253948 1148411 1338586 1146172 1241036 1459069 1205731 627951 716508 723100 1314254 994886 1282887 1705678 1393108 1712077 1400576 923026 547291 1308835 923502 663368 1016911 1607411 1281784 510744 1281018 542960 1070778 921364 1606321 1703870 1249787 1564831 1360999 1344476 1488401 1201755 950602 1731818 504664 953870 793182 1172900 1582618 728804 1145571 1273063 919016 1047802 1342517 683145 602870 1648276 1622501 1380991 1693277 1559236 560074 1141852 1133747 854384 1402464 1080471 1703957 1668638 644370 1204166 714414 1358206 1027715 1203036 946434 846699 1664249 1042485 1716155 1725165 1220274 1713856 873869 1046990 1624218 776288 973149 1366109 675323 654288 1188632 976038 561180 1338607 1363684 1502732 1031369 1384732 815055 580376 1374545 1571458 1395377 1170260 1070661 694816 683679 561746 1470475 1281386 1147188 1276962 815414 1179335 1361202 1388800 1054392 1564174 1111506 987868 1503420 1711851 1507373 1425868 1641098 570810 1373541 1211831 511029 972173 610840 1346426 1714863 1251497 1198761 1259705 1205714 1689021 1364924 960307 563469 1586400 1049348 1185988 1100514 902613 1610018 1602541 871195 1150976 977318 1605422 919835 1447884 1363822 596255 978564 1401498 1461780 1151317 1034731 1073149 1246885 937200 1704507 803548 1049859 831794 1469033 1211419 678577 1140500 1722756 1576530 590983 1211337 649674 1304078 846537 1279153 1353718 1040815 1683899 584310 971484 550199 1159031 1621576 997678 1507425 1314612 979439 1031653 995345 1030310 800904 595315 1048013 758614 1235269 836843 1455995 880259 755557 1033347 1124065 561549 903641 1609012 520943 847622 1240910 670344 1314795 1303247 596642 1177203 1417615 1385613 1694898 721874 1546623 864539 1655304 842597 1371664 1269623 1080602 1672786 1354552 1370997 831302 1657300 1198714 819853 823261 1671340 1135290 1023759 1353563 1111549 654563 1219736 1481001 637716 521269 980577 596608 1692666 914248 1518911 993073 1120947 692604 1210341 1456407 725654 711496 1509963 788303 1636970 1693739 1410562 1578090 1607691 945239 524358 721613 639157 570785 798624 1139665 1041143 1343836 1402657 831744 876759 1307704 533915 1330382 1638454 1014884 763066 921486 1002392 1426872 901227 843700 855913 841840 1162783 1439559 502946 795389 1439145 1403450 1531124 1331720 1079256 1141823 1095810 1622052 1255064 1230648 1206913 879320 1255279 1328814 1362776 1274286 564183 1091989 1163016 1221343 821690 1675341 974480 1085842 528778 1062445 504281 694116 1221562 1642195 646713 1268695 1555056 1527589 622656 1639675 950740 1078952 906810 1170825 1398173 916149 1067253 1136941 1585320 1076647 883699 602136 824728 1246107 644715 1238566 1270928 1322168 950555 879013 1467174 703100 1492807 525589 1451229 536602 1450200 1053052 677285 1591185 756736 1164696 1273902 972771 1269924 591397 1143897 1070464 933373 1311806 1570453 1237401 865829 1157795 1134854 1650980 1397561 1616694 611675 804661 1309608 1569280 550408 1422570 1692747 1727110 1561091 613442 1229872 748854 1098317 894614 1692991 895103 1457213 1454880 841646 598728 906285 1143390 1576522 1662076 1071330 844800 725503 1638394 1373735 1636011 1668504 1303964 1370633 1521229 885664 820561 1350174 1015327 1162501 1199324 512182 543616 824980 837269 1118544 643917 506402 592923 1442628 1681434 747823 875423 534858 1613138 1733817 599331 614533 1461844 971387 1500765 662700 599283 1686085 588158 1725375 804693 843414 844685 1162893 1726029 1353942 970714 1139888 697280 695339 1341836 1437968 1659257 1458117 1703316 1062947 1336929 560650 1561283 1348394 523360 968698 1362091 680834 1246187 1343243 1688697 1517121 660823 1422364 1353592 1216435 1482240 1376711 906090 1705903 523046 1328303 863702 1275263 540667 556225 673730 1567224 546413 1377102 617703 800422 1418411 1719871 857171 1353932 521768 695589 892808 753489 999977 746917 824074 1065473 984510 765495 1082287 1631085 1716669 510416 1285702 1373783 1492096 1423294 867459 1178875 1512610 1255379 1635278 1303548 1065347 703908 1089724 1050720 725155 530081 1677577 879378 637441 1231246 828087 1610890 1469629 1051717 774936 1312291 1540137 850489 597006 1031149 631009 1430909 587877 1122854 1398058 930432 1684843 1038739 1577539 1167758 992667 1397756 1695939 1190678 555017 656652 590666 1561242 548326 1581106 536742 1551651 959458 1689673 1466760 1026859 1193359 1420273 1627861 1094225 708273 766875 1501004 1072155 1311448 608528 1667118 1178100 1583931 873651 967958 589671 684109 1295141 1487741 913334 1395806 1098559 1359309 561207 930174 739629 872796 1188656 1487772 1686236 1145892 1087539 672334 1503400 1377209 1197106 889942 1150368 1545105 1165920 [出力例] 1595392 |
■参照サイト
AtCoder Beginner Contest 281