問題

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() {
    // 9から降順に並べる（貪欲にチェックするため）
    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) {
            // 最後まで到達した時ちょうどkを使い切っていないといけない
            if (r == 0) return x;
            else return string("-1");
        }
        // 修理するセグメントの残りが範囲外ならNG
        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;
            // k の消費数
            int e = b[i].count() - (d[c] & b[i]).count();
            // k が足りないなら不採用
            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を大幅更新してしまって、申し訳ない気持ちと通せば勝ちなんだよという気持ちが混じり合って複雑な心境です・・・。

Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

D. Nastya and Scoreboard (Codeforces Round #637 Div. 2)

問題

問題概要

考察

概要

回答例

反省