Mister雑記

競プロやります。

AGC027-B 「Garbage Collector」 (700)

点数に疑問はあるが、普通に良い問題。

問題リンク

概要

数直線上に N個のゴミとゴミ箱とロボットが置かれており、ゴミ箱とロボットは座標0に、 i番目のゴミは座標 x_iに置かれている。

これから、ロボットが数直線上を移動してゴミをゴミ箱へ捨てていく。動作にかかるエネルギーは以下の通り。

  • ゴミを1つ拾うのと、ゴミを1回ゴミ箱に入れるのに X
    • ゴミはいくつ同時に捨てても消費するエネルギーは Xで変わらない。
  • ゴミを k個持っているとき、1移動するのに (k + 1)^2

また、一度拾ったゴミをゴミ箱以外に置くことはできない。

このとき、ロボットが N個のゴミを全てゴミ箱へ捨てるのにかかるエネルギーの最小値を求めよ。

制約

  •  1 \leq N \leq 2 \times 10^5
  •  0 \lt x_1 \lt \dots \lt x_N \leq 10^9
  •  1 \leq X \leq 10^9

解説

この問題で最も大事なのは、実際に手を動かしてみることに他ならない。 初見は手の付け所がないように見えるが、ゴリゴリ式を整理していくうちにだんだん構造が見えてくる。

一度に K個回収するエネルギー

まず消費エネルギーがどういう値になるかを探るために、

  • ゴミが K個だけ置かれている
  • 全部まとめて一度にゴミ箱へ捨てる

ときの消費エネルギーを具体的に求めてみよう。

まず行動パターンだが、「一番奥まで行って、帰りがけに回収する」というのが最善となる。 これは道中でゴミを拾った場合、一番奥まで行ってそこに戻ってくるまでの間により多くのエネルギーを消費してしまうことから分かる。

では消費エネルギーを計算してみよう。以下に K = 4の場合を示す。

f:id:misteer:20180917214506p:plain

これは実際に手を動かせば分かるが、消費エネルギーは

 \displaystyle (2K + 1)x_1 + (2K - 1)x_2 + \dots + 7x_{K - 2} + 5x_{K - 1} + 5x_K

となる。

往復回数を固定

では、往復回数 tを固定したときのエネルギーの最小値について考えてみよう。

 t = 1は上で示した通りなので、次は t = 2について考えてみる。

ただ式で考えると理解しづらいので、「各変数についている係数」を図示して考えてみよう。

具体的に N = 10のときを考える。例えばこのとき、1回目で後ろ4個、2回目で残り6個を回収するという方法が考えられる(下図上)。

しかし、回収するゴミを交互にすることで大きい係数を手前にずらすことができるため、そちらの方が効率的である(下図中)。

さらに、回収するゴミの数を2回の往復で均一にすることで、全体の係数の最大値をより小さく抑えることができる(下図下)。

f:id:misteer:20180917214529p:plain

これは t \gt 2でも同じ話で、例えば t = 3なら以下のようになる。

f:id:misteer:20180917214555p:plain

計算量の削減

これで往復回数を固定したときのエネルギーの最小値が分かったが、愚直に計算していると各 tについて計算量は O(N)となり部分点しかとれない。

そこで、 xの累積和を予め求めておくことで計算量を削減する。具体的には、右端を tずつ引きながら累積和を足し上げていけばいい(この辺は言葉で伝えるより下のコードを見た方がわかりやすいと思う)。

一見するとこれでも全体の計算量は O(N^2)から変わらないように見える。しかし、各 tにおける計算量は正確には O(N / t)であり、調和数列の近似

 \displaystyle \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{N} \simeq \log N

から、全体の計算量は O(N \log N)まで落ちていることになる。これで満点が取れる。

実装例

ここまでの考察がちゃんとできていれば、実装自体はウィニングランみたいなものである。

ただし、一部の tでは64bit整数でもオーバーフローを起こす可能性があるため要注意(3敗)。

#include <iostream>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

int main() {
    ll N, X;
    cin >> N >> X;

    ll sum[N + 1];
    sum[0] = 0;
    for (int i = 1; i <= N; ++i) {
        ll x;
        cin >> x;
        sum[i] = sum[i - 1] + x;
    }

    ll ans = INF;
    for (ll t = 1; t <= N; ++t) {
        // ゴミ捨てとゴミ拾いに消費するエネルギー
        ll cost = (N + t) * X;

        ll now = N;  // 右端

        cost += sum[now] * 5;
        now -= t * 2;
        while (now > 0) {
            cost += sum[now] * 2;
            now -= t;

            // オーバーフロー対策
            if (cost < 0) {
                cost = INF;
                break;
            }
        }
        ans = min(ans, cost);
    }

    cout << ans << endl;
    return 0;
}

感想

  • 少しでも多くの人の理解の助けになれたら幸いである。
  • 上位で飛ばした人が多いのは、点数が考察にかかる時間と割に合わなかったからだろう。
  • なんで700点なんですかねホント。