C++の練習を兼ねて, AtCoder Beginner Contest 011 の 問題C (C – 123引き算) ～ 問題D (D – 大ジャンプ) を解いてみた.
■感想.
1. 問題C は, 3 を 優先的に引いていけば解けることに気付けたので, AC版に到達できたと思う.
2. N が 299 の 場合に, YES, NO の いずれのパターンも有り得るので, 面白いと思った.
3. 問題D は, N の 階乗, 4 の N乗 といった 巨大な数の計算を, なるべく平準化する方針で, 実装できたように思う.
4. 解答を見る前に, 解けたので, 及第点は取れたと思う.
本家のサイトAtCoder Beginner Contest 011 解説をご覧下さい.
■C++版プログラム(問題C／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 |
#include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報取得. int N, NG1, NG2, NG3; scanf("%d %d %d %d", &N, &NG1, &NG2, &NG3); // 2. N が NG1 ～ NG3 の いずれかに等しい場合. if(N == NG1 || N == NG2 || N == NG3){ printf("%s\n", "NO"); return 0; } // 3. 引き算を行う. int counter = 0; while(counter < 101){ // 2-1. N が 0 になったら終了. int N1 = N - 1, N2 = N - 2, N3 = N - 3; if(N == 0) break; // 2-2. increment. counter++; // printf("counter=%d N=%d\n", counter, N); // 2-3. 1, 2, 3 の いずれかを N から 減算. if(N3 >= 0 && N3 != NG1 && N3 != NG2 && N3 != NG3){ N -= 3; continue; } if(N2 >= 0 && N2 != NG1 && N2 != NG2 && N2 != NG3){ N -= 2; continue; } if(N1 >= 0 && N1 != NG1 && N1 != NG2 && N1 != NG3){ N--; continue; } } // 4. 出力. if(N == 0 && counter <= 100) printf("%s\n", "YES"); else printf("%s\n", "NO"); 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 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 |
[入力例] 2 1 7 15 [出力例] YES ※AtCoderテストケースより [入力例] 5 1 4 2 [出力例] YES ※AtCoderテストケースより [入力例] 300 57 121 244 [出力例] NO ※AtCoderテストケースより [入力例] 123 1 2 3 [出力例] NO [入力例] 7 7 5 3 [出力例] NO [入力例] 299 234 123 77 [出力例(debug版)] counter=1 N=299 counter=2 N=296 counter=3 N=293 counter=4 N=290 counter=5 N=287 counter=6 N=284 counter=7 N=281 counter=8 N=278 counter=9 N=275 counter=10 N=272 counter=11 N=269 counter=12 N=266 counter=13 N=263 counter=14 N=260 counter=15 N=257 counter=16 N=254 counter=17 N=251 counter=18 N=248 counter=19 N=245 counter=20 N=242 counter=21 N=239 counter=22 N=236 counter=23 N=233 counter=24 N=230 counter=25 N=227 counter=26 N=224 counter=27 N=221 counter=28 N=218 counter=29 N=215 counter=30 N=212 counter=31 N=209 counter=32 N=206 counter=33 N=203 counter=34 N=200 counter=35 N=197 counter=36 N=194 counter=37 N=191 counter=38 N=188 counter=39 N=185 counter=40 N=182 counter=41 N=179 counter=42 N=176 counter=43 N=173 counter=44 N=170 counter=45 N=167 counter=46 N=164 counter=47 N=161 counter=48 N=158 counter=49 N=155 counter=50 N=152 counter=51 N=149 counter=52 N=146 counter=53 N=143 counter=54 N=140 counter=55 N=137 counter=56 N=134 counter=57 N=131 counter=58 N=128 counter=59 N=125 counter=60 N=122 counter=61 N=119 counter=62 N=116 counter=63 N=113 counter=64 N=110 counter=65 N=107 counter=66 N=104 counter=67 N=101 counter=68 N=98 counter=69 N=95 counter=70 N=92 counter=71 N=89 counter=72 N=86 counter=73 N=83 counter=74 N=80 counter=75 N=78 counter=76 N=75 counter=77 N=72 counter=78 N=69 counter=79 N=66 counter=80 N=63 counter=81 N=60 counter=82 N=57 counter=83 N=54 counter=84 N=51 counter=85 N=48 counter=86 N=45 counter=87 N=42 counter=88 N=39 counter=89 N=36 counter=90 N=33 counter=91 N=30 counter=92 N=27 counter=93 N=24 counter=94 N=21 counter=95 N=18 counter=96 N=15 counter=97 N=12 counter=98 N=9 counter=99 N=6 counter=100 N=3 YES [入力例] 299 233 123 77 [出力例(debug版)] counter=1 N=299 counter=2 N=296 counter=3 N=293 counter=4 N=290 counter=5 N=287 counter=6 N=284 counter=7 N=281 counter=8 N=278 counter=9 N=275 counter=10 N=272 counter=11 N=269 counter=12 N=266 counter=13 N=263 counter=14 N=260 counter=15 N=257 counter=16 N=254 counter=17 N=251 counter=18 N=248 counter=19 N=245 counter=20 N=242 counter=21 N=239 counter=22 N=236 counter=23 N=234 counter=24 N=231 counter=25 N=228 counter=26 N=225 counter=27 N=222 counter=28 N=219 counter=29 N=216 counter=30 N=213 counter=31 N=210 counter=32 N=207 counter=33 N=204 counter=34 N=201 counter=35 N=198 counter=36 N=195 counter=37 N=192 counter=38 N=189 counter=39 N=186 counter=40 N=183 counter=41 N=180 counter=42 N=177 counter=43 N=174 counter=44 N=171 counter=45 N=168 counter=46 N=165 counter=47 N=162 counter=48 N=159 counter=49 N=156 counter=50 N=153 counter=51 N=150 counter=52 N=147 counter=53 N=144 counter=54 N=141 counter=55 N=138 counter=56 N=135 counter=57 N=132 counter=58 N=129 counter=59 N=126 counter=60 N=124 counter=61 N=121 counter=62 N=118 counter=63 N=115 counter=64 N=112 counter=65 N=109 counter=66 N=106 counter=67 N=103 counter=68 N=100 counter=69 N=97 counter=70 N=94 counter=71 N=91 counter=72 N=88 counter=73 N=85 counter=74 N=82 counter=75 N=79 counter=76 N=76 counter=77 N=73 counter=78 N=70 counter=79 N=67 counter=80 N=64 counter=81 N=61 counter=82 N=58 counter=83 N=55 counter=84 N=52 counter=85 N=49 counter=86 N=46 counter=87 N=43 counter=88 N=40 counter=89 N=37 counter=90 N=34 counter=91 N=31 counter=92 N=28 counter=93 N=25 counter=94 N=22 counter=95 N=19 counter=96 N=16 counter=97 N=13 counter=98 N=10 counter=99 N=7 counter=100 N=4 counter=101 N=1 NO |
■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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報取得. int N, D, X, Y; scanf("%d %d %d %d", &N, &D, &X, &Y); // 2. 目的を達成できる確率は？ // 2-1. X, Y が, D の倍数となる必要がありそう. if(X % D != 0 || Y % D != 0){ printf("%d\n", 0); return 0; } // 2-2. X, Y を D で 割った後に, N との差分が, 奇数回なら, 目的達成できない. // test_131_18204705_-145637640_0.txt 等 の WA対応. X /= D, Y /= D; if((N - abs(X) - abs(Y)) % 2 != 0){ printf("%d\n", 0); return 0; } // 2-3. 各移動方向の回数を確認. // X軸方向(+D) … r(回) // X軸方向(-D) … l(回) // Y軸方向(+D) … u(回) // Y軸方向(-D) … d(回) // -> 以下の条件が必要なはず. // D * (r - l) = X // D * (u - d) = Y // u + d + r + l = N // // ex. // [入力例] // 11 8562174 // 25686522 17124348 // -> 各移動方向の回数は, 以下のようになる. // u d r l count // 5 3 3 0 9240 // 4 2 4 1 34650 // 3 1 5 2 27720 // 2 0 6 3 4620 // ----------------- // 合計 76230 (通り) // -> 確率は, 76230 ÷ 4194304 (4 の 11乗) = 約 0.01817464828 と 計算できる. double ans = 0.0; int upper = (N - X - Y) / 2; for(int d = 0; d <= upper; d++){ // u, d, r, l を 計算. int u = Y + d; int r = (N - u - d + X) / 2; int l = (N - u - d - X) / 2; // printf("u=%d d=%d r=%d l=%d\n", u, d, r, l); // 確率を集計. // N! / ( u! * d! * r! * l!) / (4 の N乗) を 加算. double part = 1.0; int base = N; for(int ui = 1; ui <= u; ui++) part *= (base * 1.0 / 4.0), part /= (ui + 0.0), base--; for(int di = 1; di <= d; di++) part *= (base * 1.0 / 4.0), part /= (di + 0.0), base--; for(int ri = 1; ri <= r; ri++) part *= (base * 1.0 / 4.0), part /= (ri + 0.0), base--; for(int li = 1; li <= l; li++) part *= (base * 1.0 / 4.0), part /= (li + 0.0), base--; ans += part; } // 3. 出力 ～ 後処理. printf("%.16f", 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 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 |
[入力例] 2 10000000 10000000 10000000 [出力例(debug版)] u=1 d=0 r=1 l=0 0.1250000000000000 ※AtCoderテストケースより [入力例] 11 8562174 25686522 17124348 [出力例(debug版)] u=2 d=0 r=6 l=3 u=3 d=1 r=5 l=2 u=4 d=2 r=4 l=1 u=5 d=3 r=3 l=0 0.0181746482849121 ※AtCoderテストケースより [入力例] 16 123456 617280 370368 [出力例(debug版)] u=3 d=0 r=9 l=4 u=4 d=1 r=8 l=3 u=5 d=2 r=7 l=2 u=6 d=3 r=6 l=1 u=7 d=4 r=5 l=0 0.0048477202653885 [入力例] 45 12345 -246900 209865 [出力例(debug版)] u=17 d=0 r=4 l=24 u=18 d=1 r=3 l=23 u=19 d=2 r=2 l=22 u=20 d=3 r=1 l=21 u=21 d=4 r=0 l=20 u=22 d=5 r=-1 l=19 u=23 d=6 r=-2 l=18 u=24 d=7 r=-3 l=17 u=25 d=8 r=-4 l=16 u=26 d=9 r=-5 l=15 u=27 d=10 r=-6 l=14 u=28 d=11 r=-7 l=13 u=29 d=12 r=-8 l=12 u=30 d=13 r=-9 l=11 u=31 d=14 r=-10 l=10 u=32 d=15 r=-11 l=9 u=33 d=16 r=-12 l=8 u=34 d=17 r=-13 l=7 u=35 d=18 r=-14 l=6 u=36 d=19 r=-15 l=5 u=37 d=20 r=-16 l=4 u=38 d=21 r=-17 l=3 u=39 d=22 r=-18 l=2 u=40 d=23 r=-19 l=1 u=41 d=24 r=-20 l=0 0.0000000004541866 [入力例] 51 123 1353 3936 [出力例(debug版)] u=32 d=0 r=15 l=4 u=33 d=1 r=14 l=3 u=34 d=2 r=13 l=2 u=35 d=3 r=12 l=1 u=36 d=4 r=11 l=0 0.0000000000001572 [入力例] 7 123456789 246913578 370370367 [出力例(debug版)] u=3 d=0 r=3 l=1 u=4 d=1 r=2 l=0 0.0149536132812500 |
■参照サイト
AtCoder Beginner Contest 011