読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

RUPC2016 Day1 D : Scanner

競プロ DP

昨日解けなかったDP。

問題

AIZU ONLINE JUDGE

解法

DP。本番は貪欲法(Tを昇順にソートして、今までにかかっている時間が最小のスキャナーに順番に入れていく)で挑んだが、これは「1,2,3,4,5,6,7,8,9」というケースでWAする。(正解は15, 15, 15だが、この貪欲では14, 15, 16となってしまう)

純粋にDPを考えると、bool dp[i番目までの紙を処理したとき][1番目の和がj][2番目の和がk][3番目の和がl] = (となるような場合があるか) でループを回し、最後にdp[N][i][j][k] == trueをみたすもののうちから最小のmax(i, j, k)を見つければよいことになる。ただ、これだと50 * 2500 * 2500 * 2500となりメモリも計算量も厳しい。そこでいくつかの方法を使って計算を効率化する。

まず、終了状態(dp[N]~)において、3番目の和は1番目と2番目の和から復元可能である。よってlの添字は不要で、最後にdp[N][i][j] == trueとなるものからmax(i, j, sum(T) - i - j)を求めればよい。

また、T <= 50 という制約より、max(i, j, l)を最小化するように紙を振り分けると、上限は必ず2500 / 3ぐらいになる。よってi, jの上限は大きくても900程度で十分である。

以上を用いると、計算量を50 * 900 * 900まで削減することができ、この問題が解けた。

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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

const int MAX_N = 55;
const int MAX_S = 900;

int N;
int T[MAX_N];
bool dp[MAX_N][MAX_S][MAX_S];

signed main() {
    cin >> N;
    int sm = 0;
    rep(i, N) {
        cin >> T[i];
        sm += T[i];
    }

    rep(i, MAX_N) rep(j, MAX_S) rep(k, MAX_S) dp[i][j][k] = false;
    dp[0][0][0] = true;

    rep(i, N) {
        rep(j, MAX_S) {
            rep(k, MAX_S) {
                if (!dp[i][j][k]) continue;

                if (j + T[i] < MAX_S) {
                    dp[i + 1][j + T[i]][k] = true;    // 山1に追加
                }
                if (k + T[i] < MAX_S) {
                    dp[i + 1][j][k + T[i]] = true;    // 山2に追加
                }
                dp[i + 1][j][k] = true;               // 山3に追加
            }
        }
    }

    int mi = 99999999;
    rep(j, MAX_S) {
        rep(k, MAX_S) {
            if (dp[N][j][k]) {
                int ma = max(j, k);
                ma = max(ma, sm - j - k);
                mi = min(mi, ma);
            }
        }
    }

    cout << mi << endl;
}

人生初MLEを奪われました。