C++の練習を兼ねて, JOI 2021/2022 本選 過去問 の 問題A (インターカステラー (Intercastellar)) を解いてみた.
■感想.
1. 問題Aは, 方針を絞り込めたので, AC版に到達できたので十分だと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト JOI 2021/2022 本選 過去問 解説 の 各リンク を ご覧下さい.
■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; using LL = long long; using vl = vector<LL>; #define repx(i, a, b) for(int i = a; i < b; i++) #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; scanf("%d", &N); vl p, q; p.pb(0); rep(i, N){ LL a, c = 0; scanf("%lld", &a); // ピースの細分化. while(a % 2 == 0){ ++c; a >>= 1; } // 細分化したカステラ情報(位置, 長さ)を保存. p.pb(p.back() + (1LL << c)); q.pb(a); } // 2. クエリ回答. int Q; scanf("%d", &Q); rep(i, Q){ // 2-1. 質問. LL x; scanf("%lld", &x); // 2-2. カステラの場所. int at = lower_bound(all(p), x) - p.begin(); --at; // 2-3. 出力. printf("%lld\n", q[at]); } 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 |
[入力例] 4 14 9 8 12 6 2 3 5 7 11 13 [出力例] 7 9 1 1 1 3 ※AtCoderテストケースより [入力例] 13 1 4 1 4 2 1 3 5 6 2 3 7 3 8 2 10 11 13 15 17 18 20 [出力例] 1 1 1 1 5 3 1 3 ※AtCoderテストケースより [入力例] 16 536870912 402653184 536870912 536870912 134217728 536870912 671088640 536870912 536870912 536870912 939524096 805306368 536870912 956301312 536870912 536870912 5 2500000000 3355443201 4294967296 5111111111 6190792704 [出力例] 5 1 7 57 1 ※AtCoderテストケースより [入力例] 15 2592 7680 576 92160 57600 450 33177600 2 675 225 48000 3072000 20736 147456 45 11 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 [出力例] 15 15 45 45 45 45 2025 2025 2025 2025 9 [入力例] 25 37158912 2646 840 216 73728 196 3641573376 3430 98784 1555848 1032192 260112384 47185920 1209655 1032192 12042248 236027904 110100480 393216 28800000 5529600 63221765 132765696 72576 131072 15 274 504 927 1705 3136 5768 10609 19513 35890 66012 121415 223317 410744 755476 1389537 [出力例] 567 567 567 567 567 567 567 567 567 9 27783 3969 45 45 105 |
■参照サイト
JOI 2021/2022 本選 過去問