Codeforces Round #428 Div.2 D - Winter is here

http://codeforces.com/contest/839/problem/D

問題概要

N要素の数列Aが与えられる。Aの部分集合Sに対して、strength(S) = |S|・gcd(S) と定義する。gcd(S) > 1 なるすべての部分集合Sに対するstrengthの総和を求めよ。

N <= 2 * 105, max(A) <= 106

解法

一旦問題を緩和して、gcdではなく約数で考えてみる。すべての要素がxを約数に持つような部分集合の中で最も要素数が多いものをS_xと置くと、緩和版のstrengthは

  f(x) = \sum_{T \subseteq S_x}{|T|\cdot x}

と表せる。

ここでS_xは「gcdがxである集合」の上位集合であるから、f(x)から「gcdがxでない集合Tの|T|・x」を引いてやれば本当に求めたかったgcdの場合での値を得ることができる。では「S_xの中でgcdがxでない集合」のgcdがどのようになるのかと考えてみると、それらは必ずxの倍数になる。ゆえにxが大きいものから順にf(x)を求めていき、そこからΣf(xの倍数)を引いていけば答えが求まる。

肝心のf(x)の値だが、部分集合の取り方から以下のような組合せの式が立てられる。

 f(x) = x \cdot ({}_{|S_x|} C_1 + { }_{|S_x|} C_{2} + \ldots + { }_{|S_x|} C_{S_x})

後半の組合せの和は二項係数の性質から 2^{|S_x|-1}と変形できる(らしい)ので、2の累乗を前計算しておくか繰り返し二乗法ですぐ求まる。

自分は以下のように実装した。

  1. Aの全要素について約数を調べ、どの数が何回約数として使われているかをカウントする
  2. 大きい方からf(x)を求め、 g(x) = f(x) - \sum_{i>=2}{f(ix) / i}を求める(割り算のためにmod109+7での逆元をあらかじめ求めておく)
  3. g(x)の合計をとる

計算量はO(N*sqrt(N) + max(A) * log(N))

感想

C++で書いてTL3000msのところ2970msとかだったので、想定解はもうちょっとスマートになるっぽい? →今見てきたら最速で100ms強でした。速すぎる…。ちなみに私が堂々の最下位です。本当にありがとうございました。

他の方の解説見ると逆元持ち出してるところは明らかに冗長で、個数だけで包除やったあと最後に掛け算すればよい、ということはわかった。あと約数カウントはエラトステネスっぽくやると速くできるっぽい。これが一番でかそう。

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

const ll MAX = 1000000;
const ll MOD = 1000000007;
ll A[202020];
ll cnt[MAX + 1];
ll pow2[MAX + 1];
ll modinv[MAX + 1];
ll ans[MAX + 1];


int main() {
    pow2[0] = 1;
    REP(i, MAX) pow2[i + 1] = pow2[i] * 2 % MOD;
    modinv[0] = modinv[1] = 1;
    REP2(i, 2, MAX + 1) modinv[i] = modinv[MOD % i] * (MOD - MOD / i) % MOD;

    int N; cin >> N;
    REP(i, N) cin >> A[i];
    memset(cnt, 0, sizeof(cnt));
    memset(ans, 0, sizeof(ans));

    REP(i, N) {
        for (ll j = 1; j * j <= A[i]; ++j) {
            if (j * j == A[i]) {
                cnt[j] += 1;
            } else if (A[i] % j == 0) {
                cnt[j] += 1;
                cnt[A[i] / j] += 1;
            }
        }
    }

    for (ll i = MAX; i > 1; i--) {
        if (!cnt[i]) continue;
        ans[i] += i * cnt[i] % MOD * pow2[cnt[i]-1] % MOD;
        ans[i] %= MOD;
        int hoge = 2;
        for (ll j = i + i; j <= MAX; j += i) {
            ans[i] = (ans[i] - ans[j] * modinv[hoge]) % MOD;
            ans[i] = (ans[i] + MOD) % MOD;
            hoge += 1;
        }
    }

    ll tmp = 0;
    REP(i, MAX+1) tmp = (tmp + ans[i]) % MOD;
    cout << tmp << endl;
}

AtCoder Grand Contest 008 D - K-th K

http://agc008.contest.atcoder.jp/tasks/agc008_d

問題概要

与えられた長さNの数列Xに対して、次の条件すべてを満たす数列Aが構成できるか判定せよ。またできるならば実際にひとつ示せ。

  • 条件1. Aの長さはN2
  • 条件2. Aは要素として1, 2, …, NをN個ずつ含む
  • 条件3. 各i (1 <= i <= N) について、Aにおいて整数iのうち左からi番目に位置するものは、A全体ではX[i]番目に位置する

解法

とりあえずX[i]をiで埋める。各iについてX[i]より前に何個置いてX[i]より後ろに何個置けばいいかは決まっているので、あとは前から見ていってX[i]が小さい順にiを詰めていけばよい。

感想

罠があると思ったらなかった

コード (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 A = readln.split.map!(to!int).array;
    auto ans = new int[](N*N);
    foreach (i; 0..N) ans[A[i] - 1] = i + 1;
    
    auto front = N.iota.array;
    auto back = N.iota.map!(i => N - i - 1).array;
 
    auto pq1 = new BinaryHeap!(Array!(Tuple!(int, int)), "a[0] > b[0]");
    auto pq2 = new BinaryHeap!(Array!(Tuple!(int, int)), "a[0] > b[0]");
    foreach (i; 1..N) pq1.insert(tuple(A[i] - 1, i + 1));
    pq2.insert(tuple(A[0] - 1, 1));
 
    foreach (i; 0..N*N) {
        if (ans[i] > 0) {
            continue;
        } else if (!pq1.empty) {
            auto t = pq1.front;
            auto pos = t[0];
            auto num = t[1];
            if (pos < i) {
                writeln("No");
                return;
            }
            ans[i] = num;
            front[num-1] -= 1;
            if (front[num-1] == 0) {
                pq1.removeFront;
                if (num != N) pq2.insert(tuple(pos, num));
            }
        } else if (!pq2.empty) {
            auto t = pq2.front;
            auto pos = t[0];
            auto num = t[1];
            if (pos > i) {
                writeln("No");
                return;
            }
            ans[i] = num;
            back[num-1] -= 1;
            if (back[num-1] == 0) pq2.removeFront;
        } else {
            writeln("No");
            return;
        }
    }
 
    writeln("Yes");
    ans.map!(a => a.to!string).join(" ").writeln;
}

AtCoder Grand Contest 004 D - Teleporter

http://agc004.contest.atcoder.jp/tasks/agc004_d

問題概要

N個の町があり、1~Nまでの番号が振られている。それぞれの町には1台ずつテレポーターがあり、町iのテレポーターの転送先は町aiに設定されている。また初期状態では必ず何回かテレポーターをたどることで町1にたどり着けることが保証されている。

正整数Kが与えられたとき、「どの町を出発点としてもテレポーターをちょうどK回使うと町1にたどり着く」という状態を作りたい。最小で何個のテレポーターの転送先を変更するとこの条件を達成できるか求めよ。

2 <= N <= 105, 1 <= ai <= N, 1 <= K <= 109

解法

まず町1の転送先は必ず町1でなければならない。町1の転送先が町x (x!=1)でかつ町1→町1の移動がちょうどK回でできるとすると、町x→町1の移動は(K-1)回となり、結局町x→町xへの移動がちょうどK回となってしまうためである。

以上より町1の転送先を町1にすると、「初期状態では必ず何回かテレポーターをたどることで町1にたどり着けることが保証されている」という条件より、遷移を表したグラフは必ず木になることがわかる。この木において町1を根にした根付き木をGとすると、問題は以下のように言い換えられる。

Gのすべての頂点の深さをK以下にしたい。以下の操作を最小で何回行えば目的を達成できるか求めよ。【操作】頂点をひとつ選び、根が親になるよう辺を張り替える

ここで深さがKより大きいあるひとつの頂点に注目すると、自分・自分の1個上の頂点・自分の2個上の頂点・……・自分の(K-1)個上の頂点 のいずれかひとつに対して必ず1回は上の操作が行われている必要がある。また逆にある点を選んで操作を行ったとき、自分の(K-1)個下までの子供は条件を満たすことになる。ゆえにある特定の深さ>Kの点を深さK以下にしたいときには、(K-1)個上の親に操作を行うのが最適である。

ここまでを踏まえて、自分は以下のような貪欲をやった。まずマークされていない頂点の中で一番深いものを選び、その(K-1)個上の頂点の親を根に張り替える。その頂点の部分木に含まれる点をすべてマークする。これを深さ>Kの頂点がすべてマークされるまで続けたとき、親の張り替えを行った回数が答え。

感想

時間かかったけど自力で通せてよかった。ふと順位表を見たら当時の自分は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;
 
void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto K = s[1];
    auto A = readln.split.map!(to!int).array;
    auto edges = new int[][](N);
    foreach (i; 1..N) {
        auto a = A[i] - 1;
        auto b = i;
        edges[a] ~= b;
        edges[b] ~= a;
    }
    
    auto depth = new int[](N);
    void dfs(int n, int p, int d) {
        depth[n] = d;
        foreach (m; edges[n]) if (m != p) dfs(m, n, d + 1);
    }
    dfs(0, -1, 0);
 
 
    auto used = new bool[](N);
    void dfs2(int n, int lb, int ub) {
        used[n] = true;
        foreach (m; edges[n]) if (depth[m] >= lb && depth[m] <= ub && !used[m]) dfs2(m, lb, ub);
    }
 
    auto pq = new BinaryHeap!(Array!(Tuple!(int, int)), "a[1] < b[1]");
    foreach (i; 1..N) if (depth[i] > K) pq.insert(tuple(i, depth[i]));
    int ans = A[0] != 1;
 
    while (!pq.empty) {
        auto t = pq.front;
        auto n = t[0];
        pq.popFront;
        if (used[n]) continue;
        ans += 1;
        dfs2(n, min(depth[n], depth[n] - K + 1), depth[n]);
    }
 
    ans.writeln;
}

CS Academy Round #41 E - Candles

https://csacademy.com/contest/round-41/task/candles/

問題概要

N要素の数列HとM要素の数列Cが与えられる。以下のような操作をHに対して行っていく。

操作: i回目の操作においてHからC[i]個の正の要素を選び、すべてを1デクリメントする。

数列Hに正の要素がC[i]個未満しか存在しないか、あるいはiがMを超えた時点で操作を終了する。最大で何回の操作を行うことができるか求めよ。

1 <= N, M, max(H), max(C) <= 105

解法

最適な選び方自体は単純で、大きい順にC[i]個の要素を選んでデクリメントするだけ。問題は計算量で、「大きい順にC[i]個選ぶ」「それらに-1を加算する」の操作は愚直にやるとどちらも毎回O(N)かかる。

ここでHをソートしておくと「大きい順にC[i]個選ぶ」はO(1)で可能になる。またセグメントツリーでうまいことやると区間加算はO(logN)で可能になる。というわけで1回の操作はセグ木に突っ込んでおいたソート済の列の後ろC[i]個に対して-1を加算することでO(logN)で行える。ここで問題になるのは加算によってソートが崩れることである。例えば

1 2 3 3 3 4 5 に対してC[i] = 4のとき

1 2 3 3 3 4 5 にデクリメントをかけると

1 2 3 2 2 3 4 という風にソートが崩れる。

ここでソートが崩れる場所を観察すると、値の逆転が起こりうるのは「選ばれたC[i]個の中で最も小さい数値」の周りであることがわかる。これは1回につき必ず1ずつしか値が減らないという性質に依る。ゆえにデクリメントをかける際に「選ばれるC[i]個の数値のうち、もっとも小さいもの」を求めておいて、そこへのデクリメントのみ前から行う、という風にすればソート順を崩すことなく操作を行える。

1 2 3 3 4 4 5

1 2 3 3 3 4 5

1 2 2 2 3 3 4

この操作のためには、「選ばれるC[i]個の数値のうちもっとも小さいもの」の値をvとおくと「値がvであるもののうちもっとも左のindex」「値がvであるもののうちもっとも右のindex」の情報が必要になる。これは例えばセグメントツリーを上位ノードでminをとるようなタイプにしておくと、セグ木上で二分探索みたいなことができてO(logN)で可能。以上より全体としてO(MlogN)で答えが出せる。

感想

遅延評価タイプのセグ木をわかってなさすぎて実装が辛かった。本番中に正しい方針を思いつけていたところまでは良かった。

コード (C++)

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


ll N, M;
ll H[101010];
ll C[101010];


class LazySegmentTree {
public:
    vector<ll> table;
    vector<ll> lazy_;
    int size;
    ll defval;
 
    LazySegmentTree(int n, ll defval = 0) {
        size = 1;
        while (size < n) size *= 2;
        size *= 2;
        table = vector<ll>(size, defval);
        lazy_ = vector<ll>(size, defval);
        LazySegmentTree::defval = defval;
    }

    void assign(int a, ll num) {
        return assign(a, num, 0, 0, size/2-1);
    }
 
    void assign(int a, ll num, int i, int l, int r) {
        if (a < l || a > r) return;
        
        if (l == r) {
            table[i] = num;
            return;
        }
        
        assign(a, num, i*2+1, l, (l+r)/2);
        assign(a, num, i*2+2, (l+r)/2+1, r);
        table[i] = max(table[i*2+1] + lazy_[i*2+1],
                       table[i*2+2] + lazy_[i*2+2]);
    }

    void add(int a, int b, ll num) {
        return add(a, b, num, 0, 0, size/2-1);
    }
 
    void add(int a, int b, ll num, int i, int l, int r) {
        if (a > r || b < l) return;
        if (a <= l && r <= b) {
            lazy_[i] += num;
            return;
        }
        
        add(a, b, num, i*2+1, l, (l+r)/2);
        add(a, b, num, i*2+2, (l+r)/2+1, r);
        table[i] = max(table[i*2+1] + lazy_[i*2+1],
                       table[i*2+2] + lazy_[i*2+2]);
    }    
 
    ll query(int a, int b) {
        return query(a, b, 0, 0, size/2-1);
    }
 
    ll query(int a, int b, int i, int l, int r) {
        if (a > r || b < l) return defval;
        if (a <= l && r <= b) return table[i] + lazy_[i];
        
        ll vl = query(a, b, i*2+1, l, (l+r)/2);
        ll vr = query(a, b, i*2+2, (l+r)/2+1, r);
        return max(vl, vr) + lazy_[i];
    }

    ll search_left(ll num) {
        if (num > query(0, N-1)) return N;
        return search_left(num, 0, 0, size/2-1, 0);
    }

    ll search_left(ll num, int i, int l, int r, ll acm) {
        if (l == r) return l;
        acm += lazy_[i];
        ll vl = table[i*2+1] + lazy_[i*2+1] + acm;
        ll vr = table[i*2+2] + lazy_[i*2+2] + acm;
        if (vl >= num) return search_left(num, i*2+1, l, (l+r)/2, acm);
        else           return search_left(num, i*2+2, (l+r)/2+1, r, acm);
    }
};


int main() {
    cin >> N >> M;
    REP(i, N) cin >> H[i];
    REP(i, M) cin >> C[i];
    sort(H, H+N);
    LazySegmentTree st = LazySegmentTree(N, 0);
    REP(i, N) st.add(i, i, H[i]);

    ll ans = 0;
        
    REP(i, M) {
        ll x = N - C[i];
        if (x < 0) break;
        ll v = st.query(x, x);
        if (v == 0) break;

        ll l = st.search_left(v);
        ll r = st.search_left(v + 1);
        ll seg = r - x - 1;
        st.add(l, l + seg, -1);
        st.add(r, N - 1, -1);

        ans = i + 1;

    }

    cout << ans << endl;
}

AtCoder Regular Contest 080 F - Prime Flip

http://arc080.contest.atcoder.jp/tasks/arc080_d

問題概要

1, 2, …と順に番号の振られた無限枚のカードと、N要素の数列Xがある。数列Xに含まれる番号のカードは表向きで、それ以外は裏向きである。奇素数pと連続するp枚のカードを自由に選びそれらを裏返す、という操作を繰り返すとき、すべてのカードを裏向きにするために必要な最小の操作回数を求めよ。

N <= 100, max(X) <= 107

解法

表向きのカードを1, 裏向きのカードを0とすると、カードを0/1の列で表すことができる。この数列をAとし、また数列Aについてxorで階差をとった数列をBとする。こうすると「Aにおいて区間[x, x+p]をflipする」という操作が「Bにおいてx, x+pの2点をflipする」とみなせるようになる。なぜなら隣り合う点を同時にflipしてもxorの値は変わらず、端点だけで変化が生じるためである。これで連続する列に対する操作を2点のみに対する操作に変換することができた。

次にBにおいてビットが立っている点のペア(i, j)を選び、これらを両方0にすることを考える。これを達成するための最小操作回数は実のところ1回, 2回, 3回のいずれかに限定される。

  • コスト1. |i - j| が奇素数の場合 (自明)
  • コスト2. |i - j| が偶数の場合 (cf. ゴールドバッハの予想
  • コスト3. |i - j| が素数でない奇数の場合 (1回の操作で偶数差にできるため)

以上より最終的な答えは、まずコスト1で消せるだけの奇数差ペアを消し、次にコスト2で消せるだけの偶数差ペアを消し、最後に残った奇数差のペアをコスト3で消すことで得ることができる。ここで「コスト1で消せる最大のペア数」は2部グラフの最大マッチングで解くことができる。すなわちビットが立っている点を奇数と偶数でグループ分けし、その間で差が奇素数であるものに辺を張る。このようにしてできた2部グラフの最大マッチングがイコール「コスト1で消せる最大のペア数」になる。これが求まったらあとは貪欲で、残った奇数グループ、偶数グループの中でコスト2のペアをできるだけ作り、最後に余った点があればコスト3でペアを作る。以上で払ったコストの合計が解となる。

感想

①階差数列をとることで2点に対する操作に落とす ②ペアを消すためのコストが1, 2, 3の3パターンしかないことに気づく ③フローでがんばれることに気づいてがんばる という風に複数の山場がある問題ですが、①の時点でムズすぎる……。 ②③もパッと思いつけるほどではないように見えるし、奇跡的に①が思いついても自分の実力ではまず詰め切れそうにない。バイナリ列の区間に対する操作は階差を取ると良い感じになることがある、っていうのが割と汎用性の高いテクなのか、それともこのくらいのレベルになるとこういうのを都度アドホックに発見していく力が必要なのか……

コード (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 A = readln.split.map!(to!int).array;
    
    int[] B;
    foreach (a; A) {
        foreach (b; a-1..a+1) {
            if (B.length > 0 && B[$-1] == b) B.popBack;
            else B ~= b;
        }
    }
 
    auto P = new bool[](10^^7 + 10);
    fill(P, true);
    P[0] = P[1] = false;
    for (int i = 2; i < 10^^7 + 10; i++) {
        if (!P[i]) continue;
        for (int j = i + i; j < 10^^7 + 10; j += i) P[j] = false;
    }
 
 
    B.sort!"a % 2 > b % 2"();
    int M = B.length.to!int;
    int source = M;
    int sink = M + 1;
    int odd = B.map!(b => b % 2).sum;
    int even = B.map!(b => 1 - b % 2).sum;
    auto FF = new FordFulkerson(M + 2, source, sink);
    foreach (i; 0..odd) FF.add_edge(source, i, 1);
    foreach (i; odd..odd+even) FF.add_edge(i, sink, 1);
    foreach (i; 0..odd) {
        foreach (j; odd..odd+even) {
            if (P[abs(B[i] - B[j])]) FF.add_edge(i, j, 1);
        }
    }
    
    int one = FF.run;
    odd -= one;
    even -= one;
    int two = odd / 2 + even / 2;
    int three = odd % 2;
 
    writeln(one + two * 2 + three * 3);
}
 
 
 
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;
        }
    }
}

Typical DP Contest G - 辞書順

http://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical

問題概要

英小文字からなる文字列Sの部分文字列のうち、辞書順でK番目のものを求めよ。ただしここでいう部分文字列は元の文字列で連続でないものも含む。また違うindexからなるものでも、結果として同じ文字列になるものはひとつとして扱う。

|S| <= 106, K <= 1018

解法

dp(n)をn文字目を先頭としたときに作れるユニークな部分文字列の数とする。

next(α, i) = 文字列Sにおいて文字αがi番目以降初めて現れるインデックス

とすると、dp(n)は以下のように表せる。


dp(n) = \sum_{\alpha} dp(next(\alpha, n + 1)) + 1

これを求めれば「次に文字xを取ったら辞書順でいくつ進むか」がわかるので最終的な答えが求まる。

注意点(というか自分がハマったところ)として、|S|が大きいのでdpをメモ化再帰でやろうとするとスタックオーバーフローになること、またdpの値は64bit型整数でもオーバーフローしうることなどがあった。前者はdpをループで書き直し、後者はKを超える値は全部INFにまとめるという小細工で回避した。

感想

解説見ずにとおせてうれしかったです

コード (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 long INF = 10L ^^ 18 + 1000;
 
void main() {
    auto S = readln.chomp;
    auto N = S.length.to!int;
    auto K = readln.chomp.to!long;
 
    auto chars = new int[][](26, N);
    foreach (i; 0..26) {
        int tmp = -1;
        for (int j = N - 1; j >= 0; j--) {
            if (S[j] - 'a' == i) tmp = j;
            chars[i][j] = tmp;
        }
    }
 
    auto dp = new long[](N);
    fill(dp, 1);
 
    for (int i = N - 2; i >= 0; i--) {
        foreach (j; 0..26) {
            int m = chars[j][i + 1];
            if (m == -1) continue;
            if (dp[m] == INF) {
                dp[i] = INF;
                continue;
            }
            dp[i] += dp[m];
            if (dp[i] > INF || dp[i] <= 0) {
                dp[i] = INF;
                continue;
            }
        }
    }
 
 
    string ans = "";
 
 
    void dfs(int p, long acm) {
        if (acm == K) return;
        foreach (i; 0..26) {
            int m = chars[i][p];
            if (m == -1) continue;
            if (acm + dp[chars[i][m]] >= K) {
                ans ~= i.to!char + 'a';
                dfs(chars[i][m] + 1, acm + 1);
                return;
            }
            acm += dp[chars[i][m]];
        }
    }
 
 
    dfs(0, 0);
    if (ans == "") writeln("Eel");
    else writeln(ans);
}

AtCoder Grand Contest 018 C - Coins

http://agc018.contest.atcoder.jp/tasks/agc018_c

問題概要

(X+Y+Z)人の人がいて、全員が金・銀・銅の3種類のコインを決められた枚数ずつ持っている。X人から金の、Y人から銀の、Z人から銅のコインをそれぞれその人が持っている分だけもらうとき、もらえるコインの枚数の最大値を求めよ。

解法

まず(金の保有枚数 - 銀の保有枚数)で人を降順にソートする。ソートした列をあるところで前後に区切ると、前の列の人からは金と銅だけ、後ろの列の人からは銀と銅だけもらうことを考えればよくなる(ソート条件より、前の人から銀をもらって後ろの人から金をもらうのは明らかに損なため)。

次に前列から金と銅をどのようにもらうかを考える。前列にK人いるとすると、X人から金のコインをもらい(K-X)人から銅のコインをもらうことになる。ここでK人を改めて(金の保有枚数 - 銅の保有枚数)で降順にソートすると、前半X人から金を、後半(K-X)人から銅をもらうのが最適になる。後列の銀と銅に関しても同様の計算ができる。

最終的な答えは前列と後列の区切り点を全探索し、各区切り点における最適な(金, 銅), (銀, 銅)の取り方を計算していくことで求めることができる。毎回前列・後列内のソートを行っていては間に合わないので、区切り点をスライドさせながらpriority queue等を使って値を管理していくと計算量がO( (X+Y+Z)log(X+Y+Z) )に抑えられる。

感想

一番最初のソートを入れることで単に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 s = readln.split.map!(to!int);
    auto X = s[0];
    auto Y = s[1];
    auto Z = s[2];
    auto N = X + Y + Z;
    auto A = new Tuple!(long, long, long)[](N);
    foreach (i; 0..N) {
        s = readln.split.map!(to!int);
        A[i] = tuple(s[0], s[1], s[2]);
    }
    A.sort!"a[1] - a[0] < b[1] - b[0]"();
 
    auto pq = new BinaryHeap!(Array!long, "a < b")();
    auto ans1 = new long[](N);
    long tmp = 0;
 
    foreach (i; 0..N) {
        ans1[i] = tmp;
        tmp += A[i][0];
        pq.insert(A[i][2] - A[i][0]);
        if (i + 1 > X) {
            auto t = pq.front;
            pq.popFront;
            tmp += t;
        }
    }
 
    
    pq.clear;
    auto ans2 = new long[](N);
    tmp = 0;
    
    foreach (i; 0..N) {
        ans2[i] = tmp;
        tmp += A[N-i-1][1];
        pq.insert(A[N-i-1][2] - A[N-i-1][1]);
        if (i + 1 > Y) {
            auto t = pq.front;
            pq.popFront;
            tmp += t;
        }
    }
 
 
    long ans = 0;
    foreach (i; 0..N) {
        if (i >= X && N - i >= Y) ans = max(ans, ans1[i] + ans2[N-i]);
    }
 
    ans.writeln;
}