公式解説

imoscon_c 解説

解法

問題を以下のように言い換える．以降ではこの言い換えた問題を解くことについて考える．

問題 - 言い換え

長さ $2 \cdot 10^5$ の非負整数列 $X$ が与えられます．
数列 $X$ に以下の操作を施すことですべての要素を $0$ にすることができるか判定してください．
ただし，操作 $3$ はそれぞれ $1$ 回ずつしか行うことができません．行わなくても構いません．

• 操作 $1$ : 任意の整数 $i (1 \leq i \leq 199998)$ を $1$ つ選び，$X_i, X_{i+1}, X_{i+2}$ をそれぞれ $1$ 減らす
• 操作 $2$ : 任意の整数 $i (1 \leq i \leq 200000)$ を $1$ つ選び，$X_i$ を $3$ 減らす
• 操作 $3.1$ : 任意の整数 $i (1 \leq i \leq 200000)$ を $1$ つ選び，$X_i$ を $1$ 減らす
• 操作 $3.2$ : 任意の整数 $i (1 \leq i \leq 200000)$ を $1$ つ選び，$X_i$ を $2$ 減らす
• 操作 $3.3$ : 任意の整数 $i (1 \leq i \leq 200000)$ を $1$ つ選び，$X_i$ を $1$ 増やす

この言い換えは，もともとの問題文で与えられる数列 $A$ に関して，$X_i = ($数列 $A_i$ に含まれる $i$ の個数$)$ を満たすように数列 $X$ を構成することで，操作らが問題の条件と対応づけることができるので，正当である．

ここで，dpテーブルを考える．
... 記述中です！更新をお待ちください

回答例(C++)

#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> vec(200'000, 0);
    rep(i, 3 * n + 2) {
        int x;
        cin >> x;
        vec[x - 1] += 1;
    }
    vector<int> pm = {0, -2, -1, -3, 1, -1, 0, -2};
    vector<vector<int>> trans = {
        {0, 1, 2, 3, 4, 5, 6, 7}, 
        {1, 3, 5, 7}, 
        {2, 3, 6, 7}, 
        {3, 7}, 
        {4, 5, 6, 7}, 
        {5, 7}, 
        {6, 7}, 
        {7}
    };
    vector<vector<vector<bool>>> dp(8, vector<vector<bool>>(200'001, vector<bool>(9, false)));
    dp[0][0][0] = true;
    rep(j, 200'000) {
        rep(i, 8) {
            rep(k, 9) {
                if (dp[i][j][k]) {
                    for (auto next : trans[i]) {
                        int now = vec[j] + pm[next] - pm[i] - k / 3 - k % 3;
                        if (now < 0) continue;
                        dp[next][j + 1][3 * (k % 3) + now % 3] = true;
                    }
                }
            }
        }
    }
    if (dp[1][200'000][0] || dp[7][200'000][0]) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}
Copy

回答例(Python)

準備中！
Copy