C++の練習を兼ねて, AtCoder Beginner Contest 183 の 問題E (Queen on Grid) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったので, 解説をもとに実装したところ, AC版に到達できたので良かったと思う.
2. 解説に記載されている疑似コード(dp更新式)が, 非常に, 摩訶不思議な印象を受けた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 183 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://atcoder.jp/contests/abc183/editorial/179 // 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; char board[2020][2020]; LL dp[2020][2020], X[2020][2020], Y[2020][2020], Z[2020][2020]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H){ char c[2020]; scanf("%s", c); rep(j, W) board[i][j] = c[j]; } // 2. dp更新(※解説の擬似コードをもとに, 実装). dp[0][0] = 1; rep(i, H){ rep(j, W){ if(board[i][j] == '.'){ // 2-1. X更新. if(j && board[i][j - 1] == '.'){ X[i][j] = X[i][j - 1] + dp[i][j - 1]; X[i][j] %= MOD; } // 2-2. Y更新. if(i && board[i - 1][j] == '.'){ Y[i][j] = Y[i - 1][j] + dp[i - 1][j]; Y[i][j] %= MOD; } // 2-3. Z更新. if(i && j && board[i - 1][j - 1] == '.'){ Z[i][j] = Z[i - 1][j - 1] + dp[i - 1][j - 1]; Z[i][j] %= MOD; } // 2-4. dp更新. if(i || j){ dp[i][j] = X[i][j] + Y[i][j] + Z[i][j]; dp[i][j] %= MOD; } } } } // 3. 出力. printf("%lld\n", dp[H - 1][W - 1]); 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 |
[入力例] 3 3 ... .#. ... [出力例] 10 ※AtCoderテストケースより [入力例] 4 4 ...# .... ..#. .... [出力例] 84 ※AtCoderテストケースより [入力例] 8 10 .......... .......... .......... .......... .......... .......... .......... .......... [出力例] 13701937 ※AtCoderテストケースより [入力例] 11 40 ........................................ ........................................ ....##...####...###...##...#####..####.. ...#..#..#...#.#...#...#...#...#.....#.. ...#..#..#...#.#.......#...#...#.....#.. ...####..####..#.......#...#####..####.. ..#....#.#...#.#.......#...#...#.....#.. ..#....#.#...#.#...#...#...#...#.....#.. ..#....#.####...###...###..#####..####.. ........................................ ........................................ [出力例] 551533299 |
■参照サイト
AtCoder Beginner Contest 183