CODE FESTIVAL 2016 qual B D Greedy customers

所見

700初自力AC

atcoder.jp

問題概要

長さNの整数列Aについて以下の操作を繰り返し行う。

• ある正整数Pを決め、Ai >= P なる最小のiについて、Ai -= P をする。

任意のiについてAiが0にならないように操作を行うとき、操作は最大何回できるか。

取った方針

前から順番にAiを1にしていくことを考える。
理由:

• 数列の前の方に大きい数字があるとその数字が操作の対象になってしまうから。
• i > j のとき、Ai にAj 以下のPを作用させることはできない。(Ajが対象になってしまうので)
• 操作の回数を大きくしたいとき、Pは小さい方が有利であるから。
  • 小さいPを数列の後ろの方に作用させたい時、その前にある数はなるべく小さいと都合がよい。

0番目の数は、1をAi-1回引くことで1にできる。
次にPを1にすることはできないので、Pを2にすることを考える。
Pが2の時、以下をすると行える操作数が最大。

• Aiが奇数のとき、Ai/2回2を引く。
• Aiが偶数のとき、Ai/2 - 2回2を引き、1回3を引く(行われる操作はAi/2-1回)

ここで、Aiが2の時はP を2にすることはできず、Pを3にすることになる。

Pがnの時、以下をすると行える操作数が最大。

• Aiがnで割り切れないとき、Ai/N - 1回nを引き、最後の1回はAi == 1 となるようにPを定める。(操作回数はAi/N回)
• Aiがnで割り切れるとき、Ai/N - 2回nを引き、最後の1回はAi == 1となるようにPを定める。(操作回数はAi/N-1回)

よって、Ai==P なるAiが現れる度にPをインクリメントしながら上記の計算を行えばよい。それを行うコードは以下

int ans = A[0] - 1;
int P = 2;
for (int i = 1; i < N; i++) {
    if (P == A[i]) {
        P++;
        continue;
    }

    int sell = A[i] % P == 0 ? A[i] / P - 1 : A[i] / P;
    ans += sell;
}

正しい方針

同上

得られた知見

• かしこい貪欲

解くのに必要な要素

• 実験……
• 手でシミュレーションするの大事(口だけ)

周辺調査によって得られた知見

特になし