AtCoder DPの例題といてみた1

AtCoder DPの例題といてみた

今回の問題

問題文

ちょうど $N$ 本のマッチ棒を使って作れる整数の中で最大のものを求めてください。
ただし、以下の条件を満たさなければなりません。

• 作る整数の各桁は、$1$ から $9$ までの数字のうち $A_1, A_2, \ldots, A_M (1 \leq A_i \leq 9)$ のいずれかでなければならない。
• 数字 $1, 2, 3, 4, 5, 6, 7, 8, 9$ を $1$ つ作るには、それぞれちょうど $2, 5, 5, 4, 5, 6, 3, 7, 6$ 本のマッチ棒を使う。

制約

• 入力は全て整数である。
• $2 \leq N \leq 10^4$
• $1 \leq M \leq 9$
• $1 \leq A_i \leq 9$
• $A_i$ は全て異なる。
• ちょうど $N$ 本のマッチ棒を使って条件を満たすように作れる整数が存在する。

自分の回答

#include <bits/stdc++.h>
using namespace std;

// マッチ棒の本数テーブル (indexが数字に対応)
const int COST[] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> A(M);
    for (int i = 0; i < M; i++) {
        cin >> A[i];
    }
    // 復元時に大きい数字から試したいので降順ソートしておく
    sort(A.rbegin(), A.rend());

    // dp[i] := ちょうど i 本使って作れる最大の「桁数」
    // 初期値は -INF (到達不可能を表す)
    vector<int> dp(N + 1, -1000000000);
    
    // 0本で0桁がスタート地点
    dp[0] = 0;

    // 1. 桁数を最大化するDP
    for (int i = 1; i <= N; i++) {
        for (int a : A) {
            int w = COST[a];
            if (i - w >= 0) {
                dp[i] = max(dp[i], dp[i - w] + 1);
            }
        }
    }

    // 2. 復元パート
    // 残りマッチ本数が remain のとき、次に置く数字を決める
    int remain = N;
    
    // 桁数(dp[N])分だけループを回して数字を出力する
    // (while(remain > 0) でもよいですが、桁数が分かっているのでこの方が確実)
    int length = dp[N];
    
    for (int i = 0; i < length; i++) {
        // 大きい数字から順に試す
        for (int a : A) {
            int w = COST[a];
            
            // 「この数字 a を採用した場合、残りのマッチ棒(remain - w)で、
            //   残りの桁数(dp[remain] - 1)を作れるか？」を判定
            if (remain - w >= 0 && dp[remain - w] == dp[remain] - 1) {
                cout << a;
                remain -= w;
                break; // この桁は決まったので次の桁へ
            }
        }
    }
    cout << endl;

    return 0;
}

自分なりの解説

V問題以降難しすぎて理解すらできなかったので残りの日数はdpの例題を解いていこうと思う。

今回の問題はdp[i] = 「ちょうど $i$ 本のマッチを使って作れる整数の最大桁数」として、
遷移式をdp[i] = max(dp[i], dp[i - コスト] + 1)とすると解くことができる。ここから実際に一番大きい数を復元していく。