ABC 322 E Product Development

問題

コストCnのN個中から好きなだけ選んで要素K個を全てP以上にする時の最小コストを求める問題 (0<N<100,1<K,P<=5)

考えたこと

Nが100なのでNの3乗の解の可能性を考える。また、最小コストを求めよということで最小全域木の問題にできないかと考える。スコア毎に0-5として、あるiを採用したら、そのスコアに移動できるような有効グラフを考えるも、いつそのiが採用されるかわからないため、グラフの本数がとても多くなることに気づき、やめる。次に、各iを全てpriority_queueに入れて、小さい順から選択し、別のjを足し合わせてまたpriority_queueに入れるという方針が思いつく。しかし、その間にコンテストがTimeUPとなってしいました。 解答としてはDPを使う方法があります。実際にK=2、P=3の場合を考えてDPテーブルを記述してみます。以下のような形になりテーブルの数はN*(P+1)^Kとなっていることがわかります。そして各遷移にはK回の足し算が必要なので最終的な計算量はO(NK(P+1)^K)となることがわかります。ナップDPのように採用する採用しないで値を計算していけばよかったのですね。

最後に

priority_queueでやってみたけどWAが6つ。ACできず悔しい。また、制約から計算量がどうなるか予想できない、かつどのあたりの計算まで許されるかわかっていなかったのでコンテスト中は考えがまとまらなかったです。。。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

const static int NIL = -1;
const long long INF = 1LL << 60;
typedef long long ll;
typedef unsigned long long ull;

bool is_debug = true;
int ini = 1000000001;
ull mod = 1000000007;


int main(){
    int n, k, p;
    cin >> n >> k >> p;
    vector<int> c(n);
    vector<vector<int>> a(n, vector<int>(k));
    for(int i = 0; i < n; i++){
        cin >> c[i];
        for(int j = 0; j < k; j++){
            cin >> a[i][j];
        }
    }

    int limit = 0;
    int power = 1;
    for(int i = 0; i < k; i++){
        limit += p * power;
        power *= 10;
    }

    vector<vector<ll>> dp(n + 1, vector<ll>(limit + 1, INF));
    dp[0][0] = 0;
    
    auto display = [](vector<vector<ll>>dp){
        for(auto v : dp){
            for(ll e : v){
                cout << e << " ";
            }
            cout << endl;
        }
        cout << endl;
    };

    auto calc = [k, p](int current, vector<int> add){
        string s = to_string(current);
        while((int)s.size() < k){
            s = "0" + s;
        }

        int result = 0;
        for(int i = 0; i < k; i++){
            int sum = (s[i] - '0') + add[i];
            sum = min(sum, p);
            result += sum * pow(10, k - i - 1);
            
        }
        return result;
    };

    /*
   int temp = 123;
   vector<int> v = {2, 4, 0};
   cout << "--------------" << endl;
   cout << calc(temp, v) << endl;
   cout << "--------------" << endl;
   */
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < limit + 1; j++){
            if(dp[i][j] == INF)continue;
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            int ny = calc(j, a[i]);
            dp[i + 1][ny] = min(dp[i + 1][ny], dp[i][j] + c[i]);
            //cout << ny << endl;
            //cout << dp[i + 1][ny] << endl;
        }
    }

    //display(dp);
    ll result = dp[n][limit];

    if(result == INF){
        cout << NIL << endl;
    }else{
        cout << result << endl;
    }
    
}