Algoogle

Algorithm for Programming Contest

PA 2010 Termites

Category: PA Tag: greedy

Termites

問題概要


長さnの数列aがある.
今, 0に隣接した正の数を0にかえてその分の値をスコアとして得る.
これを2人で交互に繰り返す.
どちらも最適な行動を取るとき得られるスコアの総和を2人分求めよ.

解法


問題の操作はstackとdequeがいくつかあって, そのいずれかでpopしていくかんじ.
以降stackは配列の右側がtopで, 単調増加とかは左から右に見た時のことを指しているとする.
こういうゲームは自分が相手よりいくら勝っているかを考えると考えやすいことが多い.
前処理として数字をうまくマージすることでgreedyに落とすことができる.

どういうときにgreedyでできるか考える.
まずはdequeが1つの場合.
列が単調であれば取る方は大きい方でよい.
なぜなら偶数個であれば1個飛ばしで得られる列の大きいほうが得られ, 奇数個であればそれに一番小さい値が加わるだけだから.
そのようなdequeが2つ以上の場合は?
アクセス可能なところのうち大きい方から取ればよい.
2つの場合を考えると最適な取り方は片方に単調性が崩れないようにもう片方を適当な位置に挿入したになるため.

もう少しdequeを詰める.
dequeだけど大きい方しか見てないことと2つ以上あっても動き方は変わらない.
つまりdeque内の列が谷型でもよいということ(使わない小さい方を潰す).
列を谷型に直すのは単調に直すのより簡単(山になってる部分をマージする).

3つ並んだ数字x, y, zについて, を満たすときを考える.
この部分のxにアクセス可能なとき, これを取ると相手がyを取る.
これだけでは損だけでつらいのでzを取る(xを取らざるを得なかった状況でも当然zを取ることになる).
つまりxを取るとは相手よりx+y-zだけ多く得ると考えることができるので, x, y, zをx+y-zに置き換える.
これは多重にやってもいい. なぜなら置き換えた後はただの1つの数字だから.
また適用する順序は関係ない.
なぜならv, w, x, y, zとあるとき(条件は今は無視する),
v, w, xをマージするとv-w+x, y, zとなる. これをマージするとv-w+x-y+zとなる.
x, y, zをマージするとv, w, x-y+zとなる. これをマージするとv-w+x-y+zとなる.
w, x, yをマージするとv, w-x+y, zとなる. これをマージするとv-w+x-y+zとなる.

deque部分はこれでgreedyにできる!

stack部分は?
山部分が潰せるのは同じ.
それが単調非減少ならdequeの単調なものと同じ.
谷の形は前半がdequeと同じ.
つまりあとは単調減少になってる部分.

最後の2個x, y()を考える.
片方がyを取ったとき, 相手はxを取るのが最善.
なぜなら何もせずにx-yの差をつけることができるから.
つまりどちらもこの最後の2個は他に取れるのがなくなるまで取らない.
よって最初の個数の偶奇でどっちがとるか分かる(2個なので毎回同じ人が損する).
もっと言うと初期の個数だけで決まるということは最初に取り除いて良い.
これを繰り返すと単調減少になってる部分は消せる.

これであとはアクセス可能な部分の値でgreedyにできる.
priority queueに突っ込んでやりましょう.

コード


(termites.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
struct node
{
        long long val;
        int isl, idx;
        bool operator<(const node &v) const { return val < v.val;}
};

int n, m, ls[1<<20], rs[1<<20]; // [l,r)
long long s[1<<20], a[1<<20];

void merge(int l, int r, int p)
{
        int k = ls[m] = p;
        for (int i = l; i < r; i++) {
                s[k++] = a[i];
                while(k-ls[m] >= 3 and s[k-3] <= s[k-2] and s[k-2] >= s[k-1]) {
                        s[k-3] += s[k-1]-s[k-2];
                        k -= 2;
                }
        }
        rs[m++] = k;
}

long long merge2_left()
{
        int l = ls[0], r = rs[0], f = 0;
        long long val = 0;
        while(l+1 < r and s[l] > s[l+1]) {
                val += s[l+1]-s[l];
                l += 2;
                f = 1;
        }
        if(!f) return 0;
        ls[0] = l;
        return val;
}

long long merge2_right()
{
        int l = ls[m-1], r = rs[m-1], f = 0;
        long long val = 0;
        while(l+1 < r and s[r-1] > s[r-2]) {
                val += s[r-2]-s[r-1];
                r -= 2;
                f = 1;
        }
        if(!f) return 0;
        rs[m-1] = r;
        return val;
}

void solve()
{
        // merge phase
        int l = 0, r = 0, pr = 0;
        long long t = 0;
        priority_queue<node> q;
        while(r < n) {
                l = r;
                while(!a[l] and l < n) l++;
                r = l;
                while(a[r] and r < n) r++;
                if(l < r) {
                        merge(l,r,pr);
                        pr = rs[m-1];
                        // prepare for greedy
                        if(l == 0) { // left stack
                                t += merge2_left();
                                if(rs[0] > ls[0]) q.push((node){s[rs[0]-1], 0, 0});
                                ls[0]--; // guard
                        }
                        else if(r == n) { // right stack
                                t += merge2_right();
                                if(rs[m-1] > ls[m-1]) q.push((node){s[ls[m-1]], 1, m-1});
                                rs[m-1]++; // guard
                        }
                        else { // deque
                                if(rs[m-1] > ls[m-1]) q.push((node){s[ls[m-1]], 1, m-1});
                                if(rs[m-1] > ls[m-1]+1) q.push((node){s[rs[m-1]-1], 0, m-1});
                        }
                }
        }

        // greedy phase
        long long x = 0, sig = 1;
        while(!q.empty()) {
                node v = q.top(); q.pop();
                x += sig*v.val;
                sig *= -1;
                if(v.isl) {
                        ls[v.idx]++;
                        if(rs[v.idx] - ls[v.idx] > 1) q.push((node){s[ls[v.idx]], 1, v.idx});
                }
                else {
                        rs[v.idx]--;
                        if(rs[v.idx] - ls[v.idx] > 1) q.push((node){s[rs[v.idx]-1], 0, v.idx});
                }
        }
        x += sig*t;
        long long y = (accumulate(a,a+n,0)-x)/2;
        printf("%lld %lld\n", x+y, y);
}

void input()
{
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%lld", a+i);
}

int main()
{
        input();
        solve();
        return 0;
}

Comments