C++の練習を兼ねて, Mujin Programming Challenge 2017 の 問題A (Robot Racing) を解いてみた.
■感想.
1. 問題Aは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説上 の stack を利用したロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト Mujin Programming Challenge 2017 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/mujin-pc-2017/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) const LL MOD = 1e9 + 7; LL FAC[101010]; int x[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &x[i]); // 2. 事前計算. FAC[0] = 1; repx(i, 1, N + 1) FAC[i] = (LL)i * FAC[i - 1] % MOD; // 3. 操作. stack<int> st; LL ans = 1; repx(i, 1, N + 1){ // ロボット追加. st.push(x[i - 1]); // k番目の要素と見て, 座標チェック. int k = st.size(); if(x[i - 1] < 2 * k - 1){ st.pop(); ans *= (LL)k; ans %= MOD; } } // 4. 残ったロボット. ans *= FAC[st.size()]; ans %= MOD; // 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
[入力例] 3 1 2 3 [出力例] 4 ※AtCoderのテストケースより [入力例] 3 2 3 4 [出力例] 6 ※AtCoderのテストケースより [入力例] 8 1 2 3 5 7 11 13 17 [出力例] 10080 ※AtCoderのテストケースより [入力例] 13 4 6 8 9 10 12 14 15 16 18 20 21 22 [出力例] 311014372 ※AtCoderのテストケースより [入力例] 2 1 5 [出力例] 2 [入力例] 3 1 3 5 [出力例] 6 [入力例] 7 1 5 8 9 11 12 20 [出力例] 5040 [入力例] 20 2 12 21 29 30 35 47 54 65 70 71 78 80 85 89 100 106 107 118 119 [出力例] 146326063 [入力例] 120 1 2 5 11 25 33 35 42 45 46 51 52 59 64 68 69 78 88 89 99 108 118 122 123 127 128 129 136 141 150 153 154 162 164 173 175 178 187 192 195 201 206 213 216 226 236 245 252 255 264 265 272 278 285 291 299 307 311 317 322 325 329 333 336 340 346 350 353 362 365 366 370 374 383 387 392 401 405 409 418 420 423 425 429 435 436 440 448 450 453 458 465 471 476 482 489 494 501 504 511 513 522 523 526 527 533 542 550 552 556 557 567 568 572 582 585 586 595 604 606 [出力例] 588578382 |