DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦: C - 01文字列

問題記録 AtCoder DDCC2016本戦

問題概要

空文字列Sに対して以下の3種類の操作を好きな順番で好きな回数行い、与えられた文字列Tに一致させたい。そのための最小コストを求めよ。 1. Sの先頭に0を挿入する(コストA)。 2. Sの末尾に1を挿入する(コストB)。 3. Sの01をすべてflipする(コストC)

|T| <= 2×105

解法

操作1の回数をa回と決め打つと、操作bの回数は|T|-b回に定まる（Sの長さは操作1, 操作2によってしか増えないため）。さらに操作の特性上、先頭a文字が操作1由来、後ろのb文字が操作2由来であることも確定する。この時点でコストAはa回, コストBはb回支払うことが確定し、問題は操作3の回数をどれだけ少なくできるかという点に移る。操作3が反転であることを考えると明らかに0と1の切れ目では反転を行う必要があり、そうでないところでは必要がない。またaとbの切断箇所で隣り合う文字が同一の場合、どちらかが1回待たなければならない。とかの面倒なケースを処理しつつ計算する。これはO(1)でできるので操作1の決め打ち回数を全探索して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, std.bitmanip;

void main() {
    auto s = readln.split.map!(to!long);
    auto A = s[0];
    auto B = s[1];
    auto C = s[2];
    auto S = readln.chomp.map!(c => (c - '0').to!int).array;
    auto N = S.length.to!int;
    long ans = 1L << 59;

    auto seg1 = new int[](N);
    auto seg2 = new int[](N);
    seg1[0] = 1;
    seg2[N-1] = 1;
    foreach (i; 1..N) seg1[i] = S[i] == S[i-1] ? seg1[i-1] : seg1[i-1] + 1;
    foreach_reverse (i; 0..N-1) seg2[i] = S[i] == S[i+1] ? seg2[i+1] : seg2[i+1] + 1; 
    
    foreach (a; 0..N+1) { // 先頭に追加する回数
        int b = N - a; // 末尾に追加する回数
        int s1 = a == 0 ? 0 : seg1[a-1];
        int s2 = a == N ? 0 : seg2[a];
        int flip = max(s1, s2) - 1;
        if (a > 0 && a < N && s1 == s2 && S[a] == S[a-1]) flip += 1;
        if (s1 >= s2 && S[0] == 1) flip += 1;
        if (s1 < s2 && S[N-1] == 0) flip += 1;
        ans = min(ans, a * A + b * B + flip * C);
    }

    ans.writeln;
}

yukicoder No.127 門松もどき

問題記録 yukicoder 区間DP

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

問題概要

N要素の正整数列Aが与えられる。Aの部分列で門松もどきであるようなものの最大の長さを求めよ。ただし門松もどきとは 各要素の大きさが「左端→右端→左から2番目→右から2番目→...」で昇順になっているもの、または「右端→左端→右から2番目→左から2番目→...」で昇順になっているものをいう。

N <= 2000

解法

DPを2つ持って区間DPをする。

  • dp_left(l, r): 最も小さい要素がA[l]で、右端の位置がr以下であるような最長の門松もどきの長さ
  • dp_right(l, r): 最も小さい要素がA[r]で、左端の位置がl以上であるような最長の門松もどきの長さ

要するに最小の要素を固定した区間DPをする。このとき例えばdp_left(l, r)は A[l] < A[r] であるとき dp_right(l+1, r) + 1 を値にとることができる。どういうことかというとA[r] が最小であるような[l+1, r]の範囲の門松もどきに対して、その左にそれより小さいA[l]をくっつけるというイメージである。

門松もどきが伸びるのはこのパターンだけなので、あとは含む区間の最大値を引き継ぐようにすればいい。全体で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, std.bitmanip;

immutable long MOD = 10^^9 + 7;

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

    auto dp1 = new int[][](N, N);
    auto dp2 = new int[][](N, N);
    foreach (i; 0..N) dp1[i][i] = dp2[i][i] = 1;

    foreach (len; 2..N+1) {
        foreach (l; 0..N-len+1) {
            int r = l + len - 1;
            dp1[l][r] = dp1[l][r-1];
            if (A[l] < A[r]) dp1[l][r] = max(dp1[l][r], dp2[l+1][r] + 1);
            dp2[l][r] = dp2[l+1][r];
            if (A[l] > A[r]) dp2[l][r] = max(dp2[l][r], dp1[l][r-1] + 1);
        } 
    }

    int ans = 0;
    foreach (i; 0..N) foreach (j; 0..N) ans = max(ans, dp1[i][j], dp2[i][j]);
    ans.writeln;
}

yukicoder No.97 最大の値を求めるくえり

問題記録 yukicoder

問題概要

xorshiftによって生成される要素数Nの擬似乱数列Aがある。Q個のクエリqiが与えられるので、それぞれにおいて {qi * a mod 100003 (a ∈ A)} の最大値を求めよ。

1 <= N, Q <= 100003

0 <= qi < 100003

解法

この問題の肝は、Aが乱数列であることから q × A[i] (mod 100003) の値が 0 ～ 100002 の全体にだいたい均等に分布するだろうと考えられるというところである。なのでNが大きければ100002から順にひとつひとつ q × A[i] = m (mod 100003) なる A[i] はあるかということをチェックしていくとすぐに見つかることが期待できる。チェックの方法は q × A[i] = m より A[i] = m × q^{-1} となることから m × q^{-1} (mod 100003) を実際に求めてAにそれが含まれているかを見ればよい。逆にNが小さいならばこういうことをしないで普通にO(NQ)の全探索をすればOK

感想

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, std.bitmanip;

immutable long MOD = 100003;

uint xor128_x = 123456789, xor128_y = 362436069, xor128_z = 521288629, xor128_w = 88675123;
uint xor128() {
    uint t = xor128_x ^ (xor128_x << 11);
    xor128_x = xor128_y; xor128_y = xor128_z; xor128_z = xor128_w;
    return xor128_w = xor128_w ^ (xor128_w >> 19) ^ (t ^ (t >> 8));
}

void generateA(int N, long A[]) {
    for(int i = 0; i < N; ++ i)
        A[i] = xor128() % 100003;
}

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


void solve1(int N, int Q, long[] A) {
    while (Q--) {
        auto q = readln.chomp.to!long;
        auto B = A.map!(a => a * q % MOD).array;
        B.reduce!max.writeln;
    }
}

void solve2(int N, int Q, long[] A) {
    auto B = new bool[](MOD+1);
    foreach (a; A) B[a.to!int] = true;
    
    while (Q--) {
        auto q = readln.chomp.to!long;
        if (q == 0) {
            writeln(0);
            continue;
        }
        for (long x = MOD-1; x >= 0; --x) {
            auto y = x * powmod(q, MOD-2, MOD) % MOD;
            if (B[y.to!int]) {
                x.writeln;
                break;
            }
        }
    }
}

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

    if (N <= 800) solve1(N, Q, A);
    else solve2(N, Q, A);
}

AtCoder Regular Contest 065 : F - シャッフル / Shuffling

AtCoder ARC #065 ARC DP

問題概要

長さNの01文字列Sが与えられる。M個の数字ペア(Li, Ri)が与えられ、Sの区間[Li, Ri]の文字を自由に並び替える、という操作を順に行ったあとのSとしてありうるものが何通りあるか求めよ。ただしLiは必ず昇順になっているものとする。

N, M <= 3000

解法

dp(i, j): i文字目までで、0をj回使って作れる文字列の数

としてDPをする。このDPの遷移は、i文字目に0を使う/1を使う の2通りである。

ここでSのi文字目を見ているとき、iを区間に含むようなシャッフル操作LRがあれば、そのうち最大のRをr_maxと置く。なければr_max=iとする。このようにすると、「Sのi文字目までに使える0の数」は高々「Sのr_max文字目までに現れる0の数」と言うことができる。1の数も r_maxからこれを引けば出せる。

これを踏まえて dp(i, j) を更新することを考えると、上で出した「Sのi文字目までに使える0の数」がjより多ければ「使える0」が余るので dp(i+1, j+1) に遷移できる（ゼロを使うパターン）。同じように「Sのi文字目までに使える1の数」が i - j より多ければd(i+1, j) に遷移できる。

このDPは状態数 O(N2), 遷移 O(1) なので O(N2) でできる。

なおr_maxについてはシャッフル操作がLの昇順になっていることから尺取り法の要領でO(N+M)で逐次求めていくことができる。

感想

シャッフル操作の言い換えがキモという感じですが、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!int);
    auto N = s[0];
    auto M = s[1];
    auto S = readln.chomp;
    auto LR = M.iota.map!(_ => readln.split.map!(a => a.to!int - 1).array).array;

    auto zeros = new long[](N+1);
    foreach (i; 0..N) {
        zeros[i+1] = zeros[i] + (S[i] == '0');
    }

    auto dp = new long[][](N+1, N+1);
    dp[0][0] = 1;
    int rmax = 0;
    int q = 0;

    foreach (i; 0..N) {
        while (q < M && LR[q][0] <= i) {
            rmax = max(LR[q][1], rmax);
            q += 1;
        }
        rmax = max(rmax, i);
        long zero = zeros[rmax+1];
        long one = rmax + 1 - zero;

        foreach (j; 0..i+1) {
            long rest_zero = zero - j;
            long rest_one = one - (i - j);
            if (rest_zero < 0 || rest_one < 0) {
                continue;
            }
            if (rest_zero > 0) {
                dp[i+1][j+1] += dp[i][j];
                dp[i+1][j+1] %= MOD;
            }
            if (rest_one > 0) {
                dp[i+1][j] += dp[i][j];
                dp[i+1][j] %= MOD;
            }
        }
    }

    long ans = 0;
    foreach (a; dp[N]) {
        ans += a;
        ans %= MOD;
    }

    ans.writeln;
}

天下一プログラマーコンテスト2016本戦 C - たんごたくさん

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

https://atcoder.jp/contests/tenka1-2016-final/tasks/tenka1_2016_final_c

問題概要

文字列SとM要素の文字列の集合Pが与えられる。SからPの要素を取り除くと、取り除いた要素に対応する点数Wが与えられる。任意の回数この操作を行ったときの、得られる点数の最大値を求めよ

|S| <= 2×105

M <= 5000

|P_i| <= 200

解法

Pの各要素がSのどこに一致するかさえわかれば、以下のような単純なDPで解ける。

dp(i) = Sのi文字目までで得られる最大の点数

遷移については、Sの区間[i, i+k]に一致するようなPがある場合、dp(i+k) = dp(i)+そのPの点数 という方になる。

問題はPの各要素がSとどこで一致するか求めることである。これを本当に単純にやると(Sの文字数)×(Pの要素数)×(Piの最大文字数)かかる。これでは1011とかになって明らかに間に合わない。

方法のひとつはTrie木を使うことである。Trie木の特徴の一つとして、「あるひとつの文字列に対して複数の文字列をマッチさせる操作」が高速に行えるという点がある。今回の問題に当てはめていうと、木の構築を(Pの要素数)×(Piの最大文字数)で行え、S[i]を始点とした際にマッチする単語の列挙を(P_iの最大文字数)で行える。ゆえにDPの前にTrie木を構築しておけば、DPの計算は(Sの文字数)×(P_iの最大文字数)で済む。これは107のオーダーに収まるので十分間に合う。

感想

ローリングハッシュで109をゴリ押そうとしたら全然通らなかった

コード (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.chomp;
    auto M = readln.chomp.to!int;
    auto P = M.iota.map!(_ => readln.chomp).array;
    auto W = M.iota.map!(_ => readln.chomp.to!int).array;
    auto N = S.length.to!int;

    auto trie = new Trie;
    foreach (i; 0..M) {
        trie.add_word(P[i], W[i]);
    }

    auto dp = new int[](N+1);
    foreach (i; 0..N) {
        dp[i+1] = max(dp[i+1], dp[i]);
        auto x = trie.search(S[i..min(i+200, N)]);
        foreach (j; 1..x.length) {
            dp[i+j] = max(dp[i+j], dp[i] + x[j]);
        }
    }

    dp[N].writeln;
}


class Node {
    int w;
    Node[char] children;

    this (int w) {
        this.w = w;
    }
}


class Trie {
    Node root;
    
    this() {
        root = new Node(0);
    }

    void add_word(string s, int w) {
        auto cur = root;
        foreach (c; s) {
            if (c !in cur.children) {
                cur.children[c] = new Node(0);
            }
            cur = cur.children[c];
        }
        cur.w = w;
    }

    int[] search(string s) {
        int[] ret = [0];
        auto cur = root;
        foreach (c; s) {
            if (c !in cur.children) {
                break;
            }
            cur = cur.children[c];
            ret ~= cur.w;
        }
        return ret;
    }
}

みんなのプロコン (2017) 本選 C - 倍数クエリ

問題記録 みんなのプロコン みんなのプロコン2017本戦 AtCoder 平方分割

https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_c

問題概要

整数MとN要素の数列Aが与えられるので、以下の形のQ個のクエリを順に処理せよ。

クエリ: Aの区間[l, r]の全要素にxを加算する。その後、同じ区間内にMの倍数が何個あるかを出力する。

N, M, Q <= 105

A_i <= 109

解法

平方分割をする。 平方分割に関しては以下のブログがわかりやすい。

この問題の場合、分割したあとの上位のバケットに対して、以下の2つの情報を記録しておく必要がある。

  1. sum: この区間全体に対して足された数
  2. count: この区間内において 0 ～ M-1 (mod M)の値が何個存在するか

1の方は上記記事の最初に解説されているbucketSumと同じである。2の方はそれぞれの区間でサイズMの配列を持つことで管理する。メモリが心配になるが、Mが小さいので十分収まる。

次にクエリの処理について。まず加算クエリは、区間全体に足せるならsumバケットに足すだけ。区間に一部だけ重なっている場合は、もとの数列の方に直接加算する（このときcountバケットも更新する）。

倍数カウントクエリの方は、まず区間全体に重なっているならcountの値を見ればよい。つまり「Mの倍数 => mod M で 0」であるから、count配列の対応する要素を見るだけでMの倍数の数がわかる。ただしこのとき同じ区間のsumの値に注意が必要で、この値はつまり「その区間全体に足されたことになっている数値」であるから、そのぶん見る場所をずらす必要がある。区間に一部だけ重なっている場合は愚直にひとつひとつMで割り切れるか判定していけばよい。

各処理とも、「区間全体に対する処理」で済ませられる場合にはO(1), 「区間に一部だけ重なっている場合の処理」についてはO(sqrt(N))かかる（区間全体の長さが高々sqrt(N)であるため）。このとき前者の処理回数は高々sqrt(N)回, 後者の処理回数は高々2回（左右のはみだし）であるから、どちらの処理も結局O(sqrt(N))となる。これをQ回繰り返すので最終的な計算量はO(Qsqrt(N)).

感想

初めて平方分割書いた

Aの方がむずない？

コード (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 int D = 320;

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

    auto SIZE = N / D + 1;
    auto sd_sum = new int[](SIZE);
    auto sd_cnt = new int[][](SIZE, M);

    foreach (i; 0..N) {
        sd_cnt[i/D][A[i]] += 1;
    }

    int add(int a, int b, int x) { // a <= i <= b に x を加算
        int ret = 0;
        for (int i = 0, l = 0, r = D-1; i < SIZE; i += 1, l += D, r += D) {
            if (a <= l && r <= b) {
                sd_sum[i] += x;
                sd_sum[i] %= M;
                ret += sd_cnt[i][(M - sd_sum[i] + M) % M];
            } else if ((l <= a && a <= r) || (l <= b && b <= r)) {
                for (int j = max(a, l); j <= min(b, r, N-1); ++j) {
                    sd_cnt[i][A[j]] -= 1;
                    A[j] += x;
                    A[j] %= M;
                    sd_cnt[i][A[j]] += 1;
                    if ((A[j] + sd_sum[i]) % M == 0) ret += 1;
                }
            }
        }
        return ret;
    }

    while (Q--) {
        s = readln.split.map!(to!int);
        int l = s[0]-1;
        int r = s[1]-1;
        int x = s[2]%M;
        add(l, r, x).writeln;
        debug {
            sd_sum.writeln;
            sd_cnt.writeln;
            A.writeln;
        }
    }
}

みんなのプロコン (2017) 本選 B - チーム決め

問題記録 AtCoder みんなのプロコン みんなのプロコン2017本戦 二分探索

問題概要

N要素の数列AとM要素の数列Bが与えられる。数列からK個の要素を選んで任意の順序で並べる、という操作を両方の数列に対して行ってできる数列をX, Yとする。好きな選び方ができるとき、max(|X_1-Y_1|, ..., |X_K - Y_K|)の最小値を求めよ。

N, M <= 105

解法

2分探索をする。O(NlogN)

ある値αについて差がα以下であるペアをK個以上作れるかどうかを判定していくことで、αの最小値を2分探索できる。ペアをK個以上作れるかどうかは、AとBをあらかじめソートしておいたうえで前から貪欲に決めていくことで判定できる。具体的にはAとBを前から見ていき、もし見ているペアの差がα以下であればペア成立とし、AもBも次の要素に移る。逆に差がαより大きい場合、小さい方だけ次の要素に移る。最終的に作ったペアの数がK以上であればそのαは適格である。

感想

Aの方がむずない？

コード (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 K = s[2];
    auto A = readln.split.map!(to!long).array;
    auto B = readln.split.map!(to!long).array;
    A.sort();
    B.sort();

    long hi = 10^^9;
    long lo = -1;

    while (hi - lo > 1) {
        long mid = (hi + lo) / 2;
        int cnt = 0, i = 0, j = 0;
        
        while (i < N && j < M) {
            if (abs(A[i] - B[j]) <= mid) {
                cnt += 1;
                i += 1;
                j += 1;
            } else if (A[i] - B[j] > mid) {
                j += 1;
            } else {
                i += 1;
            }
        }

        if (cnt >= K) {
            hi = mid;
        } else {
            lo = mid;
        }
    }

    hi.writeln;
}