C++の練習を兼ねて, AtCoder Beginner Contest 118 の 問題D (D – Match Matching) を解いてみた.
■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. 複雑怪奇に感じたものの, 苦手な DP の訓練となったと思う.
本家のサイトABC 118解説をご覧下さい.
■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 |
// 解き直し. // ABC 118 解説. // https://img.atcoder.jp/abc118/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) const int MATCH[9] = {2, 5, 5, 4, 5, 6, 3, 7, 6}; int dp[12321]; struct match{ int n; // マッチ棒で表現する数字. int u; // 数字1文字を構成するのに必要なマッチの使用本数. bool operator<(const match& rhs) const { return (u < rhs.u) || ((u == rhs.u) && (n > rhs.n)); } }; int main(){ // 1. 入力情報取得. int N, M; scanf("%d %d", &N, &M); vector<match> A; FOR(i, 0, M){ int a; scanf("%d", &a); match m; m.n = a, m.u = MATCH[a - 1]; A.push_back(m); } // 2. 初期化, sort. FOR(i, 0, N + 1) dp[i] = -123454321; sort(A.begin(), A.end()); // for(auto &a : A) printf("%d %d\n", a.u, a.n); // 3. 解説通り. // dp[i]: ちょうどi本のマッチ棒を使って, 条件を満たす整数を作る場合の最大桁数. dp[0] = 0; FOR(i, 1, N + 1) for(auto &a : A) if(i >= a.u) dp[i] = max(dp[i], dp[i - a.u] + 1); // printf("dp[%d]=%d\n", N, dp[N]); // 4. dp の 結果をもとに, 出力. while(N > 0){ // 4-1. 最上位の桁 を 抽出. int d = 0; for(auto &a : A){ // a.n が 最上位の桁 に使えるかどうかは, // dp[N - a.u] = dp[N] - 1 であるかを確認すれば良い, とのこと. if(N - a.u >= 0 && dp[N - a.u] == dp[N] - 1) d = max(d, a.n); } // 4-2. 最上位の桁が確定したので, 未使用のマッチ棒の本数 N を デクリメント. N -= MATCH[d - 1]; printf("%d", d); } 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 |
[入力例] 2 1 1 [出力例] 1 [入力例] 5 2 1 7 [出力例] 71 [入力例] 20 4 3 7 8 4 [出力例] 777773 ※AtCoderテストケースより [入力例] 101 9 9 8 7 6 5 4 3 2 1 [出力例] 71111111111111111111111111111111111111111111111111 ※AtCoderテストケースより [入力例] 15 3 5 4 6 [出力例] 654 ※AtCoderテストケースより [入力例] 31 5 2 3 5 7 9 [出力例] 777777755 [入力例] 999 7 9 8 6 5 3 2 [出力例] 9999555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555 |
■参照サイト
AtCoder Beginner Contest 118