競プロ日記

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 29;
constexpr lint   INFL = 1LL << 61;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  rep (i, m) cin >> a[i];
  const vector<int> match{0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
  rep (i, m) b[i] = match[a[i]];
  unordered_map<int, int> num;
  rep (i, m) num[b[i]] = max(num[b[i]], a[i]);
  sort(all(b));
  b.erase(unique(all(b)), b.end());
  const int bs = b.size();
  vector<map<int, int>> dp(n + 1);
  auto comp =
    [&](map<int, int> &x, map<int, int> &y) {
      if (x[0] != y[0]) {
        return x[0] < y[0];
      } else {
        for (auto xitr = x.rbegin(), yitr = y.rbegin(); xitr != x.rend() && yitr != y.rend(); ++xitr, ++yitr) {
          int xf = xitr->first, xs = xitr->second, yf = yitr->first, ys = yitr->second;
          if (xf != yf) {
            return xf < yf;
          } else {
            if (xs != ys) return xs < ys;
          }
        }
        return true;
      }
    };
  dp[0][0] = 0;
  rep (i, n + 1) {
    if (dp[i].empty()) continue;
    rep (j, bs) {
      if (i + b[j] > n) continue;
      auto tmp = dp[i];
      ++tmp[0];
      ++tmp[num[b[j]]];
      if (comp(dp[i + b[j]], tmp)) dp[i + b[j]] = tmp;
    }
  }
  string ans;
  for (auto itr = dp[n].rbegin(); itr != --dp[n].rend(); ++itr) {
    ans += string(itr->second, itr->first + '0');
  }
  cout << ans << endl;
  return 0;
}

青だけど自力で解けてうれC。
本番だとAからDまで通せていないくらいの時間はかかっているので、そろそろ速度も考えないと。

10分程解析的に解こうと色々考えたが、最終的にDPで良い感じになりそうなことが分かった。
その後色々試行錯誤して以下のようなDPに至った。
DP[使用したマッチの総数]=最大桁数 & map{使用する数字：その数字を使用する回数}
0はマッチで作る数字には存在しないので、0に桁数を格納することでpairがいらなくなる。
使用したマッチの総数iを1～Nまで、使用するj番目の数字を0からMまでループして値を更新する。
j番目の数字a[j]、a[j]を作るのに必要なマッチの数をb[j]とし、newDP[i]を、DP[i][0]を+1、DP[i][a[j]]を+1したものとする。
すると更新はDP[i+b[j]]=max(DP[i+b[j]], newDP[i])となる。

mapの比較は以下のように行う。
まず、桁数が異なれば大きい方を大とする。
次に、等しい場合は先頭要素のkeyを比較し、異なる場合は大きい方を大とする。
先頭要素のkeyも等しい場合は、先頭要素のvalueを比較し、異なる場合は大きい方を大とする。
それも同じ場合は次の要素を比較する。

初期値はDP[0][0]=0とし、DP[i]が空だった場合は更新しない。
答えは、DP[N]から数字が大きい順に指定回数取り出したものになる。

この流れの実現に当たって少し工夫したのが、使用する数字の選別である。
同じ本数で作れる数字が複数あれば、必ず大きい方を使うべきなので小さい方は取り除いても良い。
mを減らせるので速度の改善が期待できる。
しかしこの作業を行ったがために、処理が色々と複雑になってしまった。
1発でACしたものの、実装中は色々とすんなり行かなかった。
実装中にDPに持つ情報を色々変えたので、当初は被りがあるとまずい予定だった。
最終的には被りがあろうと関係ないDPになったので、1～9のMを減らしてもせいぜい定数倍レベルしか改善さないようなこの操作はなくすべきだったかもしれない。

AC後に解法を調べてみると、どの解法も方針は大体同じものの、実装はもっと楽にできたらしい。
特に、DPの値に文字列を持つのはかなり頭良いと思った。
DPで持つ値が文字列と連想配列だとどちらが一般的かと言われれば間違いなく文字列だろうが、なぜか全く思いつかなかった。
DPは一言で言っても、本当に千差万別なのをまた実感した。
もっと慣れていきたい。