注意：以下の解説は想定解ではありません。しかも、コンテストではシステムテストを通ったのに、今投げるとTLEで落ちます。（えー
想定解はDPですのでDPで解きましょう。
この記事は自分のための備忘録として残しておくものです。
(2020-04-26追記）DPで解き直したので、別の記事に書きました。(追記ここまで)
問題
https://codeforces.com/contest/1341/problem/D
問題概要
7セグがn個並んでいて、点灯状況が与えられる。しかし、k個のセグメントが故障している。
k個の故障箇所を直した時に表現できる可能性のある数値のうちで、最大のものを答えよ。ただし、「故障」とは点灯すべきセグメントが点灯していない状況を指す。（本来消灯すべきセグメントが点灯しているという状況は考慮しない）
ただし、いかなる組み合わせでも数値として表現不可能である場合は-1を回答とせよ。
考察
制約や問題の性質を見て、あ、これはDPだなとは思ったのですが、実戦ではまあ上から貪欲でもいけるんじゃない？と思って突っ走ってしまいました。以下、その実戦での解法となります。
概要
概要としては単純で、DFSで大きい数字から順に構築していって、構築できたらそれを答えとして終了、というだけです。ただし、答えが後ろの方にあるとTLEしてしまいますので、枝狩りする必要があります。
私は、各7セグに対して追加すべきセグメントの最小値と最大値を累積和で保存して、kの残りがその範囲内で収まっていない場合即NGとしました。
例えば残り3つの状況でkの残りが0のとき、残り3つのうち一つでも追加のセグメントが必要であれば構築不可能です。また、残り3つの状況でkの残りがいくつかあるのに、残り3つすべてが追加のセグメントを必要としない場合などもkを使い切っての構築は不可能です。
回答例
注意：以下の回答は、現在TLEで落ちます
コンテスト時点ではなかったテストケースが追加されているようです。
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<bitset<7>> b{
bitset<7>("1111011"),
bitset<7>("1111111"),
bitset<7>("1010010"),
bitset<7>("1101111"),
bitset<7>("1101011"),
bitset<7>("0111010"),
bitset<7>("1011011"),
bitset<7>("1011101"),
bitset<7>("0010010"),
bitset<7>("1110111")
};
int n, k;
cin >> n >> k;
vector<bitset<7>> d(n);
vector<int> mn(n + 1, 0);
vector<int> mx(n + 1, 0);
string s;
for (int i = 0; i < n; i++) {
cin >> s;
d[i] = bitset<7>(s);
int mnn = 8;
int mxx = -1;
for (int j = 0; j < 10; j++) {
if (((d[i] | b[j]) ^ b[j]).any()) continue;
int e = b[j].count() - (d[i] & b[j]).count();
mnn = min(mnn, e);
mxx = max(mxx, e);
}
mn[i + 1] = mn[i] + mnn;
mx[i + 1] = mx[i] + mxx;
}
function<string(string, int, int)> dfs = [&](string x, int c, int r) {
if (c == n) {
if (r == 0) return x;
else return string("-1");
}
if (r < mn[n] - mn[c] or r > mx[n] - mx[c]) return string("-1");
string ret = "-1";
for (int i = 0; i < 10; i++) {
if (((d[c] | b[i]) ^ b[i]).any()) continue;
int e = b[i].count() - (d[c] & b[i]).count();
if (r - e < 0) continue;
ret = max(ret, dfs(x + to_string(9 - i), c + 1, r - e));
if (ret != "-1") break;
}
return ret;
};
cout << dfs("", 0, k) << endl;
}
反省
こういうのを枝狩りで頑張ろうとするとWAが増えがちなので（実際6WA出した）（いやそれ以前にTLE解ですけど）、DPが見えてるんなら素直にDPで解きましょう・・・。
こんなのでHighestを大幅更新してしまって、申し訳ない気持ちと通せば勝ちなんだよという気持ちが混じり合って複雑な心境です・・・。
