C++の練習を兼ねて, キーエンス プログラミング コンテスト 2021 の 問題C (Robot on Grid) を解いてみた.
■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト キーエンス プログラミング コンテスト 2021 解説 の 各リンク を ご覧下さい.
■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 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 |
// 解き直し. // https://atcoder.jp/contests/keyence2021/editorial/564 // 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 = 998244353; const LL DIV3 = 332748118; const int MAX = 5050; char board[MAX][MAX]; LL dp[MAX][MAX]; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t % MOD; } int main(){ // 1. 入力情報. int H, W, K; scanf("%d %d %d", &H, &W, &K); rep(h, MAX) rep(w, MAX) board[h][w] = '.'; rep(i, K){ int h, w; char c[11]; scanf("%d %d %s", &h, &w, c); h--, w--; board[h][w] = c[0]; } // 2. dp更新. dp[0][0] = 1; rep(h, H){ rep(w, W){ // 2-1. 開始地点は, Skip. if(h ==0 && w == 0) continue; // 2-2. 行方向更新. if(h){ // マス目(h - 1, w) の 値. char op = board[h - 1][w]; LL cur = dp[h - 1][w]; // マス目(h - 1, w) が, 空欄 の 場合. if(op == '.'){ cur *= 2LL; cur %= MOD; cur *= DIV3; cur %= MOD; } // マス目(h - 1, w) が, 'X', 'D' の 場合(何もしない). // if(op == 'X' || op == 'D'){} // マス目(h - 1, w) が, 'R' の 場合. if(op == 'R') cur = 0; // マス目(h, w) を 更新. dp[h][w] += cur; dp[h][w] %= MOD; } // 2-3. 列方向更新. if(w){ // マス目(h, w - 1) の 値. char op = board[h][w - 1]; LL cur = dp[h][w - 1]; // マス目(h, w - 1) が, 空欄 の 場合. if(op == '.'){ cur *= 2LL; cur %= MOD; cur *= DIV3; cur %= MOD; } // マス目(h, w - 1) が, 'X', 'R' の 場合(何もしない). // if(op == 'X' || op == 'R'){} // マス目(h, w - 1) が, 'D' の 場合. if(op == 'D') cur = 0; // マス目(h, w) を 更新. dp[h][w] += cur; dp[h][w] %= MOD; } } } // 3. 3 の (H * W - K)乗. LL ans = dp[H - 1][W - 1]; ans *= mPow(3LL, (LL)(H * W - K)); ans %= MOD; // 4. 出力. 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 |
[入力例] 2 2 3 1 1 X 2 1 R 2 2 R [出力例] 5 ※AtCoderテストケースより [入力例] 3 3 5 2 3 D 1 3 D 2 1 D 1 2 X 3 1 R [出力例] 150 ※AtCoderテストケースより [入力例] 5000 5000 10 585 1323 R 2633 3788 X 1222 4989 D 1456 4841 X 2115 3191 R 2120 4450 X 4325 2864 X 222 3205 D 2134 2388 X 2262 3565 R [出力例] 139923295 ※AtCoderテストケースより [入力例] 3 4 5 1 1 D 1 3 R 2 3 X 3 1 R 3 2 D [出力例] 1296 [入力例] 5 7 8 1 1 R 1 6 D 2 3 D 2 4 R 3 5 X 3 7 D 4 3 R 5 2 D [出力例] 865608789 |
■参照サイト
キーエンス プログラミング コンテスト 2021