yukicoder No.584 赤、緑、青の色塗り

yukicoder 問題記録 数え上げ

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

問題概要

1×Nのグリッドを以下のルールを守って赤、緑、青で彩色するとき、ありうる塗り方は何通りか。

  • R個のマスが赤、G個のマスが緑、B個のマスが青になるようにし、残りのマスは未彩色のまま残す
  • 3マス以上連続して色が塗られないようにする
  • 2マス以上連続して同じ色が塗られないようにする

N <= 3000

解法

正しい塗り方をすると、最終的には「2マス連続で色が塗られている箇所」「1マスだけ色が塗られている箇所」が空白マスに区切られて並んでいる形になる。

まず「2マス連続で色が塗られている箇所」が何個あるかを決めると、「1マス孤立して色が塗られている箇所」が何個あるかが決まり、さらに空白マスが何個残るかも決まる。その上でこれらの並べ方が何個あるかを考えると、「2マス」と「1マス」をそれぞれ空白の間に挿し込んでいく形になるので、(空白の数+1)C(「2マス」の数+「1マス」の数）となる。

次に並べたマスに色を塗っていくことを考える。まず赤の塗り方であるが、赤を「2マス」に何個塗って「1マス」に何個塗るかは総当たりする必要がある。なぜならどちらのマスに塗ったかによって次の色に残されるマス数が変わってくるからである（1マスの方に塗った場合は別の色で塗れない）。

こうして赤を塗ったあとは「2マス（片方が赤で塗られている）」「2マス（両方塗られていない）」「1マス（塗られていない）」の3種類のマスが残ることになる。ここに緑を塗っていくことを考えると、まず「2マス（両方塗られていない）」には必ず緑を塗る必要がある（そうしないと青で両方を塗ることになってしまう）。ゆえに緑の塗り方の総数は（「2マス（片方が赤で塗られている）」＋「1マス（塗られていない）」）から （B－「2マス（両方塗られていない）」）を選ぶ総数となる。残った青の塗り方はここまでの手続きで自動的に1通りに定まるので考慮する必要はない。

以上より、最初の2マス・1マスの取り方を総当たりするのにO(N), 赤の塗り方を総当たりするのにO(N)かかるのでO(N2)で答えが出せる。コンビネーションは前計算しておく。

感想

めっちゃ泥臭いが、一歩一歩解法を詰めていける感じで良かった

コード (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;


void main() {
    immutable int MAX = 4000;
    immutable long MOD = 10^^9+7;

    auto modinv = new long[](MAX);
    modinv[0] = modinv[1] = 1;
    foreach(i; 2..MAX) {
        modinv[i] = modinv[MOD % i] * (MOD - MOD / i) % MOD;
    }

    auto f_mod = new long[](MAX);
    auto f_modinv = new long[](MAX);
    f_mod[0] = f_mod[1] = 1;
    f_modinv[0] = f_modinv[1] = 1;

    foreach(i; 2..MAX) {
        f_mod[i] = (i * f_mod[i-1]) % MOD;
        f_modinv[i] = (modinv[i] * f_modinv[i-1]) % MOD;
    }

    long comb(int n, int k) {
        if (n < k) return 0;
        return f_mod[n] * f_modinv[n-k] % MOD * f_modinv[k] % MOD;
    }

    
    auto s = readln.split.map!(to!int);
    auto N = s[0], R = s[1], G = s[2], B = s[3];
    auto M = max(R, G, B);
    auto RGB = R + G + B;
    long ans = 0;

    foreach (two; 0..RGB/2+1) {
        auto one = RGB - two * 2;
        auto emp = N - two * 2 - one;
        if (M > two + one) continue;
        if (emp + 1 < one + two) continue;
        long tmp1 = comb(emp+1, one) * comb(emp+1-one, two) % MOD;
        foreach (i; max(0, R-one)..min(R, two)+1) {
            long tmp2 = tmp1 * comb(two, i) % MOD * comb(one, R-i) % MOD;
            int one_rest = one - (R-i);
            int two_rest = two - i;
            if (G < two_rest) continue;
            tmp2 = tmp2 * comb(one_rest + i, G - two_rest) % MOD;
            tmp2 = tmp2 * powmod(2, two, MOD);
            ans = (ans + tmp2) % 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;
}

yukicoder No.96 圏外です。

yukicoder 問題記録 凸包 最遠点対

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

問題概要

N個の中継局が二次元平面上の相異なる整数座標上に存在する。中継局と中継局は距離10以下であれば通信でき、無線機と中継局、無線機と無線機は距離1以下であれば通信できる。加えて、同じ中継局と通信できるもの同士も通信することができる。2次元平面上の任意の位置に2つの無線機を通信できるように置くとき、2つの無線機の間の距離の最大値を求めよ。

N <= 120000

-10000 <= Xi, Yi <= 10000

解法

  • 手順1. 通信できる中継局を1つのグループにまとめる
  • 手順2. 各グループの中で最遠点対を求める

まず手順1では距離が10以下という条件を満たす中継局同士をUnionFind等でまとめていく。ただし単純にすべての組の距離を求めているとO(N2)で間に合わない。ここで見るべき距離が10以下と小さいことを生かすと、ひとつの中継局においてはx, yが高々-10～10の正方形の範囲に存在する中継局との距離だけを調べれば十分であることがわかる。これは各中継局をx座標ごとにバケット分けした上で各バケットをy座標でソートしたりしておけば、二分探索でO(NlogN)でできる（具体的には(x-10)～(x+10)のバケットそれぞれにおいて、二分探索で(y-10)以上の最初の点を見つけて、y+10を超えるまで順に距離を確かめるという手順をとればよい。中継局は整数座標かつ相異なるという条件が効いているので、実際に距離を確かめる回数はひとつの中継局につき最大でも20×20回程度に抑えられる）。

手順2では手順1で求めたグループごとに最遠点対を割り出し、その最大距離を求める。やり方としては各グループで凸包を作ってその中の点対を総当たりすればよい。x, yの取りうる範囲が狭いこと、整数座標しかありえないことから凸包はそんなに大きくならず、凸包内で二乗の総当たりをしても十分間に合う。最後に無線機2台分の距離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;

void main() {
    auto N = readln.chomp.to!int;
    auto P = N.iota.map!(_ => readln.split.map!(to!int)).map!(a => Point(a[0], a[1])).array;

    if (N == 0) {
        writeln(1);
        return;
    }

    Tuple!(int, int)[][int] X;
    foreach (i, p; P.enumerate) {
        X[p.x] ~= tuple(p.y, i.to!int);
    }
    foreach (k; X.keys) X[k].sort();

    auto uf = new UnionFind(N);
    foreach (i, p; P.enumerate) {
        foreach (dx; -10..11) {
            int nx = p.x + dx;
            if (nx !in X) continue;
            int j = X[nx].assumeSorted.lowerBound(tuple(p.y, 0)).length.to!int;
            for (int k = j; k < X[nx].length; ++k) {
                int ny = X[nx][k][0];
                if (dx * dx + (ny - p.y) * (ny - p.y) > 100) break;
                if (nx != p.x || ny != p.y) uf.unite(i.to!int, X[nx][k][1]);
            }
            for (int k = min(j, X[nx].length.to!int-1); k >= 0; --k) {
                int ny = X[nx][k][0];
                if (dx * dx + (ny - p.y) * (ny - p.y) > 100) break;
                if (nx != p.x || ny != p.y) uf.unite(i.to!int, X[nx][k][1]);            
            }
        }
    }

    int farest = 0;
    foreach (i; 0..N) {
        if (uf.groups[i].empty) continue;
        auto ch = convex_hull(uf.groups[i].map!(i => P[i]).array);
        foreach (j; 0..ch.length) {
            foreach (k; j+1..ch.length) {
                farest = max(farest, dist2(ch[j], ch[k]));
            }
        }
    }

    writefln("%.9f", sqrt(farest * 1.0L) + 2);
}

struct Point {
    int x;
    int y;
}

Point[] convex_hull(Point[] points) {
    int N = points.length.to!int;
    points.sort!((a, b) => a.x == b.x ? a.y < b.y : a.x < b.x);
    Point[] ch1, ch2;
    foreach (i; 0..N) {
        while (ch1.length >= 2 && rot(ch1[$-2], ch1[$-1], points[i]) <= 0) ch1.popBack;
        ch1 ~= points[i];
    }
    foreach_reverse (i; 0..N) {
        while (ch2.length >= 2 && rot(ch2[$-2], ch2[$-1], points[i]) <= 0) ch2.popBack;
        ch2 ~= points[i];
    }

    auto ch = ch1 ~ ch2;
    return ch.sort!((a, b) => a.x == b.x ? a.y < b.y : a.x < b.x).uniq.array;
}

int rot(Point a, Point b, Point c) {
    // a -> b -> c の向き
    // 正なら左、負なら右、0なら同一直線状
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int dist2(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

class UnionFind {
    int N;
    int[] table;
    int[][] groups;

    this(int n) {
        N = n;
        table = new int[](N);
        fill(table, -1);
        groups = new int[][](N);
        foreach (i; 0..N) groups[i] = [i];
    }

    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;
        groups[x] ~= groups[y];
        groups[y] = [];
    }
}

CODE FESTIVAL 2017 Elimination Tournament Round 1: D - Ancient Tree Record

問題記録 AtCoder CODE FESTIVAL

https://atcoder.jp/contests/cf17-tournament-round1-open/tasks/asaporo2_d

問題概要

N頂点の木とN要素の数列Sが与えられる。木のすべての辺に整数の長さを割り当てて、Siが木の頂点iとすべての頂点との最短距離の和と等しくなるようにせよ。与えられる入力においてはそのような割り当て方がただひとつ存在することが保証される。

N <= 105

解法

ある頂点の組(a, b)を結ぶ辺eに注目すると、「Saの計算過程においてe以外の辺を通る回数」と「Sbの計算過程においてe以外の辺を通る回数」は等しい。また「Saの計算過程においてeを通る回数」はaから見てbの向こう側にある頂点の数に等しく、「Sbの計算過程においてeを通る回数」はbから見てaの向こう側にある頂点の数に等しい。よってSaとSbの差を取ったあと、eを通る回数の差でそれを割ればeの長さが一意に決定できる。

一点例外として、辺eの繋ぐ頂点(a, b)が両方とも木の中心である場合は注意が必要で、この場合SaもSbもeを通る回数も同じであるため上の方法では計算できない。しかしこの場合にも他のすべての辺は上の方法で求めることができるので、先にそれらを求めておけば残る辺eもそこから計算できる。

感想

なんか解けた、嬉しい　木の問題は辺を通る回数に着目するのが重要テクのひとつっぽいですね

コード (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 N = readln.chomp.to!int;
    auto E = new Tuple!(int, int)[](N-1);
    auto G = new Tuple!(int, int)[][](N);
    foreach (i; 0..N-1) {
        auto s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, i);
        G[s[1]-1] ~= tuple(s[0]-1, i);
        E[i] = tuple(s[0]-1, s[1]-1);
    }
    auto S = readln.split.map!(to!long).array;

    if (N == 2) {
        writeln(S[0]);
        return;
    }
    
    auto depth = new int[](N);
    auto sub = new int[](N);
    auto ans = new long[](N-1);
    
    int dfs(int n, int p, int d) {
        depth[n] = d;
        foreach (m; G[n]) if (m[0] != p) sub[n] += dfs(m[0], n, d+1);
        return sub[n] + 1;
    }
    dfs(0, -1, 0);

    long dfs2(int n, int p, long d) {
        long ret = d;
        foreach (m; G[n]) if (m[0] != p) ret += dfs2(m[0], n, d+ans[m[1]]);
        return ret;
    }

    foreach (i, e; E.enumerate) {
        int a = e[0];
        int b = e[1];
        if (S[a] == S[b]) continue; 
        if (depth[a] > depth[b]) swap(a, b);
        long aa = sub[b];
        long bb = N - sub[b] - 2;
        ans[i] = (S[a] - S[b]) / (aa - bb);
    }

    foreach (i, e; E.enumerate) {
        int a = e[0];
        int b = e[1];
        if (S[a] != S[b]) continue;
        if (depth[a] > depth[b]) swap(a, b);
        long aa = dfs2(a, b, 0);
        long bb = dfs2(b, a, 0);
        long ss = aa + bb;
        ans[i] = (S[a] - ss) / (sub[b] + 1);
    }

    ans.each!writeln;
}

CODE FESTIVAL 2016 Elimination Tournament Round 1: A - グラフ / Graph

問題記録 AtCoder CODE FESTIVAL

問題概要

辺に正整数の重みが設定されたN頂点M辺の無向グラフと、Q個のクエリが与えられる。i個目のクエリでは頂点SiとTiが指定される。各クエリにおいて、「SiまたはTiを始点としたとき、集合に含まれる辺のみを使ってすべての頂点にたどりつくことができる」という条件を満たすように辺集合を選ぶとき、集合に含まれる辺の重みの和の最小値を求めよ。

N <= 4000

M <= 400000

Q <= 100000

解法

クエリ1回であれば最小全域森っぽいものを求めればいけそうだが、それを毎回計算するのは不可能である。ここで重要な発想はSiとTiを同一視して縮約しまうことである。このようにすると「SiまたはTi」という面倒な条件を考える必要がなくなり、単純に縮約後のグラフの最小全域木のコストはいくらになるか、という問題に言い換えることができる。

なおSiとTiを縮約するという操作はSi-Ti間にコスト0の辺を加えると言い換えてもここでは問題がない。後の見通しがよくなるのでここでは後者のやり方を取る。そうすると、各クエリで求める必要があるのは「元のグラフにSi-Ti間のゼロコスト辺を加えたグラフの最小全域木（のコスト）」である。これは各クエリで毎回愚直に求める必要はなく、最初に元のグラフの最小全域木さえ求めておけば簡単に求めることができる。具体的には元のグラフの最小全域木のSi-Ti間にゼロコスト辺を足す。そうするとひとつ辺が余るので取り除いて全体の重みを小さくすることができるようになる。ここで取り除くべき辺は、取り除いても連結のままになる辺のうち、コストがもっとも大きいものである。「取り除いても連結のままになる辺」は初めの最小全域木のうちSiとTiの間にある辺、つまりSi-Tiのパス上にあるいずれかの辺である。Nが小さいのでこれを毎クエリごとにO(N)で求めても十分間に合う。これでO(NQ)で解ける。

感想

縮約、結構現れるテクっぽい

コード (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;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto G = new Tuple!(int, long)[][](N);
    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);
    }

    long mst_cost = 0;
    auto H = new Tuple!(int, long)[][](N);
    auto P = new Tuple!(int, long)[](N);
    auto D = new int[](N);
    auto used = new bool[](N);
    auto q = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[2] > b[2]")();
    q.insert(tuple(-1, 0, 0L));

    while (!q.empty) {
        auto t = q.front;
        auto from = t[0];
        auto cur = t[1];
        auto d = t[2];
        q.removeFront;
        if (used[cur]) continue;
        used[cur] = true;
        mst_cost += d;
        if (from != -1) {
            H[from] ~= tuple(cur, d);
            H[cur] ~= tuple(from, d);
        }
        foreach (m; G[cur]) {
            auto tar = m[0];
            auto nd = m[1];
            if (used[tar]) continue;
            q.insert(tuple(cur, tar, nd));
        }
    }

    void dfs(int n, int p, long c, int d) {
        P[n] = tuple(p, c);
        D[n] = d;
        foreach (to; H[n]) if (to[0] != p) dfs(to[0], n, to[1], d+1);
    }

    dfs(0, -1, 0, 0);


    auto Q = readln.chomp.to!int;
    while (Q--) {
        s = readln.split.map!(to!int);
        auto a = s[0]-1;
        auto b = s[1]-1;
        if (D[a] > D[b]) swap(a, b);
        long maxv = -1;
        while (D[b] > D[a]) {
            maxv = max(maxv, P[b][1]);
            b = P[b][0];
        }
        while (a != b) {
            maxv = max(maxv, P[a][1]);
            a = P[a][0];
            maxv = max(maxv, P[b][1]);
            b = P[b][0];
        }
        writeln(mst_cost - maxv);
    }
}

CODE FESTIVAL 2016 Tournament Round 3: A - ストラックアウト / Struck Out

問題記録 AtCoder CODE FESTIVAL

問題概要

1～Nまでの番号がついたN個のパネルがある。1度のゲームではK回ボールを投げてi回目にパネルjに当てるとi×Aj点が得られ、各回の点の和が得点となる。当てたパネルを順にP1, P2, ..., PK としたとき、1 <= P(i+1) - Pi <= M という条件の下でありうる最大の得点を求めよ。

N, M <= 105

K <= min(300, N)

解法

dp(i, j): i回目にパネルjに当てたときの最大の得点

とすると、dp(i, j) = max(dp(i-1, k) for k in (j-M)～(j-1)) である。セグ木をK本持てば普通にできそうだが、それだと O(KNlongN) で2秒には間に合わない。ここでjの小さいほうから順にdpを更新していく過程を見ていると、dp(i-1)から区間を横にずらしつつ最大値を取っていく形になっていることがわかる。このような場合スライド最小値（ここでは最大値だが）のやり方が使えて、これだと計算量がならしでO(N)になる。これでlogが落ちて答えが求まる。

おまけ：スライド最大値について（たぶん俺にしかわからないので蟻本2版p300を見てください）。

  • まず両端キュー(deque)を用意する。
  • このキューには値ではなくインデックスが入る
  • このキューの並び順は、常に次の条件を満たす
    • 左にあるものほど、そのインデックスが指す要素の値が大きい
    • 要素の値の大きさが同じ場合は、左にあるものほどインデックス自体が小さい
  • この条件が満たされている場合、区間の最大値は常にキューの左端に入っているインデックスを参照することでO(1)で得ることができる
  • 既にキューがこの状態になっていると仮定して、区間を右にひとつずらすことを考えると
    • まずずれた結果区間から外れたインデックスをキューから削除する。もしキューの左端を見て、そのインデックスがそれであればそのままpopする。そうでなければそのインデックスはもうキューの中にはないので何も操作する必要がない。
    • 次に新しく加わるインデックスをキューに追加する。今度は右からキューを見ていって、キューが空になるかあるいはキューの右端インデックスの指す要素の値が新しいインデックスの要素の値より小さい間は右をpopし続ける。止まったらそこに新しいインデックスをpushする。
    • 以上の操作では各インデックスについてpushとpopが高々1回ずつしか行われないので、ならしでO(N)となる

感想

まんまとlogをつけてTLEした。ゆきことか昔のABC-Dっぽい教育的問題感がある（スライド最小値名前だけ聞いてシカトしてたので勉強になった）。このくらい狙った設定じゃないとなかなかlog付きだけ落とすぞってのは難しそう

コード (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;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];
    auto A = readln.split.map!(to!long).array;

    auto dp = new long[][](2, N);
    dp[0] = A.dup;
    int cur = 0, tar = 1;

    foreach (i; 1..K) {
        dp[tar].fill(-INF);
        auto q = new long[](2*N+10);
        int x = N/2;
        int y = N/2;
        foreach (j; i..N) {
            int a = j - M - 1;
            int b = j - 1;
            if (a >= 0 && x < y && q[x] == a) x++;
            while (x < y && dp[cur][q[y-1]] < dp[cur][b]) y--;
            q[y++] = b;
            dp[tar][j] = dp[cur][q[x]] + A[j] * (i + 1);
        }
        swap(cur, tar);
    }

    dp[cur].reduce!max.writeln;
}

CODE FESTIVAL 2016 qual A: D - マス目と整数 / Grid and Integers

問題記録 AtCoder CODE FESTIVAL

問題概要

R行C列のグリッドがある。このうちN個のマスに非負整数が書き込まれている。まだ何も書き込まれていない残りすべてのマスに対して、以下のルールを満たしながら数字を書き込むことが可能か判定せよ。ルール1: マスに書き込めるのは非負整数のみ。ルール2: どの2×2のマスを取り出しても、左上＋右下＝右上＋左下 が成り立つ。

R, C <= 105

N <= 105

解法

式変形をすると 左上－左下＝右上－右下 となる。つまりどの2つの行を取ってきても、隣り合う列の要素の差は等しい、ということになる。さらにこれを推移的に適用すると隣り合っているものだけなく、「どんな2つの列a, bに対しても、列aと列bの値の差はすべての行において等しい」（ルール2の言い換え）ということになる。

まずは上で言い換えたルールが既に書き込まれているマスの間で成り立っているかを確かめる。そのために以下のようなグラフを構築する。

  • 頂点がC個（元のマス目の列に対応）
  • ある行において列a, b (a < b)に数字が書き込まれているとき、a->b に重み(b-a)の辺を、b->aに重み-(b-a)の辺を張る

このとき全部の書き込み同士で辺を張っているとO(N2)になってしまうので、ある行に列同士で辺を張る際は、書き込まれている中での隣接列同士だけに辺を張るようにする（列1, 3, 4に書き込みがあれば1-3, 3-4だけに張って、1-4は張らない）。こうして作ったグラフにおいて、上で言い換えたルールに違反するような矛盾が生じないかをDFSで確認することができる。具体的には以下のような手順で行う。

  • 適当にDFSの始点を選ぶ。スタート時には数0を持っている。
  • ある頂点を初めて訪れたとき、持っている数をその頂点に割り当ててDFSを続行する
  • 既に訪れている頂点に再び訪れたとき、今持っている数とその頂点に割り当てられている数が同じかどうかチェックする。もし同じであればtrueを返す。もし違っていれば矛盾が生じたことになるのでfalseを返す
  • この過程においてどこかで1回でもfalseが返ってきたらそもそも書き込まれている数字の時点でルール違反のため、問題の答えはNoとなる

以上の手順によってルール2の違反がないかを確かめることができる。実際には作ったグラフは必ずしも連結ではないので、各連結成分に対しそれぞれ独立に上のDFSを行う必要がある。もしここでルール違反がなかった場合、今度はルール1の違反がないかを確認する。つまり上で求めた差分関係のルールに従ってマスを埋めていったとき、どこかで非負整数が現れないかをチェックする。これは既に書き込まれているN個のマスをそれぞれ起点として、ルールに従って埋めたとき現れる最小値が0以上であることを確かめればよい。実装では先ほどのDFSで求めた相対的な値の割り当て表を再利用して、連結成分の中の最小値ひとつをチェックするだけでよい（たとえば今見ている既に書き込まれたマスの列に割り当てられた相対値が3, 同じ連結成分の中で最小の相対値が-5のとき、実際の最小値は（マスの数字-8）になる。連結成分のまとめにはUnionFind等を使う。

感想

最初等差数列だろとか思って全然通らなかった、あとあんまりエレガント感ないけどこれでいいんかいなと思いつつ地道に考察進めて書いたのが通ってよかった

コード (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 MOD = 10^^9 + 7;


void main() {
    auto s = readln.split.map!(to!int);
    auto R = s[0];
    auto C = s[1];
    auto N = readln.chomp.to!int;
    auto A = new Tuple!(int, long)[][](R);

    foreach (i; 0..N) {
        s = readln.split.map!(to!int);
        auto r = s[0] - 1;
        auto c = s[1] - 1;
        auto a = s[2].to!long;
        A[r] ~= tuple(c, a);
    }
    foreach (i; 0..R) A[i].sort!"a[0] < b[0]";

    auto G = new Tuple!(int, long)[][](C);

    foreach (i; 0..R) {
        foreach (j; 0..A[i].length.to!int-1) {
            G[A[i][j][0]] ~= tuple(A[i][j+1][0], A[i][j+1][1] - A[i][j][1]);
            G[A[i][j+1][0]] ~= tuple(A[i][j][0], A[i][j][1] - A[i][j+1][1]);
        }
    }

    auto used = new bool[](C);
    auto vals = new long[](C);

    bool dfs(int n, long x) {
        if (used[n]) return vals[n] == x;
        used[n] = true;
        vals[n] = x;
        foreach (m; G[n]) if (!dfs(m[0], x+m[1])) return false;
        return true;
    }

    foreach (i; 0..C) if (!used[i] && !dfs(i, 0)) {writeln("No"); return;}

    used.fill(false);
    auto mins = new long[](C);
    int[] g;

    long dfs2(int n, long x) {
        if (used[n]) return x;
        x = min(x, vals[n]);
        used[n] = true;
        g ~= n;
        foreach (m; G[n]) x = min(x, dfs2(m[0], x));
        return x;
    }

    foreach (i; 0..C) {
        if (used[i]) continue;
        g = [];
        auto m = dfs2(i, 1L<<59);
        foreach (j; g) mins[j] = m;
    }

    foreach (i; 0..R) {
        foreach (a; A[i]) {
            auto m = mins[a[0]];
            auto x = a[1] - (vals[a[0]] - mins[a[0]]);
            if (x < 0) {
                writeln("No");
                return;
            }
        }
    }

    writeln("Yes");
}

天下一プログラマーコンテスト2016本戦: D - 右往左往

AtCoder 問題記録 天下一プログラマーコンテスト 天下一プログラマーコンテスト2016本戦

問題概要

N個のタスクと2つの部屋がある。タスクiは部屋1で行うとAi, 部屋2で行うとBi時間かかる。またi回目の部屋の移動には C×(i-1)+D 時間かかる。またタスクにはM個の依存関係(Xi, Yi)があり、タスクYiはタスクXiの完了後でないと行えない。初めにいる部屋とタスクを行う順番を自由に選べるとき、タスク完了までの時間を最小化せよ。

解法

dp(mask, i, j) = タスク集合maskが完了、部屋をi回移動、現在部屋jにいる、という条件の下での最小時間

でbitDPをする。O(2N×N2)でかなりギリギリだが制限時間も長めなのでたぶんこれが想定解だと思います（この問題は公式のも野良のも解説が見つけられなかった）。一点ハマったところがあって、DPの中で次にタスクxをやろうとするとき、依存関係のあるタスクが全部終わってるかを見る必要があるわけだが、これを愚直に1個1個見てるとオーダーに余計なNがひとつついて間に合わない。なので依存関係（そのタスクに取り掛かるために完了していないといけないタスク番号の集合）はbitの形で持っておいて、maskと&をとっても変化しないかでO(1)でチェックする必要がある。

感想

D言語で通せず　じゃっかんの虚無みがある

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;

int T[20][2]; 
int G[20];
int dp[1<<20][21][2];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int INF = 1 << 29;

    int N, M, C, D;
    cin >> N >> M >> C >> D;
    REP(i, N) REP(j, 2) cin >> T[i][j];
    REP(i, M) {
        int a, b; cin >> a >> b; --a; --b;
        G[b] |= (1 << a);
    }

    for (int i = 0; i < (1<<N); ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < 2; ++k)
                dp[i][j][k] = INF;
    dp[0][0][0] = dp[0][0][1] = 0;
    
    for (int mask = 0; mask < (1 << N); ++mask) {
        for (int i = 0; i < N; ++i) {
            for (int a = 0; a < 2; ++a) {
                if (dp[mask][i][a] == INF) continue;
                for (int j = 0; j < N; ++j) {
                    if (mask & (1 << j)) continue;
                    if ((mask & G[j]) != G[j]) continue;
                    for (int b = 0; b < 2; ++b) {
                        if (a == b) {
                            dp[mask|(1<<j)][i][b] = min(dp[mask|(1<<j)][i][b],
                                                        dp[mask][i][a] + T[j][b]);
                        } else if (i < N-1) {
                            dp[mask|(1<<j)][i+1][b] = min(dp[mask|(1<<j)][i+1][b],
                                                          dp[mask][i][a] + T[j][b] + C*i+D);
                        }
                    }
                }
            }
        }
    }

    int ans = INF;
    REP (i, N) REP(j, 2) ans = min(ans, dp[(1<<N)-1][i][j]);
    cout << ans << endl;
}