C++の練習を兼ねて, AtCoder Beginner Contest 205 の 問題D (Kth Excluded) を解いてみた.
■感想.
1. 問題Dは, 方針を決めることができたので, AC版に到達できたと思う.
2. 桁数オーバーフローに注意する必要があると感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 205 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題D／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 all(x) x.begin(), x.end() int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); vl aCum, aMax; LL bef = 0, cur, aCount = 0; rep(i, N + 1){ // 1-1. 今回分更新. if(i < N) scanf("%lld", &cur); else cur = 2e18 + 1; // killer_00.txt, killer_01.txt の WA回避のため修正. // 1-2. 前回分 + 1 でない. if(cur != bef + 1){ // 開始地点, 終了地点, 数列の長さ. LL s = bef + 1, g = cur - 1; aCount += (g - s + 1); // 数列の長さ. aCum.pb(aCount); // 終了地点. aMax.pb(g); } // 1-3. 前回分更新. bef = cur; } // 2. クエリ回答. rep(i, Q){ // 2-1. 入力情報. LL k; scanf("%lld", &k); // 2-2. 対象区間は？ int at = lower_bound(all(aCum), k) - aCum.begin(); // 2-3. 出力. printf("%lld\n", aMax[at] - (aCum[at] - k)); } 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 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 202 203 204 205 206 207 |
[入力例] 4 3 3 5 6 7 2 5 3 [出力例] 2 9 4 ※AtCoderテストケースより [入力例] 5 2 1 2 3 4 5 1 10 [出力例] 6 15 ※AtCoderテストケースより [入力例] 25 10 6 12 13 14 15 18 19 20 21 30 31 33 34 36 38 39 50 52 53 61 62 63 70 75 76 6 12 18 23 31 38 45 52 62 72 [出力例] 7 17 27 37 47 57 67 77 87 97 [入力例] 100 23 9 10 11 17 18 19 28 30 33 35 36 37 45 46 49 52 53 54 62 64 65 66 73 75 76 82 87 89 91 95 100 103 104 106 109 112 115 116 121 123 127 132 134 135 137 138 143 145 146 147 148 150 151 152 155 159 164 167 171 175 180 181 184 189 194 198 203 204 209 210 211 215 218 221 226 230 231 232 253 254 255 297 298 299 310 311 330 331 332 353 354 355 380 381 497 498 499 502 503 504 21 54 43 46 900 3 18 83 72 17 592 93 56 651 93 50 495 25 9 34 49 421 921 [出力例] 27 79 61 68 1000 3 24 122 105 23 692 139 81 751 139 72 595 34 12 48 71 521 1021 [入力例] 250 50 746613 746614 746615 2683153 3233720 4204660 4652794 5883835 6422788 6953670 7636076 8563481 9178735 9489843 9899172 10335868 10653155 11792699 11925921 13046145 13808643 14855572 15487195 16627308 17744167 18234255 19053679 19337935 20030518 21024520 21745112 22629723 22653485 23431917 24663819 25323066 26145758 27013488 27353017 27383022 27974175 28107805 28650712 29447740 30007066 30431360 30431361 30431362 30431363 30431364 33706250 34343267 35348883 36527092 36704391 37624195 38595540 38843525 39469807 40677306 40867726 41413646 41450599 42443129 42673155 43814255 44319778 45367530 46051714 46214520 46409682 46649187 47848776 48041150 49107102 49549002 50471556 51196857 52387753 52743126 53268887 53290116 53836692 54096175 55128955 55430769 56299460 56845910 58074768 58505119 59035065 59636949 60072005 60398854 61581656 62082401 62706903 63721251 63979740 64183740 64886128 65887076 65973029 66567134 67234932 67647604 68263536 68830022 69145848 70197165 71431412 71904605 72507825 72847177 72847178 72847179 74293680 74464402 74561173 75279390 76465146 76914292 76918559 77562993 77872863 78589101 78886401 79034982 79279781 79865710 80239004 81047599 81940328 82004122 82614772 83791664 84743572 85403795 85516862 85942481 86512389 87493211 87609539 88046984 88476486 89576066 90624417 91719247 91802642 92034759 92705104 93924733 94470025 95300864 95503652 96171236 96557301 96611825 97630015 97783772 98356198 98773823 99506358 99942052 101118416 101695959 102003307 102740910 102740911 102740912 102740913 102740914 107236281 107793841 108421371 109063986 110174581 110430309 111209218 112411974 113512766 113826936 114503106 115484856 115653990 116273123 116291391 116817712 117420207 118217824 118417034 119483434 119831598 119872135 121017712 121170135 121415639 122565788 123553520 123853682 124201031 124509002 125578997 125927099 125927100 125927101 125927102 125927103 125927104 125927105 130086977 130649975 130649976 130649977 132762225 133842101 133925877 134897737 136126419 136135464 137035030 137935786 139155540 139237102 140013889 141037552 141990744 142347628 143451636 144240520 144799072 145606437 146038290 146147363 146202540 147406002 148238354 149030196 149349615 150543917 150913307 152123371 153166373 153975225 154195402 155052997 155052998 155052999 155053000 155053001 110251 688332 1853162 2241472 2302113 3394423 4113196 4897496 5629575 6030655 6203046 7355841 7941409 8860266 9915464 10475700 11295594 11611593 12341892 12382850 13535801 14596820 14945771 15212412 16050416 16556751 16952026 16982735 17404171 18360731 18404043 18566152 19717961 20534388 20942279 21892954 22344006 22615407 22884648 23243021 23868687 24210078 24529796 25214811 26154712 26222830 26723591 27744901 28976714 29989729 [出力例] 110251 688332 1853165 2241475 2302116 3394428 4113201 4897503 5629582 6030663 6203054 7355851 7941420 8860278 9915479 10475716 11295611 11611610 12341911 12382869 13535821 14596841 14945793 15212434 16050439 16556774 16952050 16982759 17404195 18360757 18404069 18566178 19717989 20534417 20942308 21892985 22344037 22615438 22884681 23243054 23868721 24210112 24529830 25214846 26154749 26222867 26723628 27744941 28976757 29989773 |
■参照サイト
AtCoder Beginner Contest 205