2019-01-03

CODE FESTIVAL 2018 Final: G - Chicks and Cages

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_g

問題概要

N羽のひよこがいて、ひよこiの大きさはAiである。ひよこをM個のケージに分けて入れるとき、各ひよこは自分とおなじケージにいるひよこの大きさの和と等しいストレスを受ける。全ひよこのストレスの和を最小化するようにひよこを分けたとき、その最小値を求めよ。

N, M <= 2000

解法

DPをしようと思うと、以下のような形になる。

DP(i, j): i匹目までのひよこをj個のケージに分けて入れたときの最小値

このDPで遷移を普通にやろうとすると次のグループの大きさを全て見る必要があるため、累積和を使ってもO(N)かかってしまい、状態数のO(NM)と合わせてO(N² M)と厳しいオーダーになってしまう。

想定解ではこの遷移を高速化する。そのために必要なアイデアは「数の多いグループには小さいひよこを入れた方が良い」ということである。ひよこiが羽数nのケージに入った場合、最終的な値には A[i] × n が加算される。つまり全部のひよこについての A[i] × (ケージの羽数) を足した数が最終的な値ということになる。よって仮にすべてのケージの羽数が定まっているならば、A[i]の小さいひよこをnの大きいケージに貪欲に割り当てていくのが当然最適となる。つまりAを小さい順に並べて、大きいケージから順番に詰め込んでいくことになる。

以上の考察より、DPの遷移を次のとおり高速化できる。まずAを小さい順にソートする。先の考察に従えば、1つのグループはソート後のAの連続部分列になる。さらに「小さいひよこほど大きいケージへ」が最適であるため、後ろのひよこに作るケージは前に作るケージと同じサイズかもしくは小さいはずである。これによって考慮するべきケージのサイズが後半ほど枝刈りできて通るようになる（前からケージを作っていくとして、これからサイズnのケージを作るとき、これまで作ったm個のケージはすべてサイズn以上と仮定できる。ということはこれまでの割当でひよこを最低でも n * m 匹は使っているはずで、もしこの数が今見てるひよこのインデックスを追い越していたらNGなので、そのサイズ以上のケージの計算は飛ばせる）。

公式解説によると上の方法をとった場合の計算量はO(NMlogN).

感想

いや、わからん……………… 「ひよこiの寄与はA[i]*ケージのサイズ」に着目しないと始まらない感じだが、着目できていたとてDPのこういう高速化に使う発想はちょっと出てきそうにない　うぐぐ

コード

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 A = readln.split.map!(to!long).array;
    A.sort();

    auto B = new long[](N+1);
    foreach (i; 0..N) B[i+1] = B[i] + A[i];

    auto dp = new long[][](N+1, M+1);
    foreach (i; 0..N+1) fill(dp[i], 1L<<59);
    dp[0][0] = 0;

    foreach (i; 0..N) {
        foreach (j; 0..M) {
            foreach (k; i..N) {
                int size = k - i + 1;
                if (size * j > N) break;
                dp[k+1][j+1] = min(dp[k+1][j+1], dp[i][j] + (B[k+1] - B[i]) * size);
            }
        }
    }

    dp[N][M].writeln;
}

2019-01-01

SoundHound Inc. Programming Contest 2018 (春): C - 広告

問題記録 SoundHound2018春 AtCoder 2部グラフ最大安定集合

https://atcoder.jp/contests/soundhound2018/tasks/soundhound2018_c

問題概要

各マスが '*' もしくは '.' で構成されたr行c列のグリッドが与えられる。'.'のマスに広告を打てるが、広告を打ったマスの上下左右4マスには広告を打つことができなくなる。最大で何マスに広告を打つことができるか求めよ。

r, c <= 40

解法

'.'マスを頂点とし、上下左右で繋がった'.'マス間に辺を張ったグラフを考えると、問われているのは「このグラフの最大安定集合のサイズを求めよ」と同じことである。
グリッドグラフは2部グラフである。
2部グラフの最大安定集合は最大フローを用いて求めることができる。

2部グラフの最大安定集合の具体的な求め方は↓のdrkenさんのスライドを見ればわかる（ありがとうございます）。

二部グラフの最小点被覆と最大安定集合と最小辺被覆の求め方

感想

知ってればやるだけだが知らなかったのでやれなかったし記事を書いた

コード (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 H = s[0];
    auto W = s[1];
    auto A = H.iota.map!(_ => readln.chomp).array;

    auto G = new BipartiteGraph(H * W);
    int cnt = 0;

    foreach (r; 0..H) {
        foreach (c; 0..W) {
            if (A[r][c] == '*') {
                cnt += 1;
                continue;
            }
            foreach (k; 0..2) {
                int nr = r + k;
                int nc = c + 1 - k;
                if (nr >= 0 && nr < H && nc >= 0 && nc < W && A[nr][nc] == '.') {
                    G.add_edge(r * W + c, nr * W + nc);
                }
            }
        }
    }

    G.construct;
    writeln(G.maximum_independent_set.length.to!int - cnt);
}

class BipartiteGraph {
    int n;
    int[][] adj;
    bool[] color;

    this (int n) {
        this.n = n;
        adj = new int[][](n);
        color = new bool[](n);
    }

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

    bool construct() {
        auto used = new bool[](n);

        bool dfs(int u, bool c) {
            if (used[u])
                return color[u] == c;

            used[u] = true;
            color[u] = c;

            if (adj[u].map!(v => used[v] && color[v] == c).any)
                return false;
            if (adj[u].map!(v => !used[v] && !dfs(v, c^1)).any)
                return false;

            return true;
        }

        foreach (u; 0..n)
            if (!used[u] && !dfs(u, 0))
                return false;

        return true;
    }

    int[] minimum_vertex_cover() {
        int s = n;
        int t = n + 1;
        auto ff = new FordFulkerson(n + 2, s, t);
        foreach (i; 0..n) if (color[i] == 0) ff.add_edge(s, i, 1);
        foreach (i; 0..n) if (color[i] == 1) ff.add_edge(i, t, 1);
        foreach (i; 0..n) if (color[i] == 0) foreach (j; adj[i]) ff.add_edge(i, j, 1);
        ff.run;

        auto used = new bool[](n);
        auto G = new int[][](n);
        foreach (i; 0..n) if (color[i] == 1) foreach (j; adj[i])
            if (ff.flow[j][i])
                G[j] ~= i;
            else
                G[i] ~= j;

        void dfs(int u) {
            if (used[u]) return;
            used[u] = true;
            foreach (v; G[u]) dfs(v);
        }

        foreach (i; 0..n) if (!used[i] && color[i] == 0 && ff.flow[s][i]) dfs(i);

        return n.iota.filter!(i => (color[i] == 0 && !used[i]) || (color[i] == 1 && used[i])).array;
    }

    int[] maximum_independent_set() {
        int[] ret;
        int[] mvc = minimum_vertex_cover;

        if (mvc.empty)
            return n.iota.array;

        for (int i = 0, j = 0; i < n; ++i) {
            if (mvc[j] == i) {
                if (j + 1 < mvc.length)
                    ++j;
            } else {
                ret ~= i;
            }
        }

        return ret;
    }
}


class FordFulkerson {
    int N, source, sink;
    int[][] adj;
    int[][] flow;
    bool[] used;

    this(int n, int s, int t) {
        N = n;
        source = s;
        sink = t;
        assert (s >= 0 && s < N && t >= 0 && t < N);
        adj = new int[][](N);
        flow = new int[][](N, N);
        used = new bool[](N);
    }

    void add_edge(int from, int to, int cap) {
        adj[from] ~= to;
        adj[to] ~= from;
        flow[from][to] = cap;
    }

    int dfs(int v, int min_cap) {
        if (v == sink)
            return min_cap;
        if (used[v])
            return 0;
        used[v] = true;
        foreach (to; adj[v]) {
            if (!used[to] && flow[v][to] > 0) {
                auto bottleneck = dfs(to, min(min_cap, flow[v][to]));
                if (bottleneck == 0) continue;
                flow[v][to] -= bottleneck;
                flow[to][v] += bottleneck;
                return bottleneck;
            }
        }
        return 0;
    }

    int run() {
        int ret = 0;
        while (true) {
            foreach (i; 0..N) used[i] = false;
            int f = dfs(source, int.max);
            if (f > 0)
                ret += f;
            else
                return ret;
        }
    }
}

2019-01-01

AtCoder Grand Contest 029: C - Lexicographic constraints

問題記録 AtCoder AGC AGC #029 辞書順文字列

https://atcoder.jp/contests/agc029/tasks/agc029_c

問題概要

N個の文字列が順番に並んでおり、それぞれの長さが数列Aとして与えられる。すべての文字列は自分の左にある文字列より辞書順で真に小さい、という制約のもとで、そのような文字列の列が存在するか判定せよ。存在する場合には、そのような文字列の列を構成するために必要な最小の文字の種類数を求めよ。

N <= 2×10⁵

A <= 10⁹

解法

明らかに単調性があるので2分探索をする。このとき問題は「使える文字の種類数xが与えられたとき、題意を満たす文字列を作れるか」という判定問題になる。

最初の文字列から順に構成していくことを考えると、辞書順で小さい順という制約上、許される限り辞書順の小さい文字列を作っていくべきである。つまり作るべき文字列は「長さがAiかつ辞書順で前の文字列を超えないという条件を満たすもののうち、辞書順で最も小さい文字列」ということになる（ただし最初の文字列は全部aで埋めることにする）。

実際にそのような文字列を構成していく。隣り合う文字列S[i-1]とS[i]について、既にS[i-1]が定まっており、これからS[i]を決めていくものとする。このとき、A[i-1]とA[i]の大小関係から、以下のようにS[i]を決めることができる。

A[i-1] = A[i]のとき: S[i]はS[i-1]の末尾の文字をひとつインクリメントした文字列になる。もし末尾の文字がそれ以上インクリメントできないのであれば、足し算の繰り上がりのように、その桁は0に戻して隣の桁をインクリメントする。
A[i-1] > A[i]のとき: S[i-1]の長さがA[i]に一致するよう、S[i-1]の余分な末尾を切り落とした文字列Tをつくる。このときTはS[i-1]のprefixであり、このままだとS[i-1] > Tになってしまうので、↑と同じ要領でTの末尾をインクリメントし、これをS[i]とする。
A[i-1] < A[i]のとき: S[i-1]の長さがA[i]に一致するよう、S[i-1]の末尾に'a'を詰めこむ。これをS[i]とする。

もしインクリメントしたとき文字種が溢れてしまうようであれば、その文字種類数では構成不可能、ということになる。

あとはこれを実際にシミュレートしていけばよい。文字の種類数が膨大になるので、実際には文字列を扱うというよりも最大10⁹ケタのx進数(xは最大の文字種類数)を扱うような感じでやる。自分の実装では、巨大な桁数の場合にはほとんどの桁が0であるということを利用して、0でない桁だけをスタックで持つ、という感じにした。上述したとおり構成時に要求される操作は末尾を切ったりインクリメントしたりといった操作だけなので、数の任意の場所にアクセスできる必要はなく、一番うしろだけすぐ参照したり操作したりができればよいため。

感想

かなり意味わからないこと書いてるんじゃないか疑惑があってこわいね　あと自分の実装の計算量わからん

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

alias Digit = Tuple!(long, "n", long, "keta");

bool incr(ref DList!Digit queue, long keta, long base) {
    if (queue.empty || queue.back.keta != keta) {
        queue.insertBack(Digit(1L, keta));
        return true;
    } else if (queue.back.n + 1 < base) {
        queue.back.n += 1;
        return true;
    }

    long prev_keta = keta + 1;
    while (!queue.empty && queue.back.keta + 1 == prev_keta && queue.back.n + 1 == base) {
        if (queue.back.keta == 1) {
            return false;
        } else {
            prev_keta--;
            queue.removeBack;
        }
    }

    if (queue.empty || queue.back.keta + 1 != prev_keta) {
        queue.insertBack(Digit(1L, prev_keta - 1));
    } else {
        queue.back.n += 1;
    }

    return true;
}

bool check(int N, const long[] A, long base) {
    DList!Digit queue;

    foreach (i; 1..N) {
        if (A[i] > A[i-1]) {
            continue;
        }
        while (!queue.empty && queue.back.keta > A[i]) {
            queue.removeBack;
        }
        if (!incr(queue, A[i], base)) {
            return false;
        }
    }

    return true;
}

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;

    if ((N-1).iota.map!(i => A[i+1] - A[i] > 0).all) {
        writeln(1);
        return;
    }

    long hi = 10^^9 + 1;
    long lo = 1;
    while (hi - lo > 1) {
        long mid = (hi + lo) / 2;
        if (check(N, A, mid))
            hi = mid;
        else
            lo = mid;
    }

    hi.writeln;
}

2018-12-31

yukicoder No.765 ukuku 2

yukicoder 問題記録ローリングハッシュ回文文字列

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

問題概要

文字列Sが与えられる。Sから任意の1文字を削除するとき、削除後の文字列において回文となる最長連続部分文字列の長さを求めよ。

|S| <= 2 * 10⁵

解法

回文の中心となる場所を総当たりしていく。最終的な回文が奇数長の場合その中心はSのどこかの1文字に、偶数長の場合Sのどこかの2文字の間になる。

例えばSのある文字Siを中心としたとき、削除を考えずにどこまで回文となっているかを調べる。つまり中心iから左にa文字、右にa文字伸びる部分文字列S[i-a:i+a]について、これが回文であるような最大のaを求める。

iを中心としたときS[i-a:i+a]が回文であるかどうかは、S[i-a:i]とreversed(S[i:i+a])が等しいかどうかで判定できる（「回文の左半分」と「回文の右半分をひっくり返した文字列」は一致する）。これによって回文判定が同じ長さの部分文字列の比較でできるようになったので、あとはSを反転した文字列S'を用意した上でローリングハッシュの要領で前処理をして部分文字列のハッシュをとれるようにしておけば、ここの一致判定はO(1)で出来る。これで判定が高速になったので、二分探索で最大のaを求めることができる。

この後で1文字削除について考えると、↑で求めた回文をさらに長くするためには回文のすぐ左右にある邪魔な1文字のどちらかを消すしかない。また消したあとにどれだけ回文を伸ばせるかは先程の判定とまったく同じ要領の二分探索で行うことができる。

以上でO(NlogN)で解くことができた。コーナーケースっぽいものとしてSが既に回文になっている場合があるが、この場合Sの真ん中の文字を消すことで必ず長さN-1の回文が作れるので、答えはN-1として良い。

感想

なんとか解けた. ローリングハッシュ（多項式ハッシュ？）便利

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

const long MOD = 10^^9 + 9;
const long BASE = 31;

void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;
    auto T = S.to!(dchar[]).reverse.to!string;

    if (is_kaibun(S)) {
        writeln(N-1);
        return;
    }

    auto P = new long[](N+1);
    auto P_INV = new long[](N+1);
    P[0] = P_INV[0] = 1;
    foreach (i; 0..N) P[i+1] = P[i] * BASE % MOD;
    foreach (i; 0..N) P_INV[i] = powmod(P[i], MOD-2, MOD);

    auto rh = new long[](N+1);
    rh[N] = 0;
    foreach (i; 0..N) rh[i+1] = (rh[i] + (S[i] - 'a') * P[i]) % MOD;

    auto hr = new long[](N+1);
    hr[N] = 0;
    foreach (i; 0..N) hr[i+1] = (hr[i] + (T[i] - 'a') * P[i]) % MOD;

    long hash_substr(int l, int r) { // [l, r]
        return ((rh[r+1] - rh[l]) * P_INV[l] % MOD + MOD) % MOD;
    }

    long hash_reverse(int l, int r) {
        int nl = N - r - 1;
        int nr = N - l - 1;
        return ((hr[nr+1] - hr[nl]) * P_INV[nl] % MOD + MOD) % MOD;
    }

    int bin_search(int r1, int l2) {
        if (r1 < 0 || l2 >= N)
            return -1;
        int hi = min(r1+1, N-l2);
        int lo = -1;
        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            int l1 = r1 - mid;
            int r2 = l2 + mid;
            if (hash_substr(l1, r1) == hash_reverse(l2, r2))
                lo = mid;
            else
                hi = mid;
        }
        return lo;
    }


    int ans = 0;

    foreach (i; 0..N) { // S[i]が中心
        int len1 = bin_search(i-1, i+1) + 1;
        int r1 = i - len1 - 1;
        int l2 = i + len1 + 1;
        int len2 = max(bin_search(r1-1, l2), bin_search(r1, l2+1)) + 1;
        ans = max(ans, len1 * 2 + len2 * 2 + 1);
    }

    foreach (i; 0..N-1) { // S[i..i+1]が中心
        int len1 = bin_search(i, i+1) + 1;
        int r1 = i - len1;
        int l2 = i + len1 + 1;
        int len2 = max(bin_search(r1-1, l2), bin_search(r1, l2+1)) + 1;
        ans = max(ans, len1 * 2 + len2 * 2);
    }


    ans.writeln;
}

bool is_kaibun(string s) {
    return iota(s.length/2).map!(i => s[i] == s[s.length.to!int-i-1]).all;
}

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-12-29

yukicoder No.776 A Simple RMQ Problem

yukicoder 問題記録セグメントツリー

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

問題概要

N要素の数列Aに対して以下の2種類のクエリがQ個飛んでくるので順次処理せよ。

set(i, x): Ai の値を x に変更する。
max(l1, l2, r1, r2): l1 <= l <= l2, r1 <= r <= r2, l <= r を満たすすべての整数の組l, rにおける、Aの区間[l, r]の和の最大値を出力する。

N, Q <= 10⁵

解法

まずmaxクエリでは、l1より左にはみ出したr1と、r2より右にはみ出したl2については考慮する必要がない（そこにr1やl2をとっても l <= r が絶対に満たせないため）。よって r1 = max(l1, r1), l2 = min(l2, r2) としてしまってよい。その上で以下の2パターンに場合分けして考える。

1. l2 < r1 のとき

このときlとrをどう取ろうがお互いに干渉することがない（どう取っても l <= r は満たされるため）。よってそれぞれを独立に決めることができる。具体的には以下の3つの区間についてそれぞれ値を求めて足し合わせればよい。

区間[l1, l2]: 右端をl2に固定して左端を区間内で自由に決められるときの、最大の区間和
区間[l2+1, r1-1]: 区間全体の和（ここの区間は絶対に合計に入ってきてしまうので）
区間[r1, r2]: 左端をr1に固定して右端を区間内で自由に決められるときの、最大の区間和

2. l2 >= r1 のとき

lとrのとり方によってはl > rとなる可能性がある。以下の3パターンに分けて考える。

2-1. l < r1 となるようにlをとるとき

言い換えると[l1, r1-1]の区間内でlを取るとき。このときlをどう取ろうがrを追い越さないので先程と同じような値の決め方ができる。つまり

区間[l1, r1-1]: 右端をr1-1に固定して左端を区間内で自由に決められるときの、最大の区間和
区間[r1, r2]: 左端をr1に固定して右端を区間内で自由に決められるときの、最大の区間和

の2つを足し合わせればよい。

2-2. l2 < r となるようにrをとるとき

これも上と同じ。一応書くと

区間[l1, l2]: 右端をl2に固定して左端を区間内で自由に決められるときの、最大の区間和
区間[l2+1, r2]: 左端をl2+1に固定して右端を区間内で自由に決められるときの、最大の区間和

の2つを足し合わせる。

2-3. 上記以外のとき

言い換えるとlもrも[r1, l2]の範囲で取るとき。このときはこの区間の中の部分区間のうち、最大の和を求める必要がある。

セグ木に乗せる

以上より、maxクエリを処理するためには、ある区間[l, r]について以下の4つの情報がわかればよいということがわかった。

sum(l, r): 区間[l, r]の単純な区間和
lmax(l, r): 区間[l, r]において左端をlに固定して右端を区間内で自由に決められるときの、最大の区間和
rmax(l, r): 区間[l, r]において右端をrに固定して左端を区間内で自由に決められるときの、最大の区間和
allmax(l, r): 区間[l, r]のすべての部分区間のうちの、区間和の最大値

で、これらはセグ木に乗せてうまいこと処理することができる。具体的には以下のように隣り合う2区間のマージをやっていく（以下ではマージする左側の区間を左区間、右側を右区間と便宜的に呼ぶ）。

sum(l, r): これは普通のセグ木でも扱うような単純な区間和なので普通に足すだけ
lmax(l, r): あらたにlmaxとなりうるのは「左区間のlmax」もしくは「左区間のsum + 右区間のlmax」のどちらかなので、これらのmaxをとる。
rmax(l, r): 同上。
allmax(l, r): あらたにallmaxとなりうるのは「左区間のallmax」もしくは「右区間のallmax」もしくは「左区間のrmax + 右区間のlmax」のどれかなので、これらのmaxをとる。

以上でmaxクエリの処理に必要なセグ木を作ることができる。更新も一点更新のみなので普通にやることができる。あとは上の考察通りにセグ木にクエリを投げて計算していけばよい。

感想

自力で解けなかったが、セグ木を組み立てるパズルみたいで楽しかった

コード (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;
immutable long INF = 1L << 59;

alias Node = Tuple!(long, "sum", long, "lmax", long, "rmax", long, "allmax");

Node merge(Node l, Node r) {
    long lmax = max(l.lmax, l.sum + r.lmax);
    long rmax = max(r.rmax, r.sum + l.rmax);
    long allmax = max(l.allmax, r.allmax, l.rmax + r.lmax);
    return Node(l.sum + r.sum, lmax, rmax, allmax);
}

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

    this(int n) {
        size = 1;
        while (size <= n) size <<= 1;
        size <<= 1;
        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) {
        if (r < l) return e;
        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));
        }
    }
}


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

    auto st = new SegmentTree!(Node, merge, Node(0L, -INF, -INF, -INF))(N);
    foreach (i; 0..N) st.assign(i, Node(A[i], A[i], A[i], A[i]));

    while (Q--) {
        auto q = readln.split;
        if (q[0] == "set") {
            auto i = q[1].to!int - 1;
            auto x = q[2].to!long;
            st.assign(i, Node(x, x, x, x));
        } else {
            auto l1 = q[1].to!int - 1;
            auto l2 = q[2].to!int - 1;
            auto r1 = q[3].to!int - 1;
            auto r2 = q[4].to!int - 1;
            l2 = min(l2, r2);
            r1 = max(l1, r1);
            long ans = -INF;
            if (l2 < r1) {
                auto v1 = st.query(l1, l2).rmax;
                auto v2 = st.query(l2+1, r1-1).sum;
                auto v3 = st.query(r1, r2).lmax;
                ans = v1 + v2 + v3;
            } else {
                if (l1 < r1) {
                    auto v1 = st.query(l1, r1-1).rmax;
                    auto v2 = st.query(r1, r2).lmax;
                    ans = max(ans, v1 + v2);
                }
                if (l2 < r2) {
                    auto v1 = st.query(l1, l2).rmax;
                    auto v2 = st.query(l2+1, r2).lmax;
                    ans = max(ans, v1 + v2);
                }
                auto hoge = st.query(r1, l2);
                ans = max(ans, st.query(r1, l2).allmax);
            }
            ans.writeln;
        }
    }
}

2018-12-10

yukicoder No.719 Coprime

yukicoder 問題記録 DP

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

問題概要

2〜Nの数の集合から、「どの相異なる2つの要素を取り出してもそれらは互いに素である」という条件を満たすように部分集合を作る。このような部分集合のうち、要素の合計が最大になるときの値を求めよ。

2 <= N <= 1262

解法

DP的な気持ちになると、「素因数に2を持つ集合」、「素因数に3を持つ集合」、「素因数に5を持つ集合」、... という感じで各素因数のグループごとに処理していきたくなるが、これらの集合は排反ではないので独立に計算していくことができない（6は素因数に2も持つし3も持つ）。

これをうまいこと回避するためには、「『最大の』素因数が2である集合」、「『最大の』素因数が3である集合」、... という形で考えればよい。これらの集合に同時に属する数はないので、集合ごと独立に計算していくことができる。

あとはこの集合ごとにDPをしていくことを考える。どの要素も互いに素という条件を満たすためにはどの素因数も高々1回までしか使えない（＝素因数にa, b, cを持つ数を合計に組み入れた場合、以後もうa, b, cを素因数に持つ数は使えない）ことから、「どの素因数を既に使っているか」という情報も持っておく必要があるため、DPは以下のような形になる。

dp(n, S) := 最大の素因数がnである集合まで見て、使った素因数の集合がSであるときの最大合計値

ここで最大ケースであるN=1262までの素数はだいたい200個くらいあるため、すべての素数について使ったかどうかを記録しておくのは不可能である。しかし実は記録しておくのは高々sqrt(N)までの素数だけで問題ない。なぜなら

最大の素因数がsqrt(N)以下の集合の場合、各要素の最大の素因数は当然sqrt(N)以下
最大の素因数がsqrt(N)より大きい場合、「最大の素因数」を除けば他の素因数はsqrt(N)以下のものしかありえない（もし存在するなら、その2つを掛け合わせることでNを超えてしまう＝矛盾）

ということになっているからである。よってsqrt(N)以下の素因数は複数の「最大の素因数別の集合」に含まれうるが、sqrt(N)より大きい素因数pは「最大の素因数がpである集合」内の要素にしか素因数として含まれ得ない。そのため大きい素因数pを使うかどうかは「最大の素因数がpである集合」を足すときだけしか考えなくてよいので、記録しておく必要がない、ということになる。

N=1262のときsqrt(N)以下の素数は11個しかないので、これは2¹¹で覚えておいても全然足りる。これで上の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 int INF = 1 << 29;

bool is_prime(int n) {
    if (n <= 1)
        return false;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

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

    auto P = iota(2, N+1).filter!(i => is_prime(i)).array;
    int cnt = 0;
    for (int i = 0; i < P.length && P[i] * P[i] <= N; ++i, ++cnt) {}

    auto F = new int[][](N+1);
    foreach (i; 2..N+1) {
        int j = i;
        foreach (p; P) {
            while (j % p == 0) {
                F[i] ~= p;
                j /= p;
            }
        }
    }

    auto A = new int[](N+1);
    foreach (i; 2..N+1) foreach (j; 0..cnt) if (i % P[j] == 0) A[i] |= (1 << j);

    auto dp = new int[][](P.length+1, 1<<cnt);
    foreach (i; 0..P.length) fill(dp[i], -INF);
    dp[0][0] = 0;

    foreach (i; 0..P.length.to!int) {
        dp[i+1] = dp[i].dup;
        foreach (mask; 0..(1<<cnt)) {
            if (dp[i][mask] < 0) continue;
            for (int j = P[i]; j <= N; j += P[i]) {
                if (A[j] & mask) continue;
                if (F[j].back > P[i]) continue;
                int nmask = mask | A[j];
                dp[i+1][nmask] = max(dp[i+1][nmask], dp[i][mask] + j);
            }
        }
    }

    dp[P.length].reduce!max.writeln;
}

2018-12-04

Kyoto University Programming Contest 2018: F - カード集め

問題記録 AtCoder KUPC2018

https://beta.atcoder.jp/contests/kupc2018/tasks/kupc2018_f

問題概要

N枚のカードを使って2人ゲームをする。先手と後手はそれぞれのターンに残っているカードから任意の1枚を選んで手持ちに加える。このときカードに書いてある数値を得点として得る。また「カードaとカードbを両方取るとボーナスとしてc点が与えられる」という特別な組み合わせがM個与えられる。最終的な先手の得点が後手より真に大きければ先手の勝ち、そうでなければ後手の勝ちである。両者が最適に行動したときの勝敗を求めよ。

N, M <= 10⁵

解法

カードを頂点、ボーナスを辺としてグラフを作ってみる。このとき頂点にはカードの点数、辺にはボーナスの点数を持たせる。このグラフ上でゲームを考えると、「ある頂点を取ったらその頂点の点数がもらえる」「ある辺の両端の頂点をどちらも取ったらその辺の点数がもらえる」という感じになる。このままだと辺の条件のせいで考えるのが難しいが、実はこっちの方は「ある頂点を取ったら、それに繋がっている辺の半分の点数がもらえる」と言い換えることができる。なぜならば、

もし辺の両端の頂点をどちらも同じプレイヤーが取っているなら、結局半分＋半分で元のボーナス点と同じ点がもらえるのと一緒
もし辺の両端の頂点を別々のプレイヤーが取っているなら、どちらにも同じだけのボーナス点が加算されることになるので結局影響はゼロ

ということになるからである。そしてこの言い換えをすることで、このゲームは単純に頂点の取り合いだけを考えればよくなる。つまり両者の最適戦略が単純に「残っている中で最も点数の高い頂点を取る」になるので、各頂点に隣接辺の半分の点数を足したあとソートすれば答えが出る。

実装上の細かい点として、最初に全部の点を倍にしておけば半分にしたときも整数の範囲で点数を扱うことができる。

感想

思いついたとき天才家！？？？QQ!!となった

コード (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 S = readln.split.map!(to!long).array;

    foreach (i; 0..N) {
        S[i] *= 2;
    }

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

    S.sort!"a > b";
    auto a = iota(0, N, 2).map!(i => S[i]).sum;
    auto b = iota(1, N, 2).map!(i => S[i]).sum;

    writeln(a > b ? "First" : "Second");
}