AtCoder Beginner Contest 118 D Match Matching

参考にさせて頂いた記事

drken1215.hatenablog.com AtCoderの解説

問題

atcoder.jp

問題の概要

マッチ棒を使って数字を作る。
から までの数字はそれぞれ 本のマッチ棒を使用することで作ることができる。
本のマッチ棒で 種類の数字 のみを使用した自然数を作るとき、この条件下で作ることができる最大の自然数を求めよ。

考察

想定解ではないのですが、こういう問題文で貪欲で考えてしまうのが人(緑)の性だと思うのです。

数字 を作るのに必要なマッチ棒の数を とします。

できるだけ大きい自然数を作りたいので、数列 の中からマッチ棒の消費を抑えられる数字を貪欲に選んでみます。

この解法では のときマッチ棒をちょうど使い切ることができます。

しかし、 のときはマッチ棒が少しだけ余ってしまい、正しい答えを導き出すことができなくなってしまいます。

そのため、

本のマッチ棒を使用したときの最大値

としたDPを考えます。
このとき答えは になります。

DPテーブルの更新は,

で行うことができます。

つまり、 本マッチ棒を使用してできる自然数の最大値に を付け加えた自然数と 本マッチ棒を使用してできる自然数の最大値のどちらが大きいかを比較します。

下図に のとき に の数字を付け加えたときの遷移を示します。

また、自然数は64bit整数型に収まらない可能性があるため文字列で持つことにします。

そのため文字列で表された自然数を比較する必要がありますが、これは単純に辞書順で比較すれば良いです。

提出コード

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

int main() {
  // 数字を作るために必要なマッチ棒
  int num[10] = {0,2,5,5,4,5,6,3,7,6};

  int n,m;
  cin >> n >> m;

  vector<int> a(m);
  for (int i = 0; i < m; ++i) {
    cin >> a[i];
  }

  // dpデーブル。dp(i) = '+' のときはi本のマッチ棒で自然数を作ることができないことを示す。
  vector<string> dp(n+10, "+");
  // 初期化
  dp[0] = "";

  for (int i = 0; i < n; ++i) {
    // 自然数を作ることができないのでスキップ
    if (dp[i] == "+") continue;
    
    // 図のような遷移を考える
    for (auto itr : a) {
      string candidate = dp[i] + (char)('0' + itr);

      if (dp[i + num[itr]] == "+") {
　　 // 遷移先がまだ到達されていない場合
        dp[i + num[itr]] = candidate;
      } else if (candidate.size() > dp[i + num[itr]].size()) {
        // 遷移先の桁数より作った自然数の桁数の方が大きい場合
        dp[i + num[itr]] = candidate;
      } else if (candidate.size() == dp[i + num[itr]].size()) {
        // 桁数が同じ場合、辞書順で比較
        // 辞書順比較は簡単にできる。
        dp[i + num[itr]] = (candidate > dp[i + num[itr]]) ? candidate : dp[i + num[itr]];
      }
    }
  }

  cout << dp[n] << endl;
}