2018-07-12

SoundHound Inc. Programming Contest 2018 -Masters Tournament-: E - + Graph

https://beta.atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e

問題概要

N頂点M辺の単純連結無向グラフが与えられる。辺iには整数siが設定されている。すべての頂点にある整数を割り当てるとき、すべての辺において「辺の両端の2頂点に割り当てられた整数を足すとsiに等しい」という条件が満たされるような割り当て方は何通りあるか。

N, M <= 10⁵

解法

あるひとつの頂点に割り当てる値を仮にxとおくと、他の頂点に割り当てるべき値は必ず x+b あるいは -x+b という形になる。というわけでまずはDFSなりBFSなりで各頂点のこの一次式の形を求める。場合によっては途中で矛盾が生じるかもしれないが（その場合答えは0通り）、ここでやり始めるとごちゃごちゃするので自分の実装ではとりあえず最初に出たパターンを割り当てて矛盾チェックは後回しにしている。

一次式の割り当てが終わったら、矛盾チェックをする。具体的には全部の辺(u, v)を見て(uに割り当てた一次式)+(vに割り当てた一次式)がsと等しくなるかを確かめる。このとき(uの一次式)と(vの一次式)のxの符号が異なれば合計は定数になり、その定数!=sであれば矛盾なので答えは0通りになる。符号が同じならば2x=hogeみたいな式になって、xが正整数にならなければ同じく0通りになる。正整数になった場合にはxがひとつに定まることになるので、後で違うxの値がでてきたらやはり矛盾で0通りになる。

仮に矛盾がなければあとはxのとりうる範囲を求めて答えとする。ある頂点の一次式が x-b の形であるならば xはbより大きくなければならず、 -x+b ならば xはb未満でなければならないので、これらからxのとりうる上限と下限が出せる。

感想

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;

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

    auto V = new Tuple!(long, long)[](N);
    fill(V, tuple(INF, INF));

    void dfs(int n, long a, long b) {
        if (V[n][0] != INF) return;
        V[n] = tuple(a, b);
        foreach (to; G[n]) {
            auto m = to[0];
            auto S = to[1];
            if (V[m][0] != INF) continue;
            dfs(m, -1*a, S-b);
        }
    }

    dfs(0, 1, 0);

    auto ans = INF;
    auto X = INF;

    foreach (i; 0..N) {
        long a1 = V[i][0];
        long b1 = V[i][1];
        foreach (e; G[i]) {
            int j = e[0];
            long S = e[1];
            long a2 = V[j][0];
            long b2 = V[j][1];
            if (a1 != a2) {
                if (b1 + b2 != S) {
                    writeln(0);
                    return;
                }
            } else if (a1 == 1) {
                long c = S - b1 - b2;
                if (c % 2 || c < 0) {
                    writeln(0);
                    return;
                }
                auto x = c / 2;
                if (X == INF || X == x) {
                    X = x, ans = 1;
                } else {
                    writeln(0);
                    return;
                }
            } else {
                long c = S - b1 - b2;
                if (c % 2 || c > 0) {
                    writeln(0);
                    return;
                }
                auto x = -c / 2;
                if (X == INF || X == x) {
                    X = x, ans = 1;
                } else {
                    writeln(0);
                    return;
                }
            }
        }
    }

    long lo = 1;
    long hi = INF;

    foreach (i; 0..N) {
        long b = V[i][1];
        if (V[i][0] == 1 && b < 0) {
            lo = max(lo, -b + 1);
        } else if (V[i][0] == -1 && b > 0) {
            hi = min(hi, b - 1);
        }
    }

    ans = min(ans, hi - lo + 1);
    ans = max(0, ans);
    ans.writeln;
}

2018-07-12

AtCoder Grand Contest 012: D - Colorful Balls

問題記録 AtCoder AGC AGC #012

https://beta.atcoder.jp/contests/agc012/tasks/agc012_d

問題概要

N個のボールが一列に並んでおり、各ボールには色と重さが設定されている。色が同じで合計の重さがX以下のボール2つの位置を入れ替える操作と、色が異なって合計の重さがY以下のボール2つの位置を入れ替える操作という2つの操作を好きな順序で何回でも行うことができる。最終的なボールの色の並びとしてありうるものは何通りか。

N <= 2*10⁵

解法

まず重要な点として入れ替え操作には推移的な関係がある。つまりボールAとボールBが入れ替え可能かつボールBとボールCが入れ替え可能であるならば、ボールAとボールCは（直接的には不可能でも）実質的に入れ替え可能とみなすことができる。（たとえばABCのような並びの場合、ABC->BAC->CAB->CBA のように交換していくことができ、最初と最後だけ見ればAとCを直接交換しているのと変わりがない）

このことを念頭におくと入替可能なボール同士はひとつのグループにまとめていくことができる(union-findのuniteのようなイメージ）。このようなグループ分けをすると「ひとつのグループ内でのボール移動は完全に自由」「異なるグループ間でのボール移動はありえない」ということがいえるので、あとは単なる組合せの問題になる（色a, b, cのボールがそれぞれx, y, z個ある。並び替え方は何通りか？）。

以上よりあとはグループ分けの仕方だけが問題となるが、これを効率的にやるためには各色の一番軽いボールに注目するとよい。入替の条件は重さの和なので、たとえば「色aの中で一番軽いボール」との入替が不可能ならば、当然それより重い同色のボールとの入替も不可能である。またこのように考えると、実は「異なる複数の色のボールを含みうるグループは高々1つである」ということも言える。全体の中で最も軽いボール(Aとする）の色がaだったとしたとき、a以外のボールが異なる色と繋がれるならば必ずAと繋がれることになるし、Aと同じ色のAより重いボールが異なる色と繋がれるならAも必ずそれと繋がれるからである。

というわけで答えは

同色の中で最も軽いボールとの和がX以下ならグループに入れる
異色の中で最も軽いボールとの和がY以下ならグループに入れる

という計算を行い、できたグループの中での色の並び替えを数えればよいということになる。

感想

最初不可能にしか見えなかったけどがんばったらできた

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

void main() {
    auto s = readln.split.map!(to!long);
    auto N = s[0].to!int;
    auto X = s[1];
    auto Y = s[2];
    auto A = new long[][](N);
    foreach (i; 0..N) {
        s = readln.split.map!(to!long);
        A[s[0].to!int-1] ~= s[1];
    }

    A = A.filter!(a => !a.empty).array;
    int M = A.length.to!int;
    
    foreach (i; 0..M) {
        A[i].sort!"a < b";
    }
    A.sort!"a[0] < b[0]";

    
    int[] B;
    
    foreach (i; 0..M) {
        if (i >= 1 && A[i][0] + A[0][0] > Y) {
            break;
        }
        
        int cnt = 1;
        long second = A.length > 1 ? A[1][0] : 1L<<59;
        
        foreach (j; 1..A[i].length) {
            if (i == 0) {
                if (A[i][0] + A[i][j] <= X || second + A[i][j] <= Y) {
                    ++cnt;
                }
            } else {
                if (A[i][0] + A[i][j] <= X || A[0][0] + A[i][j] <= Y) {
                    ++cnt;
                }
            }
        }
        B ~= cnt;
    }


    auto F = new long[](N+1);
    F[0] = 1;
    foreach (i; 0..N) {
        F[i+1] = F[i] * (i + 1) % MOD;
    }

    long ans = F[B.sum];
    foreach (b; B) {
        ans = ans * powmod(F[b], MOD-2, MOD) % 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;
}

2018-06-14

yukicoder No.95 Alice and Graph

yukicoder 問題記録

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

問題概要

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

N <= 60

M <= N(N-1)/2

K <= 15

解法

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

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

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

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

2018-06-08

AtCoder Regular Contest 093: E - Bichrome Spanning Tree

問題記録 AtCoder ARC ARC #093 最小全域木

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

2018-05-25

AtCoder Regular Contest 067: F - Yakiniku Restaurants

AtCoder 問題記録 ARC ARC #067

問題概要

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

N <= 5×10³

M <= 200

解法

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

愚直に上の値を求めようとすると「各チケットごとの区間[l, r]での最大値」の部分がネックになる。区間の個数はO(N²)でありチケットの種類はM個あるため一個一個求めていく方法ではどう頑張ってもO(MN²)はかかってしまうためである。なのでここを何とかして高速にやる必要がある。以下ではこの値を 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(N²)かかるが途中の一回一回の長方形への足し算はO(1)で可能になる。よってこれでひとつのチケットにおけるすべての区間での最大値をO(N²)で求めO(1)で参照できるようになった。さらに各チケットのスコアはただ足し算すればいいだけなので、ひとつの2次元テーブルで同じ加算をいっしょくたにやってしまっていい。これで全部のチケットを合わせた結果も同様の計算量で求まることになる。

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

感想

どの解説漁っても突然いもす法が出てくるので？？？？（？？？？？？？？？？）になってたが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));
        }
    }
}

2018-05-24

NJPC2017: F - ダブルス

問題記録 AtCoder NJPC NJPC2017

問題概要

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

N <= 10⁵

解法

二分探索をし、二分探索の中で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);
}

2018-05-14

AtCoder Regular Contest 097: E - Sorted and Sorted

問題記録 AtCoder ARC ARC #097

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(N²)で求められる。あとはO(N²)で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;
}