Match Matching [AtCoder Beginner Contest 118 D]

https://atcoder.jp/contests/abc118/tasks/abc118_d

解説

https://atcoder.jp/contests/abc118/submissions/4287467

嘘解答の可能性があります

最適方針として、なるべく桁数を増やしたほうがいいことは分かる。
そのためには、一番少ない本数で作れる数をたくさん使うのがいい。
あとは、残りを調整してピッタリN本で数を作る部分を考える。
　
自分はこの調整は6桁分くらいで十分と考え、調整用の6桁分を全探索し、たくさん使う数も全探索する。
これで10^7の全探索となるので、間に合う。
　
作れる最大の数の大小を見るために、答えを1～9の数を何個使ったかのvectorで保持する。
この比較用にcomp関数を作る。
comp(a,b) := a＜bであるならtrue, そうでないならfalse

int N, M, A[11];
int need[] = { 0, 2,5,5,4,5,6,3,7,6 };
using vi = vector<int>;
#define init vi(10, 0)
//---------------------------------------------------------------------------------------------------
bool comp(vi a, vi b) {
    int sm1 = 0;
    fore(i, a) sm1 += i;
 
    int sm2 = 0;
    fore(i, b) sm2 += i;
 
    if (sm1 != sm2) return sm1 < sm2;
 
    rrep(i, 9, 0) if (a[i] != b[i]) return a[i] < b[i];

    return false;
}
//---------------------------------------------------------------------------------------------------
string solve() {
    vector<int> ans = init;
 
    rep(a1, 0, 10) rep(a2, 0, 10) rep(a3, 0, 10) rep(a4, 0, 10) rep(a5, 0, 10) rep(a6, 0, 10) rep(r, 1, 10) {
        int cst = need[a1] + need[a2] + need[a3] + need[a4] + need[a5] + need[a6];
        int d = N - cst;
 
        if (d < 0) continue;
 
        if (A[a1] == 0) continue;
        if (A[a2] == 0) continue;
        if (A[a3] == 0) continue;
        if (A[a4] == 0) continue;
        if (A[a5] == 0) continue;
        if (A[a6] == 0) continue;
        if (A[r] == 0) continue;
 
        vi cand(10, 0);
        if(0 < a1) cand[a1]++;
        if (0 < a2) cand[a2]++;
        if (0 < a3) cand[a3]++;
        if (0 < a4) cand[a4]++;
        if (0 < a5) cand[a5]++;
        if (0 < a6) cand[a6]++;
 
        if (0 < d % need[r]) continue;
        cand[r] += d / need[r];
 
        if (comp(ans, cand)) {
            ans = cand;
        }
    }
 
    string res = "";
    rrep(i, 9, 1) {
        rep(j, 0, ans[i]) res += char('0' + i);
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    A[0] = 1;
    rep(i, 0, M) {
        int a; cin >> a;
        A[a] = 1;
    }
    cout << solve() << endl;
}