Official

G - Quintuple Scoop Ice Cream Editorial by MMNMM

この解説では、以下の \(2\) つのパートに分けて問題の解説を行います。

  1. \(K\) の上界を求める
  2. 上界を達成するアルゴリズムを考える

1. \(K\) の上界を求める

\(K\) 個の \(5\) 段アイスを買えるような非負整数 \(K\) が満たす条件について考えてみましょう。

\(K\) を固定したとき、\(x\) 番目のフレーバーのアイスは、\(\min\lbrace C_x,3K\rbrace\) 個まで買うことができます（同じ種類のアイスを \(3K\) 個より多く買うと、必ずどこかで隣接してしまいます）。 よって、次の条件が成り立っている必要があります。

  • \(\displaystyle5K\leq\sum _ {x=1} ^ N\min\lbrace C _ x,3K\rbrace\)

この条件を変形して、次の \(2\) つの条件が得られます。

  • \(\displaystyle5K\leq\sum _ {x=1} ^ NC _ x\)
  • \(\displaystyle2K\leq\sum _ {x=1} ^ NC _ x-\max _ {1\leq x\leq N}C _ x\)

導出

上は、\(\min\lbrace C _ x,3K\rbrace\leq C _ x\) の両辺を \(x=1,2,\ldots,N\) について足すことで得られます。

下は、\(\displaystyle C _ k=\max _ {1\leq x\leq N}C _ x\) なる \(k\) を \(1\) つ選び、\[\min\lbrace C _ x,3K\rbrace\leq\begin{cases}3K&\ &(x=k)\\C _ x&&(x\neq k)\end{cases}\] の両辺を \(x=1,2,\ldots,N\) について足すことで得られます。

よって、\(K\) の上界として \(K _ c\coloneqq\displaystyle \min\Biggl\lbrace\left\lfloor\dfrac15\sum _ {x=1} ^ NC _ x\right\rfloor,\left\lfloor\dfrac12\left(\sum _ {x=1} ^ NC _ x-\max _ {1\leq x\leq N}C _ x\right)\right\rfloor\Biggr\rbrace\) を得ることができます。

実は、この上界が達成可能です。

2. 上界を達成するアルゴリズム

\(K _ c\gt0\) のとき、適切に \(5\) 段重ねのアイスを作って \(K _ c\) を \(1\) だけ減らすことができれば、これを繰り返すことで \(K=K _ c\) を実現することができます。

実は、「使えるフレーバーの中で最も残り個数が多いものを使う」を繰り返すことで、\(5\) 段重ねのアイスをひとつ作って \(K _ c\) を \(1\) だけ減らすことができます。

より厳密な形でアルゴリズムを示します。

適当に順序を入れ替えることで、\(C _ 1\geq C_2\geq\dotsb\geq C _ N\) としておきます。

次のアルゴリズムを考えます。

  • \(x=0,f=()\) とし、次の操作を \(5\) 回繰り返す。
    • \(\displaystyle C _ i=\max _ {1\leq i\leq N,i\neq x}C _ i\) となる最小の \(i\ (i\neq x)\) を求める。
    • \(x=i\) とし、\(f\) の末尾に \(i\) を追加する。
    • \(C _ i\) の値を \(1\) だけ減らす。
  • 出来上がった長さ \(5\) の列 \(f\) を買うべき \(5\) 段重ねのアイスとする。

操作を行う前に \(K _ c\gt0\) ならば

  • できあがる \(f\) を買えること
  • 操作を終えたのちの \(C\) に対する \(K _ c\) の値が \(1\) だけ減っていること

を示せば、このアルゴリズムの正当性が示せます。

証明

\(C _ 1,C _ 2,\ldots,C _ 5\) の値によって場合分けを行います。

  1. \(C _ 1=C _ 5\) のとき
  2. \(C _ 1=C _ 4\gt C _ 5\) のとき
  3. \(C _ 1=C _ 3\gt C _ 4\) のとき
  4. \(C _ 1=C _ 2+1=C _ 4+1\) のとき
  5. \(C _ 1\gt C _ 2=C _ 3\) かつ 4. でないとき
  6. \(C _ 1=C _ 2=C _ 3+1\) のとき
  7. \(C _ 1\gt C _ 3+1\) かつ \(C _ 2\gt C _ 3\) のとき

1. \(C _ 1=C _ 5\) のとき

\(C _ 1=C _ 5\) のとき \(f=(1,2,3,4,5)\) となり、\(C _ 1,C _ 2,C _ 3,C _ 4,C _ 5\) は \(1\) ずつ減ります。 \(K _ c\gt0\) なので \(\displaystyle\sum _ {x=1} ^ NC _ x\geq5\) であり、\(C _ 1\geq1\) です。 よって、\(f\) を買うことができます。 また、\(\displaystyle C _ 1=\dfrac{C _ 1+C _ 2+C _ 3+C _ 4+C _ 5}5\leq\dfrac15\sum _ {x=1} ^ NC _ x\) なので \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\geq\dfrac25\sum _ {x=1} ^ NC _ x\geq1+\dfrac15\sum _ {x=1} ^ NC _ x=1+K _ c\) です。 操作の前後で \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\) は \(2\) 、\(\displaystyle\dfrac15\sum _ {x=1} ^ NC _ x\) は \(1\) だけ減少するので、操作の前後で \(K _ c\) は \(1\) だけ減っています。

2. \(C _ 1=C _ 4\gt C _ 5\) のとき

\(C _ 1=C _ 4\gt C _ 5\) のとき \(f=(1,2,3,4,1)\) となり、\(C _ 1\) は \(2\) 、\(C _ 2,C _ 3,C _ 4\) は \(1\) ずつ減ります。 \(K _ c\gt0\) なので \(\displaystyle\sum _ {x=1} ^ NC _ x\geq5\) であり、\(C _ 1\geq2\) です。 よって、\(f\) を買うことができます。 また、\(\displaystyle C _ 1=\dfrac{C _ 1+C _ 2+C _ 3+C _ 4}4\leq\dfrac14\sum _ {x=1} ^ NC _ x\) なので \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\geq\dfrac38\sum _ {x=1} ^ NC _ x\geq\dfrac75+\dfrac15\sum _ {x=1} ^ NC _ x=\dfrac75+K _ c\) です。 操作の前後で \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\) は \(\dfrac32\) 、\(\displaystyle\dfrac15\sum _ {x=1} ^ NC _ x\) は \(1\) だけ減少するので、操作の前後で \(K _ c\) は \(1\) だけ減っています。

3. \(C _ 1=C _ 3\gt C _ 4\) のとき

\(C _ 1=C _ 3\gt C _ 4\) のとき \(f=(1,2,3,1,2)\) となり、\(C _ 1,C _ 2\) は \(2\) ずつ、\(C _ 3\) は \(1\) 減ります。 \(K _ c\gt0\) なので \(\displaystyle\sum _ {x=1} ^ NC _ x\geq5\) であり、\(C _ 1\geq2\) です。 よって、\(f\) を買うことができます。 また、\(\displaystyle C _ 1=\dfrac{C _ 1+C _ 2+C _ 3}3\leq\dfrac13\sum _ {x=1} ^ NC _ x\) なので \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\geq\dfrac13\sum _ {x=1} ^ NC _ x\geq\dfrac45+\dfrac15\sum _ {x=1} ^ NC _ x=\dfrac45+K _ c\) です。 操作の前後で \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\) は \(\dfrac32\) 、\(\displaystyle\dfrac15\sum _ {x=1} ^ NC _ x\) は \(1\) だけ減少するので、操作の前後で \(K _ c\) は \(1\) だけ減っています。

4. \(C _ 1=C _ 2+1=C _ 4+1\) のとき

\(C _ 1=C _ 2+1=C _ 4+1\) のとき \(f=(1,2,1,3,4)\) となり、\(C _ 1\) は \(2\) 、\(C _ 2,C _ 3,C _ 4\) は \(1\) ずつ減ります。 \(K _ c\gt0\) なので \(\displaystyle\sum _ {x=1} ^ NC _ x\geq5\) であり、\(C _ 1\geq2\) です。 よって、\(f\) を買うことができます。 また、\(\displaystyle\dfrac12C _ 1\leq\dfrac{C _ 1+C _ 2+C _ 3+C _ 4}5\leq\dfrac15\sum _ {x=1} ^ NC _ x\) なので \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\geq\dfrac3{10}\sum _ {x=1} ^ NC _ x\geq\dfrac12+\dfrac15\sum _ {x=1} ^ NC _ x=\dfrac12+K _ c\) です。 操作の前後で \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\) は \(\dfrac32\) 、\(\displaystyle\dfrac15\sum _ {x=1} ^ NC _ x\) は \(1\) だけ減少するので、操作の前後で \(K _ c\) は \(1\) だけ減っています。

5. \(C _ 1\gt C _ 2=C _ 3\) かつ 4. でないとき

\(C _ 1\gt C _ 2=C _ 3\) かつ 3. でないとき \(f=(1,2,1,3,1)\) となり、\(C _ 1\) は \(3\) 、\(C _ 2,C _ 3\) は \(1\) ずつ減ります。 \(K _ c\gt0\) なので \(\displaystyle\sum _ {x=1} ^ NC _ x\geq5\) であり、\(C _ 1\geq3\) です。 よって、\(f\) を買うことができます。 操作の前後で \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\) と \(\displaystyle\dfrac15\sum _ {x=1} ^ NC _ x\) はどちらも \(1\) だけ減少するので、操作の前後で \(K _ c\) は \(1\) だけ減っています。

6. \(C _ 1=C _ 2=C _ 3+1\) のとき

\(C _ 1=C _ 2=C _ 3+1\) のとき \(f=(1,2,1,2,3)\) となり、\(C _ 1,C _ 2\) は \(2\) ずつ、\(C _ 3\) は \(1\) 減ります。 \(K _ c\gt0\) なので \(\displaystyle\sum _ {x=1} ^ NC _ x\geq5\) であり、\(C _ 1\geq2\) です。 よって、\(f\) を買うことができます。 また、\(\displaystyle\dfrac12C _ 1\leq\dfrac{C _ 1+C _ 2+C _ 3}5\leq\dfrac15\sum _ {x=1} ^ NC _ x\) なので \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\geq\dfrac3{10}\sum _ {x=1} ^ NC _ x\geq\dfrac12+\dfrac15\sum _ {x=1} ^ NC _ x=\dfrac12+K _ c\) です。 操作の前後で \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\) は \(\dfrac32\) 、\(\displaystyle\dfrac15\sum _ {x=1} ^ NC _ x\) は \(1\) だけ減少するので、操作の前後で \(K _ c\) は \(1\) だけ減っています。

7. \(C _ 1\gt C _ 3+1\) かつ \(C _ 2\gt C _ 3\) のとき

\(C _ 1\gt C _ 3+1\) かつ \(C _ 2\gt C _ 3\) のとき \(f=(1,2,1,2,1)\) となり、\(C _ 1\) は \(3\) 、\(C _ 2\) は \(2\) 減ります。 \(K _ c\gt 0\) なので \(\displaystyle\sum _ {x=2} ^ NC _ x\geq2\) かつ \(\displaystyle\sum _ {x=1} ^ NC _ x\geq5\) であり、\(C _ 2\geq2\) かつ \(C _ 1\geq3\) です。 よって、\(f\) を買うことができます。 操作の前後で \(\displaystyle\dfrac12\sum _ {x=2} ^ NC _ x\) と \(\displaystyle\dfrac15\sum _ {x=1} ^ NC _ x\) はどちらも \(1\) だけ減少するので、操作の前後で \(K _ c\) は \(1\) だけ減っています。

この手順を行うのにかかる時間計算量は、\(\displaystyle C _ i=\max _ {1\leq i\leq N,i\neq x}C _ i\) となる最小の \(i\ (i\neq x)\) を素朴に求めると \(O(N)\) となりますが、二分ヒープを用いて \(C _ i\) を管理することで \(O(\log N)\) とすることができます。

あとは、これを \(K _ c\) 回繰り返すことでこの問題を解くことができました。 時間計算量は \(\displaystyle\Theta\left(N+\sum _ {i=1} ^ N C _ i\log N\right)\) となり、十分高速です。

より高速な解法

余談ですが、より具体的な形で買うべき \(5\) 段重ねのアイスを構成することで時間計算量を \(\Theta(N)\) にすることができます。

詳細には踏み込みませんが、最大の \(C _ i\) が \(2K\) 以上かどうかで場合分けをすることでそれぞれ構築をすることができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <ranges>
#include <utility>

int main() {
    using namespace std;

    // A_{1,-}, A_{3,-}, A_{5,-}, A_{2,-}, A_{4,-} の順に並んだフレーバーの列を受け取り、
    // 5 段アイスの形にして出力する関数
    const auto print_5dan_ice{[](auto&& range){
        const auto flavors = ranges::begin(range);
        const auto N{ranges::size(range) / 5};
        for(unsigned i{}; i < N; ++i){
            string delim{};
            for(unsigned j{}; j < 5; ++j)
                cout << exchange(delim, " ") << flavors[j * 3 % 5 * N + i];
            cout << endl;
        }
    }};

    unsigned N;
    cin >> N;
    vector<unsigned> C(N);
    for(auto&& c : C)
        cin >> c;

    // 最適な K は min(∑C[x] / 5, (∑C[x] - maxC[x]) / 2)
    const auto K = min(reduce(begin(C), end(C)) / 5, (reduce(begin(C), end(C)) - ranges::max(C)) / 2);

    // 実際にフレーバー x を購入する個数 B[x]
    vector<unsigned> B = C;

    // 各 B[x] は 3K 以下
    for(auto&& b : B)
        b = min(b, 3 * K);

    // ∑B[x] が 5K になるまで減らす
    for(auto remains = reduce(begin(B), end(B)) - 5 * K; auto&& b : B){
        const auto k{min(remains, b)};
        b -= k;
        remains -= k;
    }

    // x の昇順に、x が B[x] 個ずつ並んだ列
    vector<unsigned> flavors(5 * K);
    ranges::copy(views::iota(0U, N) | views::transform([&B](unsigned x) {return vector<unsigned>(B[x], x + 1);}) | views::join, begin(flavors));

    cout << K << endl;

    // B が最大となる x
    const auto x_max = ranges::max_element(B) - begin(B);

    if (B[x_max] <= 2 * K)
        // B[x_max] <= 2K ならそのまま出力
        print_5dan_ice(flavors);
    else {
        // 2K < B[x_max] なら、前 5α 個 と後ろ 5(K-α) 個に分けて出力
        const auto alpha = B[x_max] - 2 * K;
        ranges::rotate(flavors, ranges::lower_bound(flavors, x_max + 1) + 2 * (K - alpha));
        print_5dan_ice(flavors | views::take(5 * alpha));
        print_5dan_ice(flavors | views::drop(5 * alpha));
    }
    return 0;
}

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>

int main() {
    using namespace std;
    unsigned N;
    cin >> N;
    vector<unsigned> C(N);
    for (auto &&c : C)
        cin >> c;

    // 最適な K は min(∑C[x] / 5, (∑C[x] - maxC[x]) / 2)
    const auto K = min(reduce(begin(C), end(C)) / 5, (reduce(begin(C), end(C)) - ranges::max(C)) / 2);
    cout << K << endl;

    // (残り個数, フレーバー)
    priority_queue<pair<unsigned, unsigned>> pq;
    for (unsigned i = 0; const auto c : C)
        pq.emplace(c, ++i);

    // 一つ下にあるフレーバーをとり、次に乗せるべきフレーバーを求める関数
    const auto next_flavor{[&pq](unsigned prev) {
        // 残っている個数が最大のもの
        const auto [amount, flavor] = pq.top();
        pq.pop();
        // 直前に乗せたフレーバーと違う味ならそれを乗せる
        if (flavor != prev) {
            // 在庫を減らして priority_queue に追加
            pq.emplace(amount - 1, flavor);
            return flavor;
        }
        // 同じ味なら次に多いものを乗せる
        const auto [second_amount, second_flavor] = pq.top();
        pq.pop();
        // 在庫を減らして priority_queue に追加
        pq.emplace(second_amount - 1, second_flavor);
        pq.emplace(amount, flavor);
        return second_flavor;
    }};

    // K 回 5 段アイスを出力
    for (unsigned i = 0; i < K; ++i) {
        for (unsigned prev = 0, j = 0; j < 5; ++j) {
            prev = next_flavor(prev);
            cout << prev << " ";
        }
        cout << endl;
    }
    return 0;
}

posted:
last update: