yukicoder No.95 Alice and Graph

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;
}

AtCoder Regular Contest 093: E - Bichrome Spanning Tree

https://beta.atcoder.jp/contests/arc093/tasks/arc093_c

問題概要

N頂点M辺のグラフが与えられる。各辺にはコストがある。すべての辺をそれぞれ白か黒かで塗り分けるとき、以下の条件が満たされるような塗り方は何通りあるか。条件:「白の辺も黒の辺も少なくともひとつ含むような全域木が存在し、かつその中で最小コストを持つ全域木のコストはXに等しい」

N <= 1000

M <= 2000

解法

とりあえず元のグラフの最小全域木を適当にひとつ構成し、そのコストをYとおく。

まず簡単なケースとして、Y > X ならば条件を満たす全域木は存在しない(最小全域木よりコストの小さい全域木はないので)。

次に Y = X の場合。この場合、元のグラフの最小全域木としてありえるもののうち、少なくともひとつが黒と白の辺を両方含むのであればその塗り方はOKということになる。そしてそのような塗り方は「元のグラフの最小全域木に含まれうる辺(以下 safe edge と呼ぶ)の集合のうち、少なくともひとつの辺は集合内の他の辺と異なる色で塗る」という塗り方と同じである。仮にsafe edgeのうちひとつが黒、別のひとつが白だった場合、それら2つを両方含む最小全域木が必ず構成できる。逆にすべてのsafe edgeの色が同じだった場合、本来最小全域木に含まれない辺(=使うと無駄なコストが発生する辺)を少なくともひとつ使って全域木を作らざるをえず、Y = Xという前提が崩れる。よってsafe edgeの数をかぞえてそれらがすべて同じ色にならない場合の数を数えればこのケースは過不足なく数えられる。

safe edgeの数え方だが、例えば以下のような方法がある。最初にひとつ適当につくった最小全域木におけるすべての頂点対(u, v)間で「(u, v)間のパス上に含まれる辺のうち最大のコストを持つもののコスト」(max_edge(u, v))を計算しておく。ここで元のグラフの辺(a, b)をひとつとったとき、辺のコストがmax_edge(a, b)と同じであればその辺はsafe edgeで、大きければsafe edgeではない。なぜなら辺(a, b)をつないだあとでmax_edge(a, b)にあたる辺を木から削除すれば、木の連結を保ったままコストは (追加した辺 - 削除した辺) の分増えることになるからである(差が0ならコストが増えない=最小全域木のまま)。この要領で全部の辺をチェックすればsafe edgeの数をかぞえることができる。

最後に Y < X の場合。この場合、元の最小全域木からコストが(X-Y)増えた全域木を作ることが目的になる。このための条件は結構厳しくて、まず元の最小全域木は明らかに作れてはいけないので、safe edgeは全部同じ色にする必要がある。そのうえで余分な辺が使われるように塗るわけだが、余分な辺をひとつ追加することによって全域木のコストがどれくらい増えるかというと 辺(a, b)のコスト - max_edge(a, b) である。これは「絶対使わなければいけない余分な辺(a, b)」を全域木にひとつ追加したとき、木の形を保つために元の木のパス(a, b)上の辺をひとつ落とすことになるが、落とすべき辺は明らかに最もコストの大きい辺なので、そういうことになる。しかも元の最小全域木に対して追加できる余分な辺は高々ひとつである。余分な辺を追加するためには少なくともsafe edgeは全部同色で塗った上で追加したい辺を別の色で塗る必要があるが、仮にひとつでも違う色を全域木に組み込めればあとは何の辺を使おうが自由なので、safe edgeだけを使っていくのが最適になるからである。そして追加される余分な辺も、safe edgeと違う色を持っているもののうちで edge_cost(a, b) - max_edge(a, b) がもっとも小さいものが自動的に選ばれることになる。以上より目的を達成するためには (1) safe edgeは全部同じ色で塗る (2) edge_cost(a, b) - max_edge(a, b) が X-Yより小さい辺もsafe edgeと同じ色で塗る (3) edge_cost(a, b) - max_edge(a, b) が X-Y と等しい辺のうち、少なくともひとつは safe edgeと別の色 (4) 残りの辺は自由 という4つの条件を満たすように塗ればよい、ということになる。

感想

なんかこれまで書いたブログの中で最も意味不明の怪文書になってしまった気がする

感想として問題解いてるときは最小全域木が何通り作れるか?みたいなところに思考が行ってしまったんだけどそんなことを考える必要はなく、色を塗ると自動的に全域木が決まるのでそれを数える、というのが考えるべきことだったんだなあという感じです

コード (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, std.bitmanip;

immutable long INF = 1L << 59;
immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto X = readln.chomp.to!long;
    auto G = new Tuple!(int, long)[][](N);
    auto E = new Tuple!(int, int, long)[](M);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, s[2].to!long);
        G[s[1]-1] ~= tuple(s[0]-1, s[2].to!long);
        E[i] = tuple(s[0]-1, s[1]-1, s[2].to!long);
    }
    auto T = new Tuple!(int, long)[][](N);

    E.sort!"a[2] < b[2]"();
    auto uf = new UnionFind(N);
    long mst_cost = 0;

    foreach (e; E) {
        if (uf.find(e[0]) == uf.find(e[1]))
            continue;
        T[e[0]] ~= tuple(e[1], e[2]);
        T[e[1]] ~= tuple(e[0], e[2]);
        uf.unite(e[0], e[1]);
        mst_cost += e[2];
    }

    auto max_edge_cost = new long[][](N, N);

    void dfs(int n, int p, int root, long d) {
        max_edge_cost[root][n] = d;
        foreach (e; T[n]) {
            int m = e[0];
            long c = e[1];
            if (m != p) 
                dfs(m, n, root, max(d, c));
        }
    }

    bool is_safe_edge(Tuple!(int, int, long) e) {
        return max_edge_cost[e[0]][e[1]] >= e[2];
    }

    foreach (i; 0..N)
        dfs(i, -1, i, 0);
    long ans = 0;

    if (mst_cost == X) {
        long safe_edges_cnt = E.map!(e => is_safe_edge(e)).sum;
        ans = (powmod(2, safe_edges_cnt, MOD) - 2) * powmod(2, M - safe_edges_cnt, MOD) % MOD; 
        ans = (ans + MOD) % MOD;
    } else if (mst_cost < X) {
        long diff = X - mst_cost;
        long a = E.map!(e => e[2] - max_edge_cost[e[0]][e[1]] < diff).sum;
        long b = E.map!(e => e[2] - max_edge_cost[e[0]][e[1]] == diff).sum;
        long c = E.map!(e => e[2] - max_edge_cost[e[0]][e[1]] > diff).sum;
        ans = 2 * (powmod(2, b, MOD) - 1) % MOD * powmod(2, c, MOD) % MOD;
        ans = (ans + MOD) % MOD;
    }

    ans.writeln;
}


class UnionFind {
    int N;
    int[] table;

    this(int n) {
        N = n;
        table = new int[](N);
        fill(table, -1);
    }

    int find(int x) {
        return table[x] < 0 ? x : (table[x] = find(table[x]));
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (table[x] > table[y]) swap(x, y);
        table[x] += table[y];
        table[y] = x;
    }
}


long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

AtCoder Regular Contest 067: F - Yakiniku Restaurants

問題概要

N軒の焼肉屋が横一直線に並んでおり、それぞれの間の距離は数列Aで表される。またM枚のチケットを1枚ずつ持っており、チケットjを焼肉屋iがある地点で使うことでB(i, j)の幸福度を得ることができる。好きな地点からスタートして自由に移動してチケットを使うとき、(得られる幸福度 - 移動距離の和) の最大値を求めよ。

N <= 5×103

M <= 200

解法

訪れる区間を固定して考える。訪れる中で最も左にある焼肉屋をl, 最も右にある焼肉屋をrとすると、求めるスコアは(各チケットごとの区間[l, r]での最大値)の和 -(lからrまでの距離)となる(単純に端から端へ移動しながら区間内の一番高いところでチケットを使えばいいので)。

愚直に上の値を求めようとすると「各チケットごとの区間[l, r]での最大値」の部分がネックになる。区間の個数はO(N2)でありチケットの種類はM個あるため一個一個求めていく方法ではどう頑張ってもO(MN2)はかかってしまうためである。なのでここを何とかして高速にやる必要がある。以下ではこの値を max[l][r] = 区間[l, r]におけるそのチケットの最大値 とおく。

ここであるチケットがとりうる最大値を考えてみる。もしあるチケットが焼肉屋xで最大値vを取るのであれば、xを含むどの区間[l, r]においてもmax[l][r]は全部vになるはずである。この手続で「xを含む区間」の最大値は全部わかるので、次はxを含まない区間[1, x)と(x, N]で同じ手続きを行う。……というように区間を分割しながら再帰的に同様の手続きを続けていくと、最終的に全部の区間の最大値を埋めることができる。そしてこの一連の手続きは必ずN回で終了する。なぜなら一回の手続で区間内から必ずひとつインデックスが消えるからである。

このように上の手続自体はN回で済むので、1回の手続にかかる計算量を抑えることができればmax[l][r]のテーブルを埋めることができる。まず必要な処理は「指定された区間の中で最大の値をもつインデックスを取得する」で、これはおなじみのRMQを用いれば1回につきO(logN)で済む。難しいのがもうひとつの処理「区間[l, r]で最大値vをとるインデックスxについて、[l, r]内でxを含むすべての区間に値vを割り当てる」だが、これはmax[l][r]のテーブルを2次元的に考えることでうまくやることができる。実はこの2次元テーブルにおいては、「区間[i, j]においてインデックスxを含むようなすべての区間」は長方形の形をとる。

f:id:fluffyowl:20180525192744p:plain

上図は区間[0, 6]で最大値をとるインデックスが仮に4だった場合を示している。ここで「インデックス4を含むすべての区間」は図で青く塗ってある部分に等しい。つまりこの部分の長方形に一様にインデックス4での値を足すことができればよく、それを効率的に行えるアルゴリズムが存在する。いもす法である。これに関しては御本人の解説がそれそのものなので参照されたい。とにかくこれを使うと最後にテーブルの累積和をとる部分でO(N2)かかるが途中の一回一回の長方形への足し算はO(1)で可能になる。よってこれでひとつのチケットにおけるすべての区間での最大値をO(N2)で求めO(1)で参照できるようになった。さらに各チケットのスコアはただ足し算すればいいだけなので、ひとつの2次元テーブルで同じ加算をいっしょくたにやってしまっていい。これで全部のチケットを合わせた結果も同様の計算量で求まることになる。

求めたい値は (各チケットごとの区間[l, r]での最大値)の和 -(lからrまでの距離)であった。これの前者は今まで述べてきたとおりO(1)で参照することができるようになり、後者は単純な累積和でこれも参照O(1)なので、区間をO(N2)で全探索しても十分間に合うことになる。

感想

どの解説漁っても突然いもす法が出てくるので????(??????????)になってたがpekempeyさんの記事の表とにらめっこしてやっと理解できた。なんかすごい汎用性ありそうなテクだ

コード (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, std.bitmanip;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto A = readln.split.map!(to!long).array;
    auto B = N.iota.map!(_ => readln.split.map!(to!long).array).array;
    auto C = new long[](N);
    foreach (i; 0..N-1) C[i+1] = C[i] + A[i];

    auto table = new long[][](N+1, N+1);
    auto st = new SegmentTree!(Tuple!(long, int), (a, b) => max(a, b), tuple(-(1L<<59), -1))(N);
    auto stack = new Tuple!(int, int)[](N+10);

    foreach (m; 0..M) {
        foreach (i; 0..N) st.assign(i, tuple(B[i][m], i));
        stack[0] = tuple(0, N-1);
        int sp = 0;
        while (sp >= 0) {
            auto l = stack[sp][0];
            auto r = stack[sp][1];
            sp -= 1;
            auto t = st.query(l, r);
            auto v = t[0];
            auto p = t[1];
            table[l][p] += v;
            table[l][r+1] -= v;
            table[p+1][p] -= v;
            table[p+1][r+1] += v;
            if (l <= p-1) stack[++sp] = tuple(l, p-1);
            if (r >= p+1) stack[++sp] = tuple(p+1, r);
        }
    }

    long ans = 0;
    foreach (i; 0..N) foreach (j; 0..N) table[i][j+1] += table[i][j];
    foreach (j; 0..N) foreach (i; 0..N) table[i+1][j] += table[i][j];
    foreach (i; 0..N) foreach (j; i..N) ans = max(ans, table[i][j] - C[j] + C[i]);
    ans.writeln;
}


class SegmentTree(T, alias op, T e) {
    T[] table;
    int size;
    int offset;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new T[](size);
        fill(table, e);
        offset = size / 2;
    }

    void assign(int pos, T val) {
        pos += offset;
        table[pos] = val;
        while (pos > 1) {
            pos /= 2;
            table[pos] = op(table[pos*2], table[pos*2+1]);
        }
    }

    T query(int l, int r) {
        return query(l, r, 1, 0, offset-1);
    }

    T query(int l, int r, int i, int a, int b) {
        if (b < l || r < a) {
            return e;
        } else if (l <= a && b <= r) {
            return table[i];
        } else {
            return op(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b));
        }
    }
}

NJPC2017: F - ダブルス

問題概要

数直線の原点上に人が2人いる。時刻Tiに座標Xiへボールが飛んでくることを意味するN個の整数の組(Ti, Xi)が与えられる。このとき2人のうちどちらか一人が時刻Tiに座標Xiにいるとボールをキャッチすることができる。2人の移動速度をvとしたとき、すべてのボールをキャッチできる最小のvを求めよ。

N <= 105

解法

二分探索をし、二分探索の中でDPをする。i個目のボールを処理した時点で、ボールをキャッチした方の人はXiにいて、キャッチしてない方の人はある連続した区間内のどこかにいる。この区間がなるべく広くなるようキャッチの担当を割り当てた方が得であるので、以下のようなDPが立つ。

dp(i): ボールiまでを処理したとき、ボールiをキャッチしていない方の人が存在しうる最大の区間

遷移は「i個目のボールをキャッチした人が(i+1)個目もキャッチする」「i個目のボールをキャッチしなかった人が(i+1)個目をキャッチする」の2通り。ボールをキャッチしに行く人が間に合うかどうかは、二分探索で速度を決め打っていることから計算可能である。ボールをキャッチしない方の人はその分左右に膨らむことができるのでそれに基づいて区間を求める。

感想

区間が連続になる が本質っぽい(むずい)

コード (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, std.bitmanip;

void main() {
    immutable real INF = 1L << 59;
    
    auto N = readln.chomp.to!int;
    auto T = new long[](N);
    auto X = new long[](N);
    foreach (i; 0..N) {
        auto s = readln.split.map!(to!long);
        T[i] = s[0];
        X[i] = s[1];
    }

    real hi = 10^^9;
    real lo = 0;
    foreach (_; 0..100) {
        real mid = (hi + lo) / 2;
        auto dp = new Tuple!(real, real)[](N+1);
        foreach (i; 0..N+1) dp[i] = tuple(INF, -INF);
        dp[0] = tuple(0.0L, 0.0L);
        real prev_t = 0;
        real prev_x = 0;
        foreach (i; 0..N) {
            if (dp[i][0] > dp[i][1])
                break;
            real t = T[i] - prev_t;
            real x = abs(X[i] - prev_x);
            if (x <= mid * t) {
                dp[i+1][0] = min(dp[i+1][0], dp[i][0] - t * mid);
                dp[i+1][1] = max(dp[i+1][1], dp[i][1] + t * mid);
            }
            if (dp[i][0] - t * mid <= X[i] && X[i] <= dp[i][1] + t * mid) {
                dp[i+1][0] = min(dp[i+1][0], prev_x - t * mid);
                dp[i+1][1] = max(dp[i+1][1], prev_x + t * mid);
            }
            prev_t = T[i];
            prev_x = X[i];
        }
        (dp[N][0] <= dp[N][1] ? hi : lo) = mid;
    }

    writefln("%.09f", hi);
}

AtCoder Regular Contest 097: E - Sorted and Sorted

https://beta.atcoder.jp/contests/arc097/tasks/arc097_c

問題概要

1~Nの番号がついた黒いボールと1~Nの番号がついた白いボールの計2N個のボールが横一列に並んでいる。隣り合う2つのボールをスワップするという操作を行って、黒白それぞれを独立に見たときその色のボールが番号の小さい順に左から並んでいる状態にしたい。この状態を達成するための最小操作回数を求めよ。

解法

左から順番にボールを確定させていくことを考える。まず一番左に置けるのは黒1か白1のどちらかである。ここで仮に黒1を置いた場合、その次に置けるのは黒2か白1である。このように次に使えるボールは常に「黒・白それぞれの使ってないボールの中で最も若い番号のもの」ということになる。よって以下のような状態数N*NのDPが立つ。

dp(b, w): 黒のボールを番号b, 白のボールを番号wまで置いたときの最小操作回数

このDPの遷移は上で述べた通り2通り(次にb+1を置くかw+1を置くか)しかない。よってあとはこの遷移のための最小操作回数が高速にわかればこの問題が解けることになる。ここでその最小操作回数は「これから置くボールより初期位置が左にあって、かつまだ使われていないボールの数」に等しい。これは実は前計算しておくとO(1)で求まる。具体的には(b, w)の状態から次に黒(b+1)を置くとき、まだ使われていないボールというのは黒の(b+2)以上か白の(w+1)以上のボールである。これを満たすボールが自分より左に何個あるかがわかればよく、これは色ごとに累積和を取っておけばO(1)で参照することができる。

dp2(c, i, j): 色がcで番号がi以上のボールが、左からj番目までに何個出現するか

これはO(N2)で求められる。あとはO(N2)でDPを回しつつ遷移の際にこの累積和テーブルを参照して更新を行っていくと答えが求まる。

感想

こういうDPを本番に通せるようになってきてうれしいですね

コード (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, std.bitmanip, std.regex;
 
void main() {
    immutable int INF = 1 << 29;
 
    auto N = readln.chomp.to!int;
    auto A = new int[](2*N);
    auto C = new bool[](2*N);
    foreach (i; 0..2*N) {
        auto s = readln.split;
        A[i] = s[1].to!int;
        C[i] = s[0] == "B";
    }
 
    auto BR = new int[](N+1);
    auto WR = new int[](N+1);
    foreach (i; 0..2*N) {
        if (C[i]) BR[A[i]] = i;
        else      WR[A[i]] = i;
    }
 
    auto dpB = new int[][](N+1, 2*N+1); //座標jまでで、iより大きいBの数
    auto dpW = new int[][](N+1, 2*N+1); //座標jまでで、iより大きいWの数
 
    foreach (i; 0..N+1) foreach (j; 0..2*N) dpB[i][j+1] = dpB[i][j] + (C[j] && A[j] > i);
    foreach (i; 0..N+1) foreach (j; 0..2*N) dpW[i][j+1] = dpW[i][j] + (!C[j] && A[j] > i);
 
    auto dp = new int[][](N+1, N+1);
    foreach (i; 0..N+1) dp[i].fill(INF);
    dp[0][0] = 0;
 
    foreach (n; 1..2*N+1) {
        foreach (b; 0..n+1) {
            int w = n - b;
            if (b > N || w > N) {
                continue;
            }
            if (b > 0) {
                dp[b][w] = min(dp[b][w], dp[b-1][w] + dpB[b][BR[b]+1] + dpW[w][BR[b]+1]);
            }
            if (w > 0) {
                dp[b][w] = min(dp[b][w], dp[b][w-1] + dpW[w][WR[w]+1] + dpB[b][WR[w]+1]);
            }
        }
    }
 
    dp[N][N].writeln;
}

第2回 ドワンゴからの挑戦状 予選: C - メンテナンス明け

https://beta.atcoder.jp/contests/dwango2016-prelims/tasks/dwango2016qual_c

問題概要

N個の駅とM個の路線が与えられる。各路線はLi個の駅を順につないだ単純パスになっており、各辺に移動時間が設定されている。駅srcから駅dstに向かいたいが、一度だけ寝過ごす可能性があり、寝過ごした場合は路線の終点まで強制的に移動する。一度寝過ごしたあとは二度と寝過ごすことはない。寝過ごしが任意の移動時に起こりうるとき、最大の移動時間を最小化するように移動したい。そのような場合の移動時間を求めよ。

N <= 25252

各路線に含まれる駅数の和 <= 252525

解法

二分探索をする。

  • 必要な考察1. 仮に寝過ごしが発生した場合、寝過ごし後にたどり着く終点からdstまでは最小移動時間で行ける。またその最小移動時間はdstを始点にして1回ダイクストラを回せばすべての頂点に対して計算可能である。
  • 必要な考察2. まだ寝過ごしが発生していない状態である辺を使って移動するとき、「仮にその移動で寝過ごしが発生した場合のdstまでの移動時間」は考察1より確定できる。

ここで「使っていい時間の最大値」を定めると、「もしある辺を使った移動で寝過ごしが起きたとき、移動時間が設定した最大値を超えるならばその辺を使うことはできない」ということが言える。よって二分探索の各ループではsrcから普通にダイクストラを回しつつ上の方法で禁止されない辺だけを使って移動していき、最終的にdstにたどり着けるかを見ればよい。

感想

あーすごい、こうやるのかというかんじ

コード (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, std.bitmanip;

void main() {
    immutable long INF = 1L << 59;
    
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto S = s[2];
    auto T = s[3];
    auto L = new int[](M);
    auto A = new int[][](M);
    auto W = new long[][](M);
    auto G = new Tuple!(int, long, int, long)[][](N);
    foreach (i; 0..M) {
        L[i] = readln.chomp.to!int;
        A[i] = readln.split.map!(to!int).array;
        W[i] = readln.split.map!(to!long).array;
        long acm1 = W[i].sum;
        long acm2 = 0;
        foreach (j; 0..L[i]-1) {
            acm2 += W[i][j];
            G[A[i][j]] ~= tuple(A[i][j+1], W[i][j], A[i].back, acm1);
            G[A[i][j+1]] ~= tuple(A[i][j], W[i][j], A[i].front, acm2);
            acm1 -= W[i][j];
        }
    }

    auto shortest = new long[](N);
    shortest.fill(INF);
    auto pq = new BinaryHeap!(Array!(Tuple!(int, long)), "a[1] > b[1]")();
    auto dist = new long[](N);

    pq.insert(tuple(T, 0L));
    while (!pq.empty) {
        auto t = pq.front;
        auto n = t[0];
        auto d = t[1];
        pq.removeFront;
        if (shortest[n] <= d) continue;
        shortest[n] = d;
        foreach (to; G[n]) {
            auto nn = to[0];
            auto nd = d + to[1];
            if (shortest[nn] <= nd) continue;
            pq.insert(tuple(nn, nd));
        }
    }


    long hi = 10L^^15;
    long lo = 0;
    
    while (hi - lo > 1) {
        long mid = (hi + lo) / 2;
        dist.fill(INF);
        pq.clear();
        pq.insert(tuple(S, 0L));
        bool ok = false;

        while (!pq.empty) {
            auto t = pq.front;
            auto n = t[0];
            auto d = t[1];
            pq.removeFront;
            if (n == T) {
                ok = true;
                break;
            }
            if (dist[n] <= d) continue;
            dist[n] = d;
            foreach (to; G[n]) {
                auto nn = to[0];
                auto nd = d + to[1];
                auto zzz = to[2];
                auto zzz_d = d + to[3];
                if (zzz_d + shortest[zzz] > mid) continue;
                if (dist[nn] <= nd) continue;
                if (nd > mid) continue;
                pq.insert(tuple(nn, nd));
            }
        }

        if (ok) hi = mid;
        else lo = mid;

    }
    
    hi.writeln;
}

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選: C - 特別講演「括弧列と塗り分け」

https://beta.atcoder.jp/contests/discovery2016-final/tasks/discovery_2016_final_c

問題概要

対応の取れた括弧列Sと非負整数Kが与えられる。Sの各文字を赤か青の2色で塗り分けるとき、すべての対応括弧の組(S[i], S[j])について、Sの区間[i, j]において赤と青の数の差がK以内になるような塗り方は何通りあるか。

|S|, K <= 3000

解法

木DPをした。括弧Aが括弧Bを包含しているときAがBの親となるようにすると、括弧の包含関係は木になる。また互いに包含関係にない括弧同士の塗り方は題意から独立である。このことから包含関係で木を作っていくと、1個以上の木(=森)ができる。それぞれの木でDPを行った結果を掛け合わせれば答えとなる。具体的なDPは

dp(n, k): 構築した森のノードnにあたる括弧(S[i], S[j])において、Sの区間[i, j]を赤と青の差がk以下になるよう塗る塗り方の総数

を順に各ノードでやっていくわけだが、これはまず子のDP値を全部求めた上でそれを使ってノード内でDPをすると求まる。

各ノードでO(NK2)?っぽいDPをやるので全部でO(N2K2)かかりそうな気がするが、最大でも区間長×2の差しか生まれない(それ以上のkは見る必要がない)ことに気を付けて適切に枝刈りを入れるとオーダーが落ちて通る。こういう感じの木DPにおける典型知識らしい→参照: http://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594

感想

気を付けず適切に枝刈りを入れなかったのでTLEを出しまくった

コード (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, std.bitmanip;

void main() {
    immutable long MOD = 10^^9 + 7;
    
    auto S = readln.chomp;
    auto N = S.length.to!int;
    auto K = readln.chomp.to!int;
    K = min(K, 2*N);
    auto P = new Tuple!(int, int)[](N/2);
    auto G = new int[][](N/2);
    auto root = new bool[](N/2);
    root.fill(true);
    long inv2 = powmod(2, MOD-2, MOD);

    auto stack = new Tuple!(int, int)[](N/2);
    for (int i = 0, p = 0, sp = -1; i < N; ++i) {
        if (S[i] == '(') {
            if (sp >= 0) G[stack[sp][1]] ~= p, root[p] = false;
            stack[++sp] = tuple(i, p++);
        } else {
            P[stack[sp][1]] = tuple(stack[sp][0], i);
            sp--;
        }
    }

    auto dp = new long[][](N/2, K+1);
    auto tmp = new long[][](2, N+1);
    
    void dfs(int n) {
        foreach (m; G[n]) dfs(m);

        int M = P[n][1] - P[n][0] + 1;
        tmp[0].fill(0);
        tmp[1].fill(0);
        
        tmp[0][0] = 2;
        tmp[0][1] = 2;
        int cur = 0, tar = 1;
        
        foreach (m; G[n]) {
            tmp[tar].fill(0);
            for (int i = 0; i <= M; ++i) {
                if (tmp[cur][i] == 0) continue;
                for (int j = 0; j <= K/2 && i+j <= M && dp[m][j] > 0; ++j) {
                    (tmp[tar][i+j] += tmp[cur][i] * dp[m][j] % MOD * inv2 % MOD) %= MOD;
                }
                for (int j = 0; j <= K/2 && abs(i-j) <= M && dp[m][j] > 0; ++j) {
                    (tmp[tar][abs(i-j)] += tmp[cur][i] * dp[m][j] % MOD * inv2 % MOD) %= MOD;
                }
            }
            swap(cur, tar);
        }

        for (int i = 0; i <= K/2; ++i) dp[n][i] = tmp[cur][i];
    }

    
    long ans = 1;
    foreach (i; 0..N/2) {
        if (!root[i]) continue;
        dfs(i);
        long t = 0;
        foreach (j; 0..K/2+1) t = (t + dp[i][j]) % MOD;
        ans = ans * t % MOD;
    }

    ans.writeln;
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}