C++の練習を兼ねて, AtCoder Beginner Contest 163 の 問題E (E – Active Infants) を解いてみた.
■感想.
1. 方針が全く見えなかった(※priority_queueを使う方針では, 駄目だった)ので, 解説を見てから, 実装して, AC版となった.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 163 解説をご覧下さい.
■C++版プログラム(問題E/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 |
// 解き直し. // https://img.atcoder.jp/abc163/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, 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 #define a first #define b second #define all(x) x.begin(), x.end() LL dp[2020][2020]; vector<P> v; // joy, index. int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ LL a; scanf("%lld", &a); v.pb({a, i + 1}); } // 2. sort. sort(all(v), greater<P>()); // 3. 解説通り. // (x + y)人 を 昇順にチェックしていくとのこと. repx(xy, 1, N + 1){ // A[i] * (i - p[i]) を 選択: x人 // A[i] * (p[i] - i) を 選択: y人 rep(x, xy + 1){ // 3-1. x人, y人 を 設定. int y = xy - x; LL hx = 0, hy = 0; // 3-2. (x - 1)人 と y人 から (x + y)人 になる場合. if(x > 0) hx = dp[x - 1][y] + v[xy - 1].a * (LL)(v[xy - 1].b - x); // 3-3. x人 と (y - 1)人 から (x + y)人 になる場合. if(y > 0) hy = dp[x][y - 1] + v[xy - 1].a * (LL)(N + 1 - y - v[xy - 1].b); // 3-4. dp更新. dp[x][y] = max(hx, hy); } } // 4. 最大値. LL ans = 0; rep(i, N + 1) ans = max(ans, dp[i][N - i]); // 5. 出力. printf("%lld\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 38 39 40 41 42 43 44 |
[入力例] 4 1 3 4 2 [出力例] 20 ※AtCoderテストケースより [入力例] 6 5 5 6 1 1 1 [出力例] 58 ※AtCoderテストケースより [入力例] 6 8 6 9 1 2 1 [出力例] 85 ※AtCoderテストケースより [入力例] 1000 70 41 75 38 71 6 14 60 3 74 48 77 102 2 98 75 33 12 102 92 98 77 80 89 107 114 57 36 75 11 37 17 111 26 67 54 69 69 93 34 19 108 104 91 50 105 86 85 54 25 22 52 45 89 92 115 61 96 52 111 29 57 35 116 57 50 52 78 104 10 102 2 26 123 23 18 103 54 103 112 10 122 46 119 66 106 83 25 107 91 68 9 11 95 18 37 2 123 60 74 88 78 43 93 118 109 65 104 106 43 6 84 117 73 87 15 44 2 80 117 97 17 96 15 31 78 100 49 116 45 93 28 113 79 44 81 62 31 75 112 17 60 41 85 91 64 101 35 63 71 24 56 56 103 24 81 23 104 95 95 105 103 74 68 89 114 29 5 61 17 77 60 18 22 52 83 7 57 21 2 105 94 99 96 43 8 63 55 101 13 105 64 102 84 33 117 21 35 102 6 13 40 118 68 111 24 104 19 90 1 8 39 57 65 3 31 94 61 115 73 10 66 45 21 101 87 103 74 11 6 76 10 28 2 121 11 14 4 103 8 31 49 83 114 121 91 105 8 4 15 101 84 53 17 120 2 92 30 51 113 81 55 58 83 20 107 11 110 58 109 55 23 77 6 20 37 13 21 75 72 17 77 70 65 7 93 37 90 91 108 100 102 117 116 50 99 104 60 10 35 108 91 12 72 12 63 102 79 6 114 49 120 66 75 91 65 30 118 36 107 26 88 87 96 9 6 22 104 14 85 112 84 46 20 93 123 75 64 55 37 101 71 76 18 45 24 79 82 69 12 44 6 66 17 65 69 39 116 51 89 52 107 28 95 24 107 82 14 12 4 109 15 15 64 4 99 57 7 43 54 42 29 30 51 34 93 20 97 43 74 90 98 60 32 40 34 120 28 105 79 27 30 123 73 4 107 105 5 83 87 31 23 49 95 83 19 15 32 119 20 97 86 50 56 18 89 114 113 95 79 70 105 61 41 75 117 20 110 48 113 67 14 111 65 6 36 91 31 123 123 44 65 2 22 89 23 55 41 90 98 85 86 66 69 63 15 21 75 24 24 12 32 113 90 22 37 82 100 106 90 61 85 54 28 110 11 50 82 77 117 37 88 86 83 69 87 80 60 46 37 57 93 113 24 97 121 100 92 31 88 33 71 92 6 62 17 113 18 84 35 25 115 114 83 47 49 54 104 105 38 15 10 67 60 53 47 102 66 104 60 59 39 104 46 55 52 119 64 19 84 109 33 83 107 19 5 9 90 18 20 25 120 4 116 37 17 29 63 14 20 87 26 93 7 117 33 43 3 56 17 20 107 102 89 103 22 101 110 114 38 76 27 101 99 38 40 66 55 47 23 36 58 85 19 106 47 58 35 77 47 99 81 36 112 94 66 23 65 4 102 119 72 7 123 77 112 7 27 44 58 47 123 98 29 63 37 23 5 118 48 53 5 86 18 3 16 49 16 27 3 15 5 26 116 41 93 68 96 10 76 5 12 80 102 110 47 53 91 89 55 83 82 56 24 48 121 72 85 26 120 56 123 39 28 7 50 96 44 76 77 26 9 73 34 108 113 51 14 109 95 57 9 19 78 106 20 52 48 2 32 93 29 84 30 50 118 12 52 15 95 96 18 44 27 77 30 59 23 103 2 7 34 19 37 93 53 93 94 68 108 93 89 102 101 53 26 80 59 38 65 36 24 11 39 4 72 48 55 119 10 79 99 116 107 76 122 43 121 22 89 22 24 39 46 55 58 17 97 5 11 72 75 61 54 106 13 76 23 20 54 116 98 32 101 81 38 67 117 27 51 87 93 20 70 40 95 56 116 74 21 57 37 112 26 104 31 45 42 25 25 115 123 88 16 83 119 111 7 12 85 5 121 104 60 48 92 64 110 93 114 4 59 86 18 28 89 75 41 60 52 39 83 85 8 43 74 115 47 50 26 33 106 17 114 22 77 43 118 2 35 111 22 33 5 28 85 67 41 59 73 59 100 117 87 5 36 7 5 18 89 13 38 95 16 101 69 7 70 112 96 5 81 67 79 63 16 112 26 53 24 80 14 56 66 122 119 2 13 102 13 95 56 34 103 54 92 99 22 114 10 38 19 109 89 23 33 119 96 91 118 22 99 95 64 33 32 84 77 114 57 98 40 64 117 9 10 34 13 82 59 21 87 85 103 68 41 114 113 54 98 56 41 35 46 122 67 77 57 110 115 112 70 50 84 89 7 111 48 80 40 77 47 115 34 43 58 108 41 51 44 [出力例] 36116215 [入力例] 100 62348265 95118635 88054189 121268617 106864743 43443412 39089716 90005653 90407480 61727531 10640257 77739370 34308834 41637572 26904411 115837893 76505695 72814009 54022243 47711319 61268030 81181912 68700366 51202991 58630161 39475078 65163030 36017359 68297710 24484888 80071596 20937946 108066614 119344302 74603735 84460903 62061764 5510962 69425324 112771391 119382808 58473923 24060311 46840374 67943003 16480754 93527856 113070388 29569607 40157553 71094181 88543249 59269990 35626451 98694582 38008567 120847955 120411925 121330414 64063181 122991777 32151428 85712702 21751581 31449111 94566545 54499823 68414787 54995847 98738012 77292808 42234394 38135507 69679926 21624428 41860842 21819789 63474564 81735114 110205665 83768177 21756959 1582887 14429454 117149701 80571598 87476072 83505763 112108880 89461233 80063731 76208411 34661572 87190410 39834167 24542553 63945913 71905551 46749037 78809363 [出力例] 374598037940 [入力例] 500 415740821 221850321 41384601 922455619 733988292 10737122 910402593 307466244 744732428 676153329 726496724 324458831 970969966 416407799 583701681 770688808 96899422 964051260 591579151 373255767 932902324 406763003 480043799 471759715 860368894 154854101 291388993 385686584 71324017 69963893 957610363 611713330 291608589 775913934 462565042 145998157 611652762 448539078 762566168 73073636 991501640 257947005 593042486 29618614 77777672 959256024 314773796 630574591 959748996 482888957 788543663 356305640 484108406 263833633 992135754 709563527 274270660 253334073 741376525 164316465 460345409 189434727 871334757 395487842 516502296 533411025 854863158 240098682 947186795 949657526 561904748 608447749 213599658 484030161 386616406 588322273 938333769 951577977 259013040 376472673 77100454 613545045 706541617 605221486 91738873 796660365 881000645 454934725 3781977 511400378 529590051 142020774 780025282 155253712 148092830 853026140 307797097 504713952 323607903 887588976 39535556 771636311 124842284 267528984 879690220 442469323 819298694 196528588 784263881 732671334 399158020 930618068 717205326 108858692 890495554 57655898 470923246 467089973 784879927 816020297 145868362 259749495 533581067 30178956 174799899 576494830 203015853 197017329 613951517 759062291 938895552 401790875 243623371 252867092 118576699 838157568 176932195 480747739 429560255 889153631 761873611 258101971 54983086 623911621 634804533 685642486 754295610 109076553 311418860 344583006 635818079 774357468 91627532 184161489 722900742 743701625 872251338 335280940 897245765 797057216 47032590 836102050 814290555 955450036 908783654 481413968 35594032 651647466 602463602 1483924 554751391 573164310 412941957 991689630 347258135 188392871 626473360 249639482 255155258 27982014 605892203 136179085 517158296 246666573 304210124 806548146 821321826 189019185 602419091 102154730 882383285 733314244 350502525 699353815 657528516 456821438 397620410 102518484 230733386 872764142 134876380 397223490 585829826 729525467 398379349 224372383 257805001 235439937 649151352 125213301 294059302 991320778 99452893 991043349 496064341 401694975 466840048 72669307 954429429 529234342 605148165 118923434 416951209 53775332 158933204 754847171 435600614 63425711 766511783 804649992 689617506 852110064 381314214 691159579 481575026 44298821 874885138 840392862 876798386 836652200 908125443 747221316 896232059 254419136 852980046 382936378 924758300 2317320 82152492 92506390 301097174 837485564 753053927 668126566 687927306 80374655 318228911 926290907 179606807 894725341 574389347 80556524 733598359 775678478 498185043 571636142 621090739 632952737 473659336 547742269 336022000 942710571 859488373 666971270 351520919 222575238 991967494 951779918 904250162 305530293 320898233 312913409 218061846 737017877 227477347 720927596 344101378 532738853 411906764 533454717 425269617 393914681 848112060 489871374 861782610 964184599 201435582 841574587 279337685 396594122 199918093 283979878 928582142 780992132 751487978 455800238 662061870 233254972 565494260 30746813 537423635 725312594 22550639 41457734 519441630 789710141 473423252 52308852 584690557 327121247 535004743 4521896 862343475 687258737 381865349 285728806 216216180 528530882 511656249 32187951 480925897 813995229 970461797 487166876 110231122 359272428 693667848 431823688 988925953 344916935 31548136 888055127 378262109 506990101 403876056 110211587 123241593 287332152 405398141 932416088 2831084 679307570 494279793 601519508 985045492 850057592 164121859 771348766 221122514 221252440 89487737 872701416 38962747 682837375 700224277 565816651 350343660 668562332 51169872 557317108 787788957 855058406 68662346 962946226 401223596 387749420 593318697 703905727 386756033 169222307 494062948 6739882 533350369 821311769 227242678 828832150 843957695 826520930 765482387 619940308 794607917 429420661 135527293 489713085 387670092 498313800 447435567 991809892 560793490 682223712 599172061 212701192 835266036 951933349 612423230 178796464 105178524 216096737 896620293 234909684 588148930 505449834 622924093 34638859 805835550 561111579 891210362 887814214 473370936 867883624 186853678 526536583 154315691 141303237 108819632 614958922 286222095 275940649 708541641 812666215 20964433 940468616 439494728 856710354 667166833 712334578 602273817 262726780 819893357 24282481 681042753 795416296 235732460 597730460 503597086 591043811 796248177 525726279 138283859 170920872 679191898 151147957 37912717 544745211 211759678 872377798 945710921 535663942 805023755 497241687 170000344 779215798 941409425 255415772 8056573 559707960 271360756 723121594 190493492 366979382 421868113 547589193 922098969 754538608 799396239 442087028 984944550 167507030 520931853 141871083 4647323 864879888 116344376 558790763 423779029 823477547 652618924 109363757 533945834 839428202 811261480 636652354 132852593 999823304 145009894 74501249 821760045 195288852 940570539 858110272 [出力例] 73710316323217 |
■参照サイト
AtCoder Beginner Contest 163