Code Thanks Festival 2018 G Sum of Cards

問題文

atcoder.jp

考えること

まず、k種類以上の和で最大化なので、

dp[i][j] = i番目までのカードを使ってj種類の整数を見せているときの合計の最大値

のようなDPを考えたい。しかし適当な順序でカードを見ていっても、そのとき使った整数の種類が増えるかどうかがわからないので、適切な順序で並びかえる必要がある。 そこでカードを(表面の整数)→(裏面の整数)のようにつなぐ有向辺と見てみる。 例えば

N = 4
A = (1, 2, 3, 4)
B = (2, 3, 1, 4)

みたいな組み合わせであったらグラフは下のようになる。

この辺たちにDPでうまく遷移できるような適切な順序を考えたい。 カードに現れる整数は表と裏でそれぞれ1回ずつなので、グラフの頂点の入次数と出次数は必ずそれぞれ1つ。 よってある頂点xについて、(xに入ってくる辺)→(xから出ていく辺)のような順序でグラフを見ていけば、xを使うかどうかが判定でき、使う整数の種類についてDPができる。そうすると、知りたかったカード(辺)を見る順序は下のようにループをそれぞれ一周していく形になる。

しかし、ループの最初に見る辺の出ていく側の頂点(図の頂点１のような点)はループが一周するまで使われるかわからないので場合分けによって解決する必要がある。また、DPの遷移中に使う整数の種類が増えるかの判定のために、直前に見た辺でどちら側を使ったかの情報が必要であり、正しいDPテーブルはこの２要素を考慮したdp[i][j][k][l]の形。

このDPの遷移は 見ている辺がループの最初に見る辺なのか、途中なのか、最後なのかによって場合分けしてあげればよい。 具体的には実装を参考

実装

辺の情報にループの最初か最後か途中かの情報を加えて持つと実装が楽。順序付けはDFSすればよくあとは頑張って場合分けしてDPをループで回すだけ。 ただし、DPテーブルの初期値には注意が必要で、i = 0のとき(何もカードを選んでいないとき)、何も選んでないのに1つ以上の整数を使っている場合から遷移するとまずいので

のようにする必要がある。DP配列を使いまわせば空間計算量が下がるし、初期化の時間分速くなるけどめんどくさいのでやってないしやらなくても通る。

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

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

const ll INF = 1e16;
const ll INM = 114514;
const ll MOD = 1e9 + 7;
template <typename T>
void dump(T x) { cout << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    fill((T *)array, (T *)(array + N), val);
}

ll dp[5001][5001][2][2];
int g[5002];
bool used[5002] = {};
struct edge {
    int from, to;   //表→裏のような辺
    bool first, last; //ループの最初(最後)に使う辺か？
};
vector<edge> e;

int main() {
    IOS();
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n; i++) {
        g[a[i]] = b[i];
    }
    //DFSで辺に順序付け
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            e.emplace_back(edge{i, g[i], true, g[i] == i});
            int d = g[i];
            while (d != i) {
                e.emplace_back(edge{d, g[d], false, g[d] == i});
                used[d] = true;
                d       = g[d];
            }
        }
    }
    Fill(dp, -INF);
    dp[0][0][0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= n; j++) {
            if (e[i].first) {
                ll prev  = max({dp[i][j - 1][0][0], dp[i][j - 1][0][1], 
                            dp[i][j - 1][1][0], dp[i][j - 1][0][1]});
                dp[i + 1][j][1][1] = prev + e[i].from;           //最初に表を使う
                dp[i + 1][j][0][0] = prev + e[i].to;         //最初に裏を使う
                dp[i + 1][j][1][0] = dp[i + 1][j][0][1] = -INF; //その他はありえない
            } else if (e[i].last) {
                //ループの最初に表を使ったときは最後に裏を使っても種類数は増えない
                dp[i + 1][j][1][1] = max(dp[i][j - 1][1][1], dp[i][j][1][0]) + e[i].from;
                dp[i + 1][j][0][1] = max(dp[i][j - 1][0][1], dp[i][j][0][0]) + e[i].from;
                dp[i + 1][j][1][0] = max(dp[i][j][1][0], dp[i][j][1][1]) + e[i].to;
                dp[i + 1][j][0][0] = max(dp[i][j - 1][0][0], dp[i][j - 1][0][1]) + e[i].to;
            } else {
                //直前に裏を使って表を使う時は使う種類数は増えない
                dp[i + 1][j][1][1] = max(dp[i][j][1][0], dp[i][j - 1][1][1]) + e[i].from;
                dp[i + 1][j][0][1] = max(dp[i][j][0][0], dp[i][j - 1][0][1]) + e[i].from;
                dp[i + 1][j][1][0] = max(dp[i][j - 1][1][0], dp[i][j - 1][1][1]) + e[i].to;                
                dp[i + 1][j][0][0] = max(dp[i][j - 1][0][0], dp[i][j - 1][0][1]) + e[i].to;
            }
        }
    }
    ll ans = 0;
    for (int i = k; i <= n; i++) {
        for (int j = 0; j < 2; j++) {
            for (int l = 0; l < 2; l++) {
                ans = max(ans, dp[n][i][j][l]);
            }
        }
    }
    dump(ans);

    return 0;
}

伸縮箱の提出

atcoder.jp

総評

500点にしては難しいと思う。グラフのDPは頂点に関してのDPが多いけど、これは辺に関してのDPって言えるかな。editorialの後半読んでも意味わからなかったです、わかるかた教えてください