AtCoder Beginner Contest 431 【ABC 431】 A ~ D

AtCoder Beginner Contest 431に参加しました。
パフォーマンス 721
レーティング 1124 → 1090 (-34)　となりました。
D問題で配列をN個持ってしまい、MLEになったまま終わってしまいました。

A - Robot Balance

答えは $\max(H - B, \, 0)$ です。

cpp

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

int main() {
    int H, B;
    cin >> H >> B;
    cout << max(H - B, 0) << endl;
}

B - Robot Weight

$a[i]$ を 種類 $i$ がついているとき、 $1$ ついていないとき $-1$ とします。
$i$ 番目のクエリは次のように処理できます。

• $a[P] \leftarrow -a[P]$
• $X \leftarrow X + W[P] \, \cdot \, a[P]$

これを実装すればよいです。

cpp

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

int main() {
    int X, N;
    cin >> X >> N;
    vector<int> W(N), a(N, -1);
    for (int i = 0; i < N; i++) cin >> W[i];
    int Q;
    cin >> Q;
    while (Q--) {
        int P;
        cin >> P;
        P--;
        a[P] *= -1;
        X += W[P] * a[P];
        cout << X << endl;
    }
}

C - Robot Factory

貪欲法で解きます。 $H$ を昇順に、 $B$ を降順にsortします。
問題文の条件を満たす必要十分条件は、

• $1 \leq i \le K$ を満たす全ての整数 $i$ について、$H[i] \leq B[K - 1 - i]$ が成り立つ　

となります。

cpp

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<int> H(N), B(M);
    for (int i = 0; i < N; i++) cin >> H[i];
    for (int i = 0; i < M; i++) cin >> B[i];
    sort(all(H));
    sort(rall(B));
    for (int i = 0; i < K; i++) {
        if (H[i] > B[K - 1 - i]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}

D - Robot Customize

動的計画法で解きます。
$dp[i][j] = \big(種類iまで用いて, (体の重さー頭の重さ) = jとなるときの嬉しさの最大値\big)$
とします。遷移は以下の通りです。

• $dp[i + 1][j + W_i] \leftarrow max(dp[i + 1][j + W_i], \, dp[i][j] + B_i)$
• $dp[i + 1][j - W_i] \leftarrow max(dp[i + 1][j - W_i], \, dp[i][j] + H_i)$

答えは、 $$\displaystyle\max_{0 \leq j \leq sum H} dp[N][j]$$
です。
$dp$ は $N \cdot sumH \leq 500 \cdot 500 \cdot 500 \leq 1.3 \cdot 10^8$ 程度で計算できるので、
この問題を解くことができました。
ただし、$j$ が負になることや、メモリ制限に注意してください。

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll LINF = 2e18;
template<typename T> bool chmax(T &a, const T &b){if(a < b){a = b; return true;} return false;}

int main() {
    int N;
    cin >> N;

    const int M = 500 * 500;
    vector<ll> dp(2 * M + 1, -LINF), ndp(2 * M + 1, -LINF);
    dp[M] = 0;
    for (int i = 0; i < N; i++) {
        ll W, H, B;
        cin >> W >> H >> B;
        ndp.assign(2 * M + 1, -LINF);
        for (int j = 0; j <= 2 * M; j++) {
            if (dp[j] == -LINF) continue;
            chmax(ndp[j + W], dp[j] + B);
            chmax(ndp[j - W], dp[j] + H); 
        }

        swap(dp, ndp);
    }

    ll ans = 0;
    for (int j = M; j <= 2 * M; j++) chmax(ans, dp[j]);
    cout << ans << endl;
}