2019-01-24

AtCoder Regular Contest 020: D - お菓子の国の旅行

問題記録 AtCoder ARC #020 DP bitDP ARC

https://atcoder.jp/contests/arc020/tasks/arc020_4

問題概要

N個の町があり、隣り合う町同士は道で結ばれている。町iと町(i+1)を結ぶ距離はDiとして与えられる。いまN個の町からK個の町を選び順に移動していくことを考える。このとき訪れる町に重複があってはならず、町から町への移動は必ず最短距離で行わなければならない。ただし始点と終点はどのように選んでもよい。このルールを守って移動する町の列を決めるとき、移動距離の合計がMの倍数となるようなものは何通りあるか求めよ。

N <= 100

M <= 30

K <= 10

解法

あるひとつの道に着目してその道が移動に何回使われるかということを考える。もし今見ている道が町3と町4を繋ぐものだった場合、その道が使われるのは(3以下の町→4以上の町)の移動と(4以上の町→3以下の町)の移動の2パターンである。つまり移動する町の列が与えられたとき、列の中で隣り合う2つの町のうち片方が3以下で片方が4以上となっている部分の数を数えればその道が使われる回数を出すことが出来る。例えばK=5で(5, 9, 1, 4, 3)の順に移動するとき、9->1, 1->4, 4->3 の移動で道3をまたぐので、道3は3回使われるということがわかる。

これをすべてのありうる移動列ごとに計算していけば当然答えは出せるが、移動列は最大で100C10*10!とかのパターンがあるのでまったく間に合わない。そこでさっきの考察に立ち戻ると、町iと町(i+1)を結ぶのコスト計算で必要なのは移動列そのものではなく「移動列に含まれる町のそれぞれが道の左にあるか右にあるか」という情報だけであった。このことを使うと移動列は愚直に持つ必要がなく、「左か右か」の情報だけを持ったbit列に潰すことができる。例えば先程と同じくK=5で移動列が(5, 9, 1, 4, 3)のとき、道3から見たこの移動列は(0, 0, 1, 0, 1)になる（道3より左の町を1, 右の町を0としている）。この形にしてしまっても、道が使われるのは 0 -> 1 への移動が行われる場所と 1 -> 0 への移動が行われる箇所だけということが依然としてわかるので、コストの計算は問題なく行うことができる。

以上を踏まえると、以下のようなbitDPを行うことができる。

dp(i, mask, m): i番目までの道までを見ていて、現在の道から見た移動列がmask(ビット列)で表され、コストの合計が m (MOD M) であるような場合の数

このDPの状態数はO(N * 2^K * M)である。iからi+1への遷移ではmaskはそのまま維持されるか、どこかに1がひとつ増えることになる。例えば(5, 9, 4, 1, 3)の移動列は

道1から見ると (0, 0, 0, 1, 0)
道2から見ると (0, 0, 0, 1, 0)
道3から見ると (0, 0, 0, 1, 1)
道4から見ると (0, 0, 1, 1, 1)

という感じになっている。つまりmaskに1が1個増えるのは「さっきまでの道にとっては右だった町が今回の道からは左になる」パターンである。道は右にずれていくことを考えると1が減ったりすることはありえないし、同じ町には2度訪れないという制約を考えると1がいきなり2個以上増えたりしないこともわかる。この遷移はたかだかO(K)なので、状態数と併せてもO(NKM * 2^K)で十分間に合う計算量になる。

感想

公式解説では何をどうbit列にしてるのかよくわからなかったのでkmjpさんのブログを見ました。木の問題とかを思うとひとつの辺に注目するというテク自体はそんなに突拍子がないものとは感じなくなってきたのはまあ成長といえるんだろうか　結局解けてないんだけど

コード (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, core.stdc.string;

immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];
    auto A = iota(N-1).map!(_ => readln.chomp.to!int).array ~ 0;

    auto cross = new int[](1<<K);
    foreach (mask; 0..1<<K) cross[mask] = iota(K-1).map!(i => (mask & (0b11 << i)).popcnt == 1).sum;

    auto dp = new long[][][](N+1, 1<<K, M); // dp(i, mask): i番目の道まで見た / 訪問する町を順に並べた数列を「道iより左にあるか否か」でbitに変換したbitmask / コスト合計の mod M
    dp[0][0][0] = 1;

    foreach (i; 0..N) {
        foreach (mask; 0..1<<K) {
            foreach (j; 0..M) {
                int cost = (j + cross[mask] * A[i]) % M;
                (dp[i+1][mask][cost] += dp[i][mask][j]) %= MOD;
                foreach (k; 0..K) {
                    if (mask & (1<<k)) continue;
                    int nmask = mask | (1<<k);
                    int ncost = (j + cross[nmask] * A[i]) % M;
                    (dp[i+1][nmask][ncost] += dp[i][mask][j]) %= MOD;
                }
            }
        }
    }

    dp[N][(1<<K)-1][0].writeln;
}

2019-01-24

AtCoder Regular Contest 004: D - 表現の自由 ( Freedom of expression )

問題記録 AtCoder ARC ARC #004 DP 約数

https://atcoder.jp/contests/arc004/tasks/arc004_4

問題概要

整数N, Mが与えられる。NをM個の整数の積として表す方法が何通りあるか求めよ。構成要素が同じでも並び順が異なればそれぞれ1通りとして数えるものとする。

|N| <= 10⁹

M <= 10⁵

解法

掛け算の中に現れるのはNの約数だけなので、まずはこれを求めておく。その上で素朴な解答を考えると以下のようなDPが立つ。

dp(i, j): Nの約数をi回掛けていて、現在の積がjであるような場合の数

このDPでjとしてありうるのはNの約数だけである。なぜなら現在の積が一度Nの約数以外になってしまったら、それに何を掛けてももうNにはできないからである。よってNの約数の個数をKとかで表すことにすると、このDPはiの状態数がM, jの状態数がKであわせてO(MK)の状態数になる。遷移も愚直にNの約数全部で試すことにすると、DPの計算量は全体でO(MK²)になる。10⁹までの数だと約数の個数は多くて1350個くらいになる（cf. 高度合成数）ので、これは全然間に合わない。

ここでMが大きい場合ほとんどの数は1か-1になるということに注目する。たとえば1の次に小さい数である2であっても、30回かそこら掛け続けると10⁹を超えてしまう。すると残りの数は全部1か-1で埋めるしかなくなる。というわけで、まずは1と-1以外の数を使ってNを作る場合の数を求めてから、あとでそれらの残りの部分に1を埋めるやり方の総数を求める、という方法を使うことができる。

1と-1以外の数を使う場合の数を求めるパートは上述のDPをやればよい。ただし1と-1を掛けるような遷移は行わないことと、掛ける回数は最大でも30回程度でよくなったことに注意する。計算量はO(MK²)のMが30になったもので 30 * 1350² となり十分間に合う（負の約数を考慮すると4倍になるが、それでも10⁸くらいなのでそれなりの速度の言語なら問題ないはず）。

あとは各dp(i, N), dp(i, -N)に対して、余った数のぶんだけ1か-1を詰め込んでいく方法が何通りあるかを数えればよい。どれだけ余っているかはiを見ればわかる。また符号を調整する必要があるが、n個の1に対して-1にする数を奇数個選ぶ場合の数の総和と偶数個選ぶ場合の数の総和はどちらも 2 ^ (n - 1) である（二項係数の足し算）。最後に並べ替え方であるが、n個の1とM-n個のそれ以外のもの（区別しない）を並べ替えるやりかたは MCn である。これらをdp(i, N)に掛けていけばよい。

感想

公式解説へのリンクがないのでこれが想定解法なのかわからない　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;

immutable long MOD = 10^^9 + 7;

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

    if (N == 1) {
        if (M == 1) {
            writeln(1);
        } else {
            writeln(powmod(2, M-1, MOD));
        }
        return;
    }

    long[] F;
    for (long i = 1; i * i <= abs(N); ++i) {
        if (N % i == 0) {
            if (i * i == N) {
                F ~= i;
                F ~= -i;
            } else {
                F ~= i;
                F ~= N / i;
                F ~= -i;
                F ~= -(N / i);
            }
        }
    }

    F.sort!"abs(a) < abs(b)";

    int K = F.length.to!int;
    int[long] D;
    foreach (i, f; F) D[f] = i.to!int;

    const mx = 33;
    auto dp = new long[][](mx, K);
    dp[0][D[1]] = 1;

    foreach (i; 0..mx-1) {
        foreach (j; 0..K) {
            if (dp[i][j] == 0) continue;
            foreach (k; 2..K) {
                long x = F[j] * F[k];
                if (x !in D) continue;
                (dp[i+1][D[x]] += dp[i][j]) %= MOD;
            }
        }
    }

    long ans = 0;
    auto Comb = new Combination(10^^5+10);

    foreach (i; 0..min(mx, M+1)) {
        foreach (j; K-2..K) {
            if (dp[i][j] == 0) continue;
            if (i == M && F[j] == -N) continue;
            long n = M - i; // 1か-1でn個埋める
            if (n == 0) {
                ans += dp[i][j];
                ans %= MOD;
                continue;
            }
            long tmp = dp[i][j] * powmod(2, n - 1, MOD) % MOD;
            tmp = tmp * Comb.comb(M, n) % MOD;
            (ans += tmp) %= MOD;
        }
    }

    ans.writeln;
}


class Combination {
    long[] modinv;
    long[] f_mod;
    long[] f_modinv;

    this(int size) {
        modinv = new long[](size);
        modinv[0] = modinv[1] = 1;
        foreach(i; 2..size) {
            modinv[i] = modinv[MOD.to!int % i] * (MOD - MOD / i) % MOD;
        }

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

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

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

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

2019-01-22

AtCoder Regular Contest 039: D - 旅行会社高橋君

ARC #039 AtCoder 二重辺連結成分分解 LCA 問題記録 ARC

https://atcoder.jp/contests/arc039/tasks/arc039_d

問題概要

N頂点M辺の無向グラフとQ個の旅行計画が与えられる。各旅行計画は始点、中継点、終点をあらわす頂点の組(A, B, C)からなる。各旅行計画について、一度も同じ辺を通ることなく始点→中継点→終点と移動することが可能かどうかを求めよ。同じ頂点は何度通っても良い。

N <= 10⁵

M <= 2 * 10⁵

Q <= 10⁵

解法

グラフを二重辺連結成分分解し各成分をひとつの頂点と見なすと、これは各成分が元のグラフにおける橋によって繋がれた木になる（この辺の話は「二重辺連結成分分解」でググった方が早い）。

この木上で問題を考えると、木の各辺が必ず橋になっていることから、結局「始点Aが属する頂点 -> 中継点Bが属する頂点 -> 終点Cが属する頂点」の最短距離での移動が単純パスになっているか、という問題と同義である。この判定のためにLCAを使うことができる。自分は以下のような場合分けでやった。

AがCの祖先であるとき <=> LCA(A, C) = A のとき このとき条件が成り立つのは「BがAとCの間にある」、つまり「AがBの祖先であり、BがCの祖先である」ときのみである。すなわち LCA(A, B) = A かつ LCA(B, C) = B が成り立っていればよい。
CがAの祖先であるとき <=> LCA(A, C) = C のとき 1の逆をやればよい。
上記1, 2のどちらにも当てはまらないとき このときBはAかCどちらかの祖先でなくてはならず、またそうでない方とBのLCAはAとCのLCAと等しい。

まとめるとこの問題は 1. 二重辺連結成分分解をする 2. 分解後の各成分で木をつくる 3. 木に対してLCAとかをやってA->B->Cを通る単純パスが作れるかを判定するという3ステップで解くことが可能である。二重辺連結成分分解（とそれによる木の構築）の実装については例えば以下の Spaghetti Source のコードが参考になった。

（補足の追記）上の話だとA, B, Cが同じ連結成分に属している場合には必ず旅行可能である（つまり同じ二重辺連結成分内の任意の3点a, b, cに対して、a->b->cと移動するような単純パスが必ず存在する）と暗に仮定しているが、このことについての証明は公式解説に詳しい。（自分が解いたときはたぶんできるだろと思って決め打ちでやってしまったが、よく考えてみると全然自明な感じではなかった）

感想

二重辺連結成分分解のライブラリとLCAのライブラリをたまたま別件で作っていて、この問題で組み合わせて使ってみたらかなり便利だった　コードの再利用ってすごいですね　対談形式のプログラミング入門の本に出てくる人みたいな感想ですいません

コード (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 G = new UndirectedGraph(N);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        G.add_edge(s[0]-1, s[1]-1);
    }

    auto T = new BridgeBlockTree(G);
    auto L = new LCA(T.block.length.to!int, 0);

    foreach (i; 0..T.block.length.to!int) {
        foreach (j; T.adj[i]) {
            if (i < j) {
                L.add_edge(i, j);
            }
        }
    }

    bool check() {
        s = readln.split.map!(to!int);
        auto a = T.index[s[0] - 1];
        auto b = T.index[s[1] - 1];
        auto c = T.index[s[2] - 1];
        auto ab = L.lca(a, b);
        auto bc = L.lca(b, c);
        auto ca = L.lca(c, a);

        if (ca == a) {
            return ab == a && bc == b;
        } else if (ca == c) {
            return bc == c && ab == b;
        } else {
            return (ab == ca && bc == b) || (bc == ca && ab == b);
        }
    }


    auto Q = readln.chomp.to!int;

    while (Q--) {
        writeln( check ? "OK" : "NG" );
    }
}



class UndirectedGraph {
    int N;
    int[][] adj;

    this (int N) {
        this.N = N;
        adj = new int[][](N);
    }

    void add_edge(int u, int v) {
        adj[u] ~= v;
        adj[v] ~= u;
    }
}

class BridgeBlockTree : UndirectedGraph { // 二重辺連結成分分解 (橋で分解したあとの木)
    int[] index;
    int[][] block;
    Tuple!(int, int)[] bridges;

    this (UndirectedGraph g) {
        int n = 0;
        int cnt = 0;

        bridges = detect_bridges(g);
        auto is_bridge = new bool[int][](g.N);
        foreach (b; bridges) {
            is_bridge[b[0]][b[1]] = true;
            is_bridge[b[1]][b[0]] = true;
        }

        index = new int[](g.N);
        auto used = new bool[](g.N);

        void dfs(int n) {
            index[n] = block.length.to!int - 1;
            block.back ~= n;
            used[n] = true;
            foreach (m; g.adj[n]) {
                if (used[m] || m in is_bridge[n]) continue;
                dfs(m);
            }
        }

        foreach (u; 0..g.N) {
            if (used[u]) continue;
            block.length += 1;
            dfs(u);
        }

        super(block.length.to!int);

        foreach (u; 0..g.N) {
            foreach (v; g.adj[u]) {
                if (u < v && index[u] != index[v]) {
                    adj[index[u]] ~= index[v];
                    adj[index[v]] ~= index[u];
                }
            }
        }
    }

    Tuple!(int, int)[] detect_bridges(UndirectedGraph g) {
        Tuple!(int, int)[] bridges;
        int cnt = 0;
        auto ord = new int[](g.N);
        auto low = new int[](g.N);
        fill(ord, -1);
        fill(low, -1);

        void dfs(int n, int p) {
            ord[n] = low[n] = cnt++;
            foreach (m; g.adj[n]) {
                if (m == p) continue;
                if (ord[m] == -1) dfs(m, n);
                low[n] = min(low[n], low[m]);
                if (ord[n] < low[m]) bridges ~= tuple(n, m);
            }
        }

        dfs(0, -1);
        return bridges;
    }
}


class LCA {
    int n, root, lgn;
    int[][] g;
    int[] depth;
    int[][] dp;
    bool constructed = false;

    this(int n, int root) {
        this.n = n;
        this.root = root;
        lgn = bsr(n) + 3;
        g = new int[][](n);
        depth = new int[](n);
        dp = new int[][](n, lgn);
    }

    void add_edge(int u, int v) {
        g[u] ~= v;
        g[v] ~= u;
    }

    void construct() {
        auto stack = new Tuple!(int, int, int)[](n+10);
        int sp = 0;
        stack[0] = tuple(root, -1, 0);
        while (sp >= 0) {
            auto u = stack[sp][0];
            auto p = stack[sp][1];
            auto d = stack[sp][2];
            sp -= 1;
            dp[u][0] = p;
            depth[u] = d;
            foreach (v; g[u]) if (v != p) stack[++sp] = tuple(v, u, d+1);
        }

        foreach (k; 0..lgn-1)
            foreach (i; 0..n)
                dp[i][k+1] = (dp[i][k] == -1) ? -1 : dp[dp[i][k]][k];
        constructed = true;
    }

    void dfs(int u, int p, int d) {
        dp[u][0] = p;
        depth[u] = d;
        foreach (v; g[u]) if (v != p) dfs(v, u, d+1);
    }

    int lca(int a, int b) {
        if (!constructed) construct;
        if (depth[a] < depth[b]) swap(a, b);

        int diff = depth[a] - depth[b];
        foreach_reverse (i; 0..lgn) if (diff & (1<<i)) a = dp[a][i];

        if (a == b) return a;

        int K = lgn;
        while (dp[a][0] != dp[b][0]) {
            foreach_reverse (k; 0..lgn) {
                if (dp[a][k] != dp[b][k]) {
                    a = dp[a][k];
                    b = dp[b][k];
                    K = k;
                }
            }
        }

        return dp[a][0];
    }
}

2019-01-20

DISCO presents ディスカバリーチャンネルコードコンテスト2019 本戦: D - DISCO!

問題記録 AtCoder 文字列セグメントツリー DDCC DDCC2019本戦

https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d

問題概要

どの文字もDISCOの5文字のうちいずれか1文字であるような文字列Sが与えられる。この文字列に対する以下のQ個の問に答えよ。

問: Sの区間[l, r]の範囲内で長さ5の部分文字列（連続でなくともよい）を抜き出したとき、それが"DISCO"となっているようなものは何通りか。mod 2³² で答えよ。

|S| <= 10⁶

Q <= 10⁵

解法

自分がこの問題を解いたときは類題（ドワコン2018予選のC問題 k-DMC）を思い出しながら解いていた。この類題では、解法の1ステップとして以下のような小問題を解く必要があった（便宜上簡略化してます）。

問: いま見ている区間には文字Aがa個, 文字Bがb個, 部分文字列ABがc個あることがわかっている。この区間を右にひとつだけ伸ばしたとき、この数はどのように変化するか？

答:

新たな文字が"A"であれば"A"の数が1増える
新たな文字が"B"であれば"B"の数が1増え、"AB"の数が"A"の数だけ増える

後者の「"AB"の数が"A"の数だけ増える」のところは「新たにBがひとつ後ろに付け加わったのであれば、前に出てきているAの分だけABが増える」という理屈である。

ではこれを少し変化させた以下のような問題だとどうなるか。

問: 区間[x, y)の文字Aの数, 文字Bの数, 部分文字列ABの数と、区間[y, z)の文字Aの数, 文字Bの数, 部分文字列ABの数がわかっている。この2つの区間をくっつけた区間[x, z)の文字Aの数, 文字Bの数, 部分文字列ABの数はどうなっているか？

答:

[x, z)のAの数 = [x, y)のAの数 + [y, z)のAの数
[x, z)のBの数 = [x, y)のBの数 + [y, z)のBの数
[x, z)のABの数 = [x, y)のABの数 + [y, z)のABの数 + [x, y)のAの数 × [y, z)のBの数

足し算のところは元あったものをそのまま足しているだけなので問題ないと思う。また最後の掛け算も「後ろにBが付け加わると、前に出てきたAの分だけABが増える」という計算をしているだけなので、やっていることはさっきと同じである（というかそもそもさっきの問題はこの問題の特殊なパターンのひとつとみなすことができる）。

以上より、「左の区間と右の区間をあわせてひとつの区間にするとき、そこに含まれる部分文字列の数がどうなるか？」という問題に対する基本的なアイデアが得られた。上の例だと部分文字列が最大でも長さ2であるが、今回の問題のようにもう少し長いものが必要な場合でも同じことができる。たとえば左(s), 右(s)をそれぞれ左区間、右区間の部分文字列sの数であるとすると、両方をあわせた区間の部分文字列"DISC"の数は以下のように計算できる。

左("DISC") + 右("DISC") + 左("D") × 右("ISC") + 左("DI") × 右("SC") + 左("DIS") × 右("C")

このように左の区間の値と右の区間の値を合成することでより長い区間の結果を計算することができる。合成の際に変な演算をすることもないのでこれはセグメントツリーに乗せられそうだということがわかる。自分の実装では以下のような形のセグ木を作った。

各ノードは「Dの数, DIの数, DISの数, DISCの数, DISCOの数, Iの数, ISの数, ...」のように"DISCO"のありえる連続部分文字列（15通り）についてそれぞれ何個あるかを配列とかで持っておく。
上の"DISC"の計算式の例のように左と右を合成したときどうなるかの計算式を15通りすべてに対して気合で書いてmerge関数を作り、セグ木の区間のマージをそれでやるようにする(コード参照)。

あとはこのセグ木に区間クエリを投げて、帰ってきた結果から"DISCO"の数にあたる部分を答えればよい。

実装上の細かい点として、この問題ではmodが2³²なので、C++であればいちいち剰余を取らずとも数をunsigned intで持っておくだけでよい（勝手にmod 2³²の値になる）。

感想

いきなりセグ木で殴る話をしてもあれなので自分の思考過程的な感じで書いてみたけど人が読んだらかなり意味不明な気がして不安になってきたそれはともかくこの問題のおかげで結構良い順位取れたのでOKです

コード (C++)

※冒頭のコメントは「セグ木のノードに持たせるvectorにおいて、何番がどの部分文字列の数に対応しているか」をメモったもの（ひどい）

#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;
typedef unsigned int uint;
typedef vector<int> VI;
typedef vector<ll> VL;

/*
  00: D
  01: DI
  02: DIS
  03: DISC
  04: DISCO
  05: I
  06: IS
  07: ISC
  08: ISCO
  09: S
  10: SC
  11: SCO
  12: C
  13: CO
  14: O
 */

const int K = 15;

vector<uint> merge(vector<uint> a, vector<uint> b) {
    vector<uint> ret = vector<uint>(K, 0);
    REP(i, K) ret[i] = a[i] + b[i];

    ret[1] += a[0] * b[5];
    ret[2] += a[0] * b[6] + a[1] * b[9];
    ret[3] += a[0] * b[7] + a[1] * b[10] + a[2] * b[12];
    ret[4] += a[0] * b[8] + a[1] * b[11] + a[2] * b[13] + a[3] * b[14];

    ret[6] += a[5] * b[9];
    ret[7] += a[5] * b[10] + a[6] * b[12];
    ret[8] += a[5] * b[11] + a[6] * b[13] + a[7] * b[14];

    ret[10] += a[9] * b[12];
    ret[11] += a[9] * b[13] + a[10] * b[14];

    ret[13] += a[12] * b[14];
    return ret;
}


class SegmentTree {
public:
    vector<vector<uint>> table;
    int size;
    int offset;

    SegmentTree(int n) {
        size = 1;
        while (size <= n) size <<= 1;
        size <<= 1;
        table = vector<vector<uint>>(size, vector<uint>(K, 0));
        offset = size / 2;
    }

    void assign(int pos, vector<uint> val) {
        pos += offset;
        table[pos] = val;
        while (pos > 1) {
            pos /= 2;
            table[pos] = merge(table[pos*2], table[pos*2+1]);
        }
    }

    vector<uint> query(int l, int r) {
        return query(l, r, 1, 0, offset-1);
    }

    vector<uint> query(int l, int r, int i, int a, int b) {
        if (b < l || r < a) {
            return vector<uint>(K, 0);
        } else if (l <= a && b <= r) {
            return table[i];
        } else {
            return merge(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b));
        }
    }
};


string S;
int N, Q;
int L[1010101];
int R[1010101];

void solve() {
    cin >> S >> Q;
    N = (int)S.size();

    SegmentTree st = SegmentTree(N);
    REP(i, N) {
        vector<uint> v = vector<uint>(K, 0);
        if (S[i] == 'D') v[0] = 1;
        else if (S[i] == 'I') v[5] = 1;
        else if (S[i] == 'S') v[9] = 1;
        else if (S[i] == 'C') v[12] = 1;
        else v[14] = 1;
        st.assign(i, v);
    }

    while (Q--) {
        int l, r; cin >> l >> r; --l, --r;
        vector<uint> v = st.query(l, r);
        cout << v[4] << "\n";
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    solve();
}

2019-01-17

DISCO presents ディスカバリーチャンネルコードコンテスト2017 本戦: C - グラフいじり

問題記録 AtCoder DDCC 有向グラフ閉路

https://atcoder.jp/contests/ddcc2017-final/tasks/ddcc2017_final_c

問題概要

N頂点M辺の強連結な重み付き有向グラフが与えられる。ひとつの辺の重みを自由に変更できるとき、グラフのすべての単純サイクルについて、サイクル内に含まれる辺の重みの和が0となるようにすることができるか判定せよ。

N <= 300

M <= N² - N

解法

ここの部分は以下の記事を言い換えてるだけなので、見ていない方はまずそちらから目を通すことをおすすめします。わかりやすいです。

まず辺の重みを変更できるという条件を一旦忘れて、辺の重みが全てそのままであるとき条件が満たせるかどうかを考える。これは実はDFS1回で判定可能である。具体的には通った辺の重みを足しながらDFSしていき、初訪問の頂点に当たったときはそのとき持っている合計重みをその頂点の値として記録しておく。訪問済みの頂点を再び訪れた場合、最初にその頂点に記録した値と現在持っている値が異なっていたら矛盾が生じるため条件は満たされない。逆にDFS全体でこのような矛盾が一度も生じなければ条件は満たされる。これはもし元の頂点に帰ってきたのであればどこかのサイクルをちょうど一回りしているはずで、サイクルをちょうど一回りしてるなら戻ってくるまでに取った重みの合計は0のはずなので、最初の値と同じでなければおかしい、という理屈である。

では辺をひとつ自由に変更できるという条件の元ではどうなるか。単純な方法として、変更する辺を総当たりするという方法が考えられる。この場合変更する辺eをひとつ決め、eが入っていく頂点を始点として上のDFSをやる。始点を固定する理由は、eを必ずサイクルの最後に訪れるようにするためである。上のDFSで矛盾が検出されるのはサイクルをちょうど一周したときで、このような始点の決め方をすればe上を移動した瞬間ちょうどサイクルができることになる。つまりeが関わっているサイクルすべてにおいて、eが最後の通る辺になる。これによって「もしe以外で矛盾が起きたらその時点でNG」「eで矛盾が起きたらちょうどよく調整が起きたことにして無視」という動きができる。これをすべての辺で試して、ひとつでもOKのものがあればOKということになる。

上の方法は辺の列挙にO(M), 1度のDFSでもO(M)かかりO(M²) = O(N⁴)となり間に合わない（DFSもO(M)なのは1度のDFSですべての辺を舐める必要があるため）。だがここである頂点vを始点とし、vに入る辺全部を変更候補として前段のDFSをやっても実は問題がない。なぜならこれらの辺は同じ単純サイクルには絶対に含まれないからである。ゆえにこのうちのひとつの辺の変更が他の辺の担当するサイクルに影響せず、独立に矛盾チェックを行うことができる。よって手続きとしては始点vを決めてDFSを行い、vに入ってくる辺で矛盾が起きたらカウントを+1し、カウントが2を超えたらNGとすればよい。もし無関係の辺で矛盾が起きたらこれまで同様即アウトとする。この方法では始点の総当たりでO(N), DFSでO(N²)の計O(N³)になるので通る。

感想

感覚でわかっても言葉で説明するのがむずい

コード (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, core.stdc.string;

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 (_; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, s[2].to!long);
    }


    auto used = new bool[](N);
    auto cost = new long[](N);
    int cnt;

    bool dfs(int n, long c, int start) {
        if (used[n]) {
            if (cost[n] == c) return true;
            if (n != start) return false;
            if (cnt == 1) return false;
            cnt += 1;
            return true;
        }
        used[n] = true;
        cost[n] = c;
        foreach (e; G[n]) {
            if (!dfs(e[0], c+e[1], start)) return false;
        }
        return true;
    }

    foreach (start; 0..N) {
        used[] = false;
        cost[] = 0;
        cnt = 0;
        if (dfs(start, 0, start)) {
            writeln("Yes");
            return;
        }
    }

    writeln("No");
}

2019-01-15

Educational DP Contest / DP まとめコンテスト: W - Intervals

問題記録 AtCoder DPまとめコンテスト DP

https://atcoder.jp/contests/dp/tasks/dp_w

問題概要

'0'と'1'のみからなる長さNの文字列を考える。M個のスコア条件(l, r, a)が与えられたとき、文字列の区間[l, r]のうち少なくとも1文字が'1'であればa点を得る。文字列を自由に構成できるとき、スコアの最大値を求めよ。

N, M <= 2*10⁵

-10⁹ <= a <= 10⁹

解法

文字列を左から構成していくものとして、以下のDPを考える。

dp(i): 最後に'1'を置いたのがi文字目であるときの最大スコア

dp[i]の値を決めるときのことを考えてみる。もしiに被っている区間が [x, y] のひとつだけで、この区間のスコアがaだったとすると、遷移は以下のようになる。

dp[i] = max( max(dp[0〜x-1] + a), max(dp[x〜i-1]) )

この式は「もし最後に1を置いたのがxより前であるなら、ここで1を置いたとき初めて[x, y]が有効になって自動的にa点が入る」と「既にx〜i-1のどこかに1を置いているのでiに新たに1を置いても何も起こらない」の2パターンを見て大きい方を取る、ということを表している。（dp[i]ではiに1を置いたときのことを考えているので、どちらが取られるにせよaの値は織り込まれているという点に注意する）

ひとつのiに対して被る区間が複数ある場合でも考え方は同じ（「区間が被らない場所から遷移してくる場合にはその区間の点数を足す」「区間が被っている場所から遷移してくる場合には点数は足さない」）。つまり現在のiに被っているすべての区間[x, y]について、dp[0] 〜 dp[x-1]に一律にその区間の点数を足しておいた上で、dp[0〜i-1]までのmaxをとるとdp[i]の値となる。

これは尺取りみたいなやつとかで現在のiに被っている区間を管理しつつ、新たな区間[x, y]が入ってきたらdp[0]〜dp[x-1]にスコアを加算する、抜ける区間があったらdp[0]〜dp[x-1]から最初に足したぶんのスコアを引く、dp[i]の値にはdp[0]〜dp[i-1]のmaxを採用する、という操作で実現できる。区間加算、区間maxができればよいので遅延セグ木とかを使えばok.

解法

kmjpさんの解説を読んで解いた。既に確定しているはずの過去の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, core.stdc.string;

immutable long INF = 1L<<59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto LRA = M.iota.map!(_ => readln.split.map!(to!int).array).array;
    LRA.sort();

    auto st = new LazySegmentTree!(long, long, max, (a,b)=>a+b, (a,b)=>a+b, (a,b)=>a, -INF, 0L)(N+1);
    st.table[] = 0L;
    auto pq = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[1] > b[1]")();

    for (int i = 1, p = 0; i <= N; ++i) {
        while (p < M && i >= LRA[p][0]) {
            pq.insert(tuple(LRA[p][0], LRA[p][1], LRA[p][2].to!long));
            st.update(0, LRA[p][0]-1, LRA[p][2].to!long);
            ++p;
        }

        auto v = st.query(0, i-1);
        st.update(i, i, v);

        while (!pq.empty && pq.front[1] <= i) {
            st.update(0, pq.front[0]-1, -pq.front[2].to!long);
            pq.removeFront;
        }
    }

    st.query(0, N).writeln;
}



class LazySegmentTree(T, L, alias opTT, alias opTL, alias opLL, alias opPrd, T eT, L eL) {
    T[] table;
    L[] lazy_;
    int n;
    int size;

    this(int n) {
        this.n = n;
        size = 1;
        while (size <= n) size <<= 1;
        size <<= 1;
        table = new T[](size);
        lazy_ = new T[](size);
        table[] = eT;
        lazy_[] = eL;
    }

    void push(int i, int a, int b) {
        if (lazy_[i] == eL) return;
        table[i] = opTL(table[i], opPrd(lazy_[i], b - a + 1));
        if (i * 2 + 1 < size) {
            lazy_[i*2] = opLL(lazy_[i*2], lazy_[i]);
            lazy_[i*2+1] = opLL(lazy_[i*2+1], lazy_[i]);
        }
        lazy_[i] = eL;
    }

    T query(int l, int r) {
        if (l > r) return eT;
        return query(l, r, 1, 0, n-1);
    }

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

    void update(int l, int r, L val) {
        if (l > r) return;
        update(l, r, 1, 0, n-1, val);
    }

    void update(int l, int r, int i, int a, int b, L val) {
        if (b < l || r < a) {
            push(i, a, b);
        } else if (l <= a && b <= r) {
            lazy_[i] = opLL(lazy_[i], val);
            push(i, a, b);
        } else {
            push(i, a, b);
            update(l, r, i*2, a, (a+b)/2, val);
            update(l, r, i*2+1, (a+b)/2+1, b, val);
            table[i] = opTT(table[i*2], table[i*2+1]);
        }
    }
}

2019-01-08

Educational DP Contest / DP まとめコンテスト: T - Permutation

問題記録 AtCoder DPまとめコンテスト DP 順列のDP

https://atcoder.jp/contests/dp/tasks/dp_t

問題概要

整数Nと長さN-1の文字列Sが与えられる。Sは'>'と'<'のみからなり、長さNの数列における隣り合う値の大小関係を表す。(1, 2, ..., N)のすべての順列のうちSの表す大小関係に従うものは何通りあるか。

N <= 3000

解法

値を左から確定させていくことを考えると、単純なDPは以下のようになる。

dp(i, j, T): i番目まで決めていて、最後に置いた値がjであり、残っている未使用の値の集合がTであるような場合の数

このとき遷移は、対応する文字が'>'であればTの中からjより小さい値を選び、'<'であればjより大きい値を選ぶ、という形になる。このことを踏まえると、ひとつ前に選んだ数字とこれから選ぶ数字の大小関係が本質的な情報である。よって状態を以下のようにまとめてしまうことができる。

dp(i, j): i番目まで決めていて、最後に置いた値が「残っている未使用の値のうちj番目に小さい値」であるような場合の数

もし直前に「残っている中で2番目に小さい値」を置いており、次の記号が'<'であるとする。すると今回置けるのは「残っている中で2番目以上の値」である（以下の画像参照）。

f:id:fluffyowl:20190108124728p:plain

このようにすると前回取った値と大小記号だけで次に取れる値が決まるのでdpを埋めていくことができる。上の例でいくと、i回目に2を置いて記号が'<'のとき、遷移は dp[i][2] を dp[i+1][2～4] に一律に足す操作となる。これは区間への加算になるが、いもす法とかでうまいことやれば i -> i+1 の遷移全体をO(N)で計算できるので、結局O(N²)で最終的な答えが出せる。

上の説明は配る視点で書いたが自分の実装ではもらうDPでやっているのでそちら視点でも一応書いておく。たとえば今回のjが3で記号が<であれば、前回のjは0〜3のどれか。よって dp[i][j] += sum(dp[i-1][0〜j]) というような遷移になる。累積和等を使えば区間sumをとる部分がO(1)で処理できるようになるのでこちらも最終的には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, core.stdc.string;

immutable long MOD = 10^^9 + 7;

void main() {
    auto N = readln.chomp.to!int;
    auto S = readln.chomp;

    auto dp = new long[][](N, N);
    dp[0][] = 1;

    foreach (i; 1..N) {
        if (S[i-1] == '>') {
            long s = dp[i-1][N-i];
            foreach_reverse (j; 0..N-i) {
                (dp[i][j] += s) %= MOD;
                (s += dp[i-1][j]) %= MOD;
            }
        } else {
            long s = dp[i-1][0];
            foreach (j; 0..N-i) {
                (dp[i][j] += s) %= MOD;
                (s += dp[i-1][j+1]) %= MOD;
            }
        }
    }

    long ans = 0;
    foreach (j; 0..N)
        (ans += dp[N-1][j]) %= MOD;
    ans.writeln;
}