少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね！

問題へのリンク

問題概要

$N$ 個の整数 $a_{0}, a_{1}, \dots, a_{N-1}$ が黒板に書かれている (各整数は 100 桁までありうる)。

奇数の精と、偶数の精がいる。

奇数の精は、黒板に書かれている数字がすべて奇数となるようにしたい。そのために、「黒板に書かれている数字を 1 つ選び、その数字の桁を 1 つ選んで消す」という操作を、最大 $X$ 回まで実行できる。ただし、1 桁の整数に対して操作したときは、整数自体が消失するものとする。

偶数の精は、黒板に書かれている数字がすべて奇数になるのを防ぎたい。そのために、奇数の精が操作を開始する前に、予め、上述の操作を最大 $Y$ 回まで実行できる。

偶数の精がどのように予め操作したとしても、奇数の精が目的を達せられるならば "Yes" を出力し、そうでなければ "No" を出力せよ。

制約

$1 \le N, X, Y \le 100$
$1 \le a_{i} \lt 10^{100}$

考えたこと

たとえば、2122112122 という整数を考えてみよう。この整数は、

偶数の精が何もしない場合：2 回の操作で奇数にできる
偶数の精が 1 回操作する場合：3 回の操作で奇数にできる
偶数の精が 2 回操作する場合：3 回の操作で奇数にできる
偶数の精が 3 回操作する場合：5 回の操作で奇数にできる
偶数の精が 4 回操作する場合：6 回の操作で奇数にできる

というようになっている。この整数にはもともと 4 個までしか奇数を含んでいないので、偶数の精としては、 5 回以上操作する意味はない。

このように、各整数 $a_{0}, a_{1}, \dots, a_{N-1}$ に対して、次の配列を求めよう。

len[i][j] ← 整数 $a_{i}$ に対して、偶数の精が $j$ 回操作をした場合の、奇数の精の必要操作回数

DP へ

以上の前処理しておくことで、次の DP で問題が解ける。

dp[i][j] ← 整数 $a_{0}, \dots, a_{i-1}$ のみを考えて、偶数の精が合計 $j$ 回操作した場合についての、奇数の精の必要合計操作回数の最大値

DP の遷移としては、

chmax(dp[i+1][j+k], dp[i][j] + len[i][k]);

といった更新を行えばよい。

ここで、chmax(a, b) とは、a よりも b の方が大きい場合、a を b で書き換える関数であるとする。

最後に、dp[N][j] ( $j = 0, 1, \dots, Y$ ) の最大値が $X$ 以下になるかどうかを判定すればよい。

全体で計算量は $O(NY^{2})$ となる。

コード

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<string> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    
    vector<vector<int>> len(N);
    for (int i = 0; i < N; ++i) {
        reverse(a[i].begin(), a[i].end());
        a[i] += "1";
        
        int prev_odd_id = -1;
        for (int j = 0; j < a[i].size(); ++j) {
            if ((a[i][j] - '0') % 2 == 1) {
                int add = j - prev_odd_id - 1;
                if (!len[i].empty()) {
                    len[i].push_back(len[i].back() + add);
                } else {
                    len[i].push_back(add);
                }
                prev_odd_id = j;
            }
        }
    }
    
    vector<vector<int>> dp(N+1, vector<int>(Y+1, -1));
    dp[0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= Y; ++j) {
            for (int k = 0; k < len[i].size() && j + k <= Y; ++k) {
                chmax(dp[i+1][j+k], dp[i][j] + len[i][k]);
            }
        }
    }
    
    int res = 0;
    for (int j = 0; j <= Y; ++j) chmax(res, dp[N][j]);
    cout << (res > X ? "No" : "Yes") << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 0461 奇数の精と偶数の精 (PCK 2021 予選問題 9)

問題概要

制約

考えたこと

DP へ

コード