2020-11-15

AtCoder AGC 049 C - Robots (黄色, 800 点)

AtCoder AtCoder800点黄色diff コーナーケース最適化テク:最適解の形を考えるロボット条件の言い換え操作最小コスト Greedy:各要素について独立に考えてよい操作によって作れるものの集合を考える(判定関数を考える) 操作の流れを単純化する一直線上のN点の問題 AGC-C 点が移動していく問題最適化問題

11 WA の末に通した...

問題へのリンク

問題概要

初期状態では、数直線上の座標 $0, 1, \dots, 10^{100}$ の位置にロボット $0, 1, \dots, 10^{100}$ がいる。

一方、たくさんのボールがある。ボールの情報は長さ $N$ の整数列 $A$ と $B$ で表される。具体的には、各 $i (1 \le i \le N)$ について、 $A_{i}$ の書かれたボールが $B_{i}$ 個ある。

今からすぬけくんは、次の操作を行う。

Step 1: 0 個以上のボールを選び、そこに書かれている整数を $1$ 以上 $10^{100}$ 以下の好きな正整数に書き換える (ボールごとに書き換える整数を選択できる)
Step 2: ボールを 1 つずつ食べる。ボールを食べる順番は自由に選べる。ボールを食べるたびに，以下の操作を行う。
- 今食べたボールに書かれた整数を $v$ とする
- ロボット $v$ が存在するならば、それを現在の座標より 1 小さい座標へ移動させる。もし移動先に別のロボットがいるならば、そのロボットは破壊される )ロボット $v$ は無事である）

すぬけくんは、ロボット 0 が破壊されないように、すべてのボールを食べきりたいです。すぬけくんが目標を達成するために Step 1 で書き換える必要のあるボールの個数の最小値を求めよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

無数の嘘解法を生やしてしまった。すごく反省。この問題は気づくべきポイントがいくつかある。

とりあえず、ロボット $A_{i}$ が破壊されたようなボール $i$ は、周囲に影響を与えることなく食べることができることに注意する。そうすると、ロボットという設定は無視してしまって、次のように捉え直して OK。

ボール $i$ は 1 個だけあって、数値 $B_{i}$ が書かれていて、座標 $A_{i}$ の位置にある
ボール $i$ は数値が正である限りは左に動かすことができる。左に 1 動かすと数値は 1 減少する (これを「食べる」と呼ぶことにする)
ボール $i$ が左に動いたとき、その場にあるボールは破壊される

ちょっと考えやすくなった。また、既存のボールに対してコスト 1 を支払うことで、そのボールの数値を 1 減らし、ボールのない位置に数値 $1$ のボールを出現させたり、すでにあるボールの数値を $1$ 増やしたりできる。

ポイント(1)；操作完了可能かどうかの判定

まずはそもそも、与えられたボール集合をすべて無事に食べることができる条件を特徴付けなければならない。そしてそれは次のように言える。

$A_{i} \gt B_{i}$ であるボール $i$ を無害
$A_{i} \le B_{i}$ であるボール $i$ を有害

であると呼ぶことにすると、次のように考えられる。まずは無害ボールを $A_{i}$ が小さい順に、すべて食べていく。

ボール $i$ をすべて食べると、 $A_{j} \le A_{i} - B_{i}$ であるようなボール $j$ はすべて破壊される (有害なボールもすべて丸ごと破壊される)。

この作業終了後に、有害なボールが残らなければよい。つまり、条件は次のように言える。

すべての有害なボール $j$ について
$A_{j} \lt A_{i}$ かつ $1 \le A_{i} - B_{i} \le A_{j}$ であるようなボール $i$ が存在する

ポイント(2)：削除不能な有害ボールはコスト 1 で自力破壊できる

ここに気づくのに時間がかかった。たとえば $A = 9, B = 1000$ のような圧倒的有害ボールもあっさり削除できる。具体的には、1000 個のうちの 1 個の数値を 10 に書き換える。そしてそのボールを食べればよい。

このとき、 $A_{i} = 10$ であるようなボール $i$ が存在するのではないかと気になるところだが、もしそのボールが無害だったらそもそもそれを動かすことで $A = 9$ のボールを削除可能なので矛盾。有害だったら、仮にその有害ボールを活用して $A = 9$ のボールを削除したとしても、その有害ボールを削除するのにさらにコスト 1 が追加で必要なので、結局変わらない。

よってシンプルに、有害ボール 1 個につき、コスト 1 で破壊できるものと考えて OK。

ポイント(3)：有害ボールはある一定コストを払うことで有用ボールに早変わりすることも！

これも気づくのに時間がかかったけど、たとえば $A = 9, B = 11$ といった有害ボールがあったとする。このとき有害ボールのうちの $B - A + 1 (= 3)$ 個を書き換えると、 $A = 9, B = 8$ の状態になる。

これは、座標 1 まで軒並みボールを破壊し尽くすという有用ボールに早変わりする！！！場合によっては有効活用したい。

ポイント(4)：有害ボールを有用ボールにするコストで、他の有害ボール潰しができる

最後にこれになかなか気付けなかった！！！たとえば

$(A, B) = (9, 11), (15, 100), (16, 110), (30, 80)$

というケースでは、1 種類目のボールのうちの 3 個を書き換えて

$(9, 8)$
$(17, 2)$
$(31, 1)$

というふうにすることで、3 種の有害ボール $(15, 100), (16, 110), (30, 80)$ をすべて潰すことができる。

以上を踏まえて

以上を踏まえて、次のような解法が考えられる。

以下のいずれかの最小値を求める

有害ボールを有用ボールに変換する操作を行わない場合の最小コスト：削除不可能な有害ボールの個数
有害ボールを有用ボールに変換する場合の最小コスト
- $c = B_{i} - A_{i} + 1$ のコストを支払う
- このとき、 $i+1$ 番目以降の、削除不可能な有害ボールの個数を $n$ として、 $\max(0, n - c)$ の追加コストを支払う
- なおこのとき、ボール $i$ 自身は削除可能であってもよい

計算量は $O(N)$ となる。

コード

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

int main() {
    int N;
    cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];

    const long long INF = 1LL<<60;
    long long res = INF;
    long long num = 0, vmin = INF;
    for (int i = N-1; i >= 0; --i) {
        // harmless
        if (A[i] > B[i]) vmin = min(vmin, A[i] - B[i]);
        // harmful and not can be deleted
        else {
            long long c = B[i] - A[i] + 1;
            res = min(res, c + max(0LL, num - c));
            if (A[i] < vmin) ++num;
        }      
    }
    res = min(res, num);
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます