C++の練習を兼ねて, AtCoder Beginner Contest 185 の 問題E (Sequence Matching) を解いてみた.
■感想.
1. E問題は, 方針が見えなかったので, 解説を参照したところ, AC版に到達できたので良かったと思う.
2. 苦手なdpの訓練を積めたので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 185 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc185/editorial/356 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int a[1010], b[1010], dp[1010][1010]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%d", &a[i + 1]); rep(i, M) scanf("%d", &b[i + 1]); // 2. 初期化. rep(i, N + 1) rep(j, M + 1) dp[i][j] = 2020202020; rep(i, N + 1) dp[i][0] = i; rep(j, M + 1) dp[0][j] = j; // 3. dp更新. repx(i, 1, N + 1){ repx(j, 1, M + 1){ // a[i] を 削除するケース. dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1); // b[j] を 削除するケース. dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1); // a[i], b[j] を 残すケース. dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (a[i] != b[j])); } } // 4. 出力. printf("%d\n", dp[N][M]); 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 |
[入力例] 4 3 1 2 1 3 1 3 1 [出力例] 2 ※AtCoderテストケースより [入力例] 4 6 1 3 2 4 1 5 2 6 4 3 [出力例] 3 ※AtCoderテストケースより [入力例] 5 5 1 1 1 1 1 2 2 2 2 2 [出力例] 5 ※AtCoderテストケースより [入力例] 100 150 97 10 80 58 88 12 39 49 75 87 17 85 1 27 3 76 64 68 39 28 38 29 93 93 44 2 40 47 93 47 76 18 14 57 65 43 39 28 74 18 49 59 98 96 84 17 33 50 94 5 20 16 49 88 96 43 15 35 90 18 34 58 59 7 59 35 97 39 87 22 79 20 90 71 8 36 54 20 81 47 60 32 87 57 72 89 90 22 29 46 96 37 7 51 49 47 54 85 71 66 59 67 6 58 68 42 128 6 39 72 120 128 100 44 117 75 67 77 133 51 92 17 130 56 123 119 9 60 122 44 54 71 150 27 84 92 128 126 96 21 112 29 109 124 10 136 98 32 97 10 96 138 43 142 23 1 22 22 32 34 18 60 140 116 147 147 5 149 41 141 23 13 122 123 55 114 134 68 80 76 123 98 132 50 52 48 66 11 17 147 40 78 61 8 42 90 57 148 141 69 98 105 88 15 43 56 23 49 26 74 16 7 21 123 35 37 57 83 81 118 1 82 100 68 99 15 98 136 95 124 61 13 146 66 72 138 110 62 138 20 14 115 150 67 99 100 57 122 108 75 [出力例] 137 |
■参照サイト
AtCoder Beginner Contest 185