【AtCoder】ABC 388 E - Simultaneous Kagamimochi | 緑コーダーが解くAtCoder

atcoder.jp

配点: 450 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1068

C問題の発展バージョン。

問題概要
制約
考察
実装例
コメント

問題概要

$N$ 個の餅が小さい順に並んでおり、 $i$ 番目の餅の大きさは $A_i$ である。

2つの餅 $A,B$ の大きさをそれぞれ $a,b$ としたとき、 $a \leq \frac{b}{2}$ であるときに限り、餅 $A$ を餅 $B$ の上に乗せて鏡餅を1つ作ることができる。

このとき、同時にいくつの鏡餅を作ることができるか求めよ。より厳密には、以下ができるような最大の非負整数 $K$ を求めよ。

$N$ 個の餅から $2K$ 個の餅を選んで $K$ 個の2つ組に分け、一方の組の餅ををもう一方組の餅の上に乗せることで鏡餅を $K$ 個作る

制約

$2\leq N\leq 5\times 10^5$
$1\leq A_i\leq 10^9$
入力はすべて整数。

考察

$0 \leq k \leq \bigl\lfloor \frac{N}{2} \bigr\rfloor$ 個の鏡餅を作ることを目指して、餅同士のマッチングを考えよう。

このマッチングで大切な(直感的な)考え方は、

上の餅はなるべく小さく、下の餅はなるべく大きく ・・・(☆)

である。

以下の例で考えてみよう。なお、餅は左から小さい順に並んでいるとし、線でつながれた餅同士は鏡餅を構成しており、×印の餅は鏡餅を構成していない餅であることを示す。

とりあえず適当にマッチングをさせてみたが、よく見るとこれは先ほどの(☆)の考え方に反していることが分かるだろうか。

例えば、「1 - 4」と「6 - 8」のマッチングについて、「1 - 6」と「4 - 8」と組み替えても問題はない。

簡単な証明

餅 $A, B,C, D$ の大きさをそれぞれ $a, b, c, d$ とする。ここで、 $a \leq b \leq c \leq d$ である。

今、「 $A - B$ 」と「 $C - D$ 」というマッチングがあったとする。つまり、 $a \leq \frac{b}{2}, \: c \leq \frac{d}{2}$ が成り立っている。

このとき、 $b \leq c$ であることを利用すると、 $a \leq \frac{b}{2} \leq \frac{c}{2}, \: b \leq c \leq \frac{d}{2}$ と書けるので、「 $A - C$ 」及び「 $B - D$ 」のマッチングも可能である。

さらに、「3 - 7」のマッチングについては、使われていない「2」と上の餅を入れ替えて、「2 - 7」としてもよい。これは自明だと思う。

これを一般化すると、

「下, 上」の並びがあれば、「上, 下」に入れ替える
「×, 上」の並びがあれば、「上, ×」に入れ替える

とマッチングし直せばよい。これを行うと、上の例は次のようになる。

綺麗に「上」を前に、「下」を後ろに並べることができた。

ということは、 $k$ 個の鏡餅を作りたいときは

先頭 $k$ 個と後方 $k$ 個の餅を使う

という、(☆)の考え方に沿った貪欲なやり方で良いことが分かった。

あとはこの $k$ を最大化しよう。

「ある $k$ について $k$ 個の鏡餅を作れるかどうか」は、各 $i =1, 2, \cdots, k$ に対して $2A_i \gt A_{N - k + i -1}$ が成り立つかどうかをチェックすれば十分(実装例では 0-indexed)。

また、 $k$ 個の鏡餅が作ることができるのなら、それより少ない個数の鏡餅も全て作ることができるので、問題文中の $K$ は $0$ から $\bigl\lfloor \frac{N}{2} \bigr\rfloor$ の範囲で二分探索をすることによって求められる。

全体の計算量は $O(N \log N)$ となり、本問の制約下では十分高速だ。

実装例では、めぐる式二分探索を使っているが、公式解説ではこの部分を関数化したpartition_pointを用いているようだ。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];

    int ok = 0, ng = N / 2 + 1;
    while (ng - ok > 1)
    {
        int mid = (ok + ng) / 2;
        bool flag = true;
        rep(i, 0, mid)
        {
            if (A[i] * 2 > A[N - mid + i])
            {
                flag = false;
                break;
            }
        }

        if (flag)
            ok = mid;
        else
            ng = mid;
    }

    cout << ok << endl;

    return 0;
}