2019-04-07

Codeforces Global Round 2 E - Pavel and Triangles (R1900)

こういう貪欲は確実に抑えて行きたい

問題へのリンク

問題概要

長さが $2^{0}, 2^{1}, \dots, 2^{n-1}$ の線分がそれぞれ $a_{0}, a_{1}, \dots, a_{n-1}$ 本ずつある。

これらから三角形は最大で何個作れるか？

制約

$1 \le n \le 3 × 10^{5}$
$1 \le a_{i} \le 10^{9}$

考えたこと

面白そう！！！！！
$2^{k}$ な量を扱う問題リストにまた 1 問加えられる！！！！！

この手の問題では、 $2^{k-1}$ が 2 個束になっても $2^{k}$ は超えない、みたいな思考が大事になる。少し考えると、

$2^{a}, 2^{b}, 2^{c}$ ( $a \le b \le c$ ) で三角形ができるなら、 $a \le b = c$ であることが必要十分

ということがわかる。もし $b$ < $c$ であったならば、 $a$ を目一杯大きくして $a = b$ としても、 $2^{a} + 2^{b}$ が $2^{c}$ より大きくなることはないからだ。

よってこの問題は、 $0, 1, \dots, n-1$ がそれぞれ $a_{0}, a_{1}, \dots, a_{n-1}$ 個ずつあって、この中から $i \le j = k$ を満たすような三つ組を最大で何個とれるかを問いかける問題となる。

マッチングっぽい Greedy の解き方

三つ組の問題だけど、二つ組であればマッチング問題と言える。この手のマッチングは Greedy で解けると相場は決まっている。この問題も Greedy で解けるにちがいない。

そしてこの手の問題で考えるべきことは「最適解に対し、解を悪化させずに扱いやすい解に必ず変形できることを示せないか」ということな気がする。今回はあるマッチングが与えられたときに、マッチングの個数を減らさずに、より性質の良いマッチングに変形できることを示したい。

正三角形

まず、 $a_{i} \le 3$ となっている部分についての考察から始める。

$x$ が 3 個あって、 $x \le a = a$ , $x \le b = b$ , $x \le c = c$ ができているときは、 $a \le b \le c$ とすれば、 $x = x = x$ と $a \le c = c$ , $b \le c = c$ への組替えが可能
$x$ が 3 個あって、 $x \le a = a$ , $b \le x = x$ のときは、 $x = x = x$ と $b \le a = a$ への組替えが可能

ということから、割と正三角形は作ってしまっても良さそう。ただし注意すべき点が 1 つあって、「完全にすべて最初から正三角形を目一杯作る」とすると嘘で、例えば $a = a = a = a$ < $b = b = b = b$ < $c = c = c = c$ みたいなケースでは 4 つ作れるが、最初に正三角形を 3 個作ると、 $a$ < $b$ < $c$ が残って詰む。

それでも、 $x \le a = a$ , $x \le b = b$ , $x \le c = c$ から $x = x = x$ を含むように組替えられることから、以下のことは言える

(何個かマッチングを作って残ったやつのうち) 最小の長さのものが 3 個以上あったならば、その中では正三角形を目いっぱい作ってよい。

1 個と 2 個について

残ったマッチングのうち最小の長さのものが 1 個か 2 個の場合に帰着された。例えば

1, 1, 2, 2, 3, 3

みたいなケースでは、1 はバラバラにして、

1, 2, 2
1, 3, 3

の 2 個を作るのがよい。さて、 $a \le b = b$ な組であって、この $a, b, b$ がそれぞれ独立に異なる 3 個の三角形の頂点として使われているケースでは、 $a \le b = b$ な三角形を含むように組替えができることは示せる。

つまり、

$a \le c = c$
$b \le d = d$
$b \le e = e$

となっているならば、 $a \le b = b$ で組んでしまって、残りの $c = c, d = d, e = e$ でさらに 2 個組むことができる。

ここから言えることは、

残ったやつのうち最小のものが

孤立点 $a$ のときは、 $a$ より大きくて 2 つ揃ってる最小の $b = b$ を見つけてマッチングさせて損はない ( $b$ をバラバラに使っても得しない)
2 つ組 $a = a$ のときは、それぞれの $a$ について、孤立点と同様の扱いをすればよい

ということになる。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    
    // 2 個以上あるところを管理
    priority_queue<int, vector<int>, greater<int> > que;
    for (int i = 0; i < N; ++i) if (a[i] >= 2) que.push(i);
    
    // 小さい方から Greedy
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        res += a[i] / 3;
        a[i] %= 3;
        for (int iter = 0; iter < a[i]; ++iter) {
            while (!que.empty() && que.top() <= i) que.pop();
            if (que.empty()) continue;
            int j = que.top(); que.pop();
            res++; a[j] -= 2;
            if (a[j] >= 2) que.push(j);
        }
    }
    cout << res << endl;
}