yukicoder No.95 Alice and Graph

yukicoder 問題記録

https://yukicoder.me/problems/no/95

問題概要

N頂点M辺の無向グラフが与えられる。グラフの頂点には0～(N-1)の番号が付いている。はじめプレイヤーは頂点0にいて、一度の移動で一辺で繋がれた2頂点間を移動できる。また頂点nをはじめて訪れたとき(2n - 1)点の得点がもらえる。K回まで移動できるとき、得られる最大の得点を求めよ。

N <= 60

M <= N(N-1)/2

K <= 15

解法

実はこれは結構おなじみのパターンで、スコアがなんかのべき乗になっているような場合は貪欲に解を構成していけることが多い。ここでは 2n > 2n-1+2n-2+...+20 という関係が使える。つまり2nが取れる場合それ以下の全部を取っても2nの得点に満たないので、一番でかいやつから順番にひとつずつそれが取れるかを検討していけば最適な解が構成できる。上の不等式は2進表記で考えると直感的に理解できると思う(1000 > 0100 + 0010 + 0001)。

具体的な解法は、まず訪れる頂点集合S（初めはスタート地点の頂点0だけが入っている）を用意し、ここに新たな頂点nを加えても大丈夫かどうかを頂点番号の大きい順に見ていけばよい。もし頂点nを加えても大丈夫ならそのまま残しておけばいいし、だめなら取り除いて続行する。

ある頂点集合が条件を満たすかどうかは、K手の移動で含まれる頂点全部を回りきれるかで判定すればよい。これは巡回セールスマン問題っぽくなるが、ここでKの小ささが効いてくる。K<=15ということはスタート地点含め最大でも16頂点しか回れないということなので、以下のbitDPがO(K2 2K)で回せる。

dp(mask, i): 頂点集合maskを訪れていて、最後に訪れた頂点がiであるときの最小移動距離

感想

AtCoderで類題を踏んでいたので割とあっさりできた。最近こどふぉでも似たようなの見た気がするし結構典型？スコアが変な形してたらそれを活かすことを考えるのは鉄則っぽい

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

immutable int INF = 1 << 29;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];
    auto G = new int[][](N);
    auto D = new int[][](N, N);

    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= s[1]-1;
        G[s[1]-1] ~= s[0]-1;
    }

    foreach (i; 0..N)
        foreach (j; 0..N)
            D[i][j] = i == j ? 0 : INF;

    foreach (i; 0..N)
        foreach (j; G[i])
            D[i][j] = 1;

    foreach (i; 0..N)
        foreach (j; 0..N)
            foreach (k; 0..N)
                D[j][k] = min(D[j][k], D[j][i] + D[i][k]);

    
    bool can_travel(const int[] nodes) {
        int n = nodes.length.to!int;
        auto dp = new int[][](1<<n, n);
        foreach (i; 0..(1<<n)) fill(dp[i], INF);
        dp[1][0] = 0;

        foreach (mask; 1..(1<<n)) 
            foreach (i; 0..n) 
                if ((1 << i) & mask) 
                    foreach (j; 0..n) 
                        if (!((1 << j) & mask)) 
                            dp[mask|(1<<j)][j] = min(dp[mask|(1<<j)][j],
                                                     dp[mask][i] + D[nodes[i]][nodes[j]]);

        return dp[(1<<n)-1].reduce!min <= K;
    }

    int[] S = [0];
    
    foreach_reverse (i; 1..N) {
        S ~= i;
        if (!can_travel(S))
            S.popBack;
        if (S.length == K+1)
            break;
    }

    ulong ans = 0;
    foreach (n; S)
        ans += (1UL << n) - 1;
    ans.writeln;
}