Codeforces Round #637 (Div.2) - D

DP は比較的すぐに浮かんだのに、復元できなくて詰んだ、反省。

リンク

D. Nastya and Scoreboard
codeforces.com

問題概要

上図のように数字を点灯させることができる Scoreboard がある。
個の Scoreboard の状態が与えられるが、新たに 個点灯させたときにできる最大数を求めよ。
(与えられた Scoreboard が数字を表示できているとは限らない。)
ちょうど 個点灯させることで、数字を形成できない場合は を出力せよ。
注意点として、 番目の入力が左から 桁目となる。(最初明記されていなかったらしいが…)
また、0 から始める数字列も許容されている。

ここで、Scoreboard の状態は、7 桁の 0 と 1 の羅列で与えられ、 桁目との対応は下図のようになる。

制約

考察

しばらく考えて、
dp[ ][ ] := 左から 桁見たときに、ちょうど 個点灯させてできる最大数
と定義する DP が浮かんだ。
ただ、これだとテーブルを string 型で持つ必要があるので、最悪計算量が となり、MLE となってしまう。
落ち着け、無理だろそんなの。
というわけで、計算量の削減を考える。

string 型で持つのが厳しい制約なので、テーブルの持ち方を変えて、そこから 1 文字ずつ復元するというのが浮かぶ。
まあ、復元分からんとなって時間切れたんですけど。

DP の定義を以下のように変更する。
dp[ ][ ] := 右から順に見ていき 個まで見たとき、ちょうど 個点灯させて数字ができるかどうか
これだと、bool 型でテーブルを持つことができ、計算量が削減できる。

から始めて、 まで到達できるかどうかを調べる。
できなければ を出力する。
逆から見ていくというのが重要な点で、こうすることで、復元で 桁目まで到達したときに、 以外の場所に行ってしまうことが防げる。
(初期値をそのように定めることで、遷移元にはなり得ないから。)

書いていて思ったが、左から遷移して右から復元でもできないことはない。
ただ、復元順とは逆向きに出力しないといけないので、右から遷移させる方が自然だろう。
本番ではそれに気が付かなかったわけであるが…

どういう遷移を辿るかを意識しましょう。(自戒)

コード

数字 が作れるかどうかの判定を bitset で行っているが、分かりやすいやり方でよい。
bitset はあまり使ったことがなく、個人的に苦手意識があるので、今回使用してみた。
Scoreboard の状態が 2 進数表記で与えられているので、bitset で扱いやすいのではないかと思ったのも動機である。
スマートな初期化の仕方が分からなくて、本番まずそこで躓いたんだけど…

#include <iostream>
#include <vector>
#include <string>
#include <bitset>
using namespace std;

string s[10] = {"1110111", "0010010", "1011101", 
                "1011011", "0111010", "1101011", 
                "1101111", "1010010", "1111111", "1111011"};

// dp[i][j] := n 桁目から始めて (n - i) 個見たときに、
//             未点灯をちょうど j 個点けた状態にできるかどうか
bool dp[2010][2010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<bitset<7>> input(n);     // 現在の Scoreboard の状態
    for(int i = 0; i < n; ++i)  cin >> input[i];

    // bs[i] := 数字 i が作れるときの Scoreboard の状態
    vector<bitset<7>> bs(10);
    for(int i = 0; i < 10; ++i) bs[i] = bitset<7>(s[i]);
    
    dp[n][0] = 1;
    for(int i = n - 1; i >= 0; --i){
        for(int j = 0; j <= k; ++j){
            // ちょうど j 個点灯できる直前の状態がなければ continue
            if(!dp[i + 1][j])   continue;

            for(int x = 0; x < 10; ++x){
                // 数字 x を今見ている Scoreboard で作れるかどうか判定する
                if(bs[x] != (input[i] | bs[x])) continue;

                // 数字 x にするのに、何個必要か
                int add = (input[i] ^ bs[x]).count();

                dp[i][j + add] |= dp[i + 1][j];
            }
        }
    }

    // 未点灯部分をちょうど k 個使う方法が存在しなければ -1 を出力
    if(!dp[0][k]){
        cout << -1 << '\n';
        return 0;
    }

    for(int i = 0; i < n; ++i){
        // 数字を降順に見ていって、遷移元がある数字を出力していく
        for(int x = 9; x >= 0; --x){
            if(bs[x] != (input[i] | bs[x])) continue;
            int dif = (input[i] ^ bs[x]).count();
            if(k - dif >= 0){
                if(!dp[i + 1][k - dif])   continue;
                cout << x;
                k -= dif;
                break;
            }
        }
    }
    cout << '\n';
}

雑記

今回はだいぶ流して書いた。
復元なかなか書く機会がないから、自分の中に落とし込めないな。
書いてからも本当にこれで大丈夫なのか、という気持ちになるし。
そもそも DP を理解できていないということを痛感させられる。