教育的 Greedy 問題！

問題概要

$N$ 個の整数からなる数列 $A_1, \dots, A_N$ と数列 $B_1, \dots, B_N$ がある。以下の操作を好きな回数だけ行える:

$N$ 以下の整数 $i$ を 1 つ選び、 $A_1, \dots, A_i$ の値を $1$ ずつ増やす

すべての $i$ に対して $A_i$ が $B_i$ の倍数となるようにしたい。これを実現するための操作回数の最小値を求めよ。

制約

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

考えたこと

ひとまず問題を以下のように言い換えます。数列 $D_1, D_2, \dots, D_N$ であって

$D_1 \ge D_2 \ge \dots \ge D_N$
$A_i + D_i$ が $B_i$ の倍数

を満たすもののうち、 $D_1$ の最小値を求める問題と言い換えることができます。

後ろの方から前の方に行くにつれて、ドンドン差分が大きくなっていくイメージです。

Greedy

世の中には Greedy が成立する問題と、そうではない問題とがあります。その違いはどこにあるのか、この問題を通して考えてみます。

とりあえずこの問題でまず思い浮かぶのは、

$A_N$ を増やせる操作は $A_1, \dots, A_N$ 全体への操作のみ

という点です。ですので、まずは $A_N$ の条件を満たすために、 $A_1, \dots, A_N$ 全体への操作を何回するのが良いのかを考察してみます。

もし後先何も考えなくてよいのならば

$A_N$ 以上の整数のうち $B_N$ の倍数でもある最小の整数を $C_N$ として、 $C_N - A_N$ 回操作するのが良い

ということがわかります。さて、これは $A_N$ のことのみを考えた都合でしたが、数列全体のことを考えた時はどうでしょう？？？

一般には「今考えている要素にとって一番良い選択であっても、その後にとって良いとは限らない」という状況がほとんどです。代表例としてナップサック問題などがあります。しかし今回は

操作した後の $A_N$ が小さい方が、後の $A_{1}, \dots, A_{N-1}$ にとっても助かる

という状況になっています。理由は

$A_N = a$ まで操作したあとの $A_{1}, \dots, A_{N-1}$ に対してできる操作は
$a$ より小さな $b$ に対して $A_N = b$ まで操作したあとの $A_{1}, \dots, A_{N-1}$ に対しても実行できる

からです。つまり、 $A_N$ への操作回数が小さい方が、後先にとってもよい！！！！！自分にとっても、後続にとっても良い、となったらもう迷うことはないです。この種の考察が Greedy の構造になっているケースが多いように思います。

詰め

ここまでは $A_N$ について考えましたが残りも同様です

$A_N + C_N$ が $B_N$ の倍数になる最小の $C_N$ をとる
$A_{N-1} + C_{N-1}$ が $B_{N-1}$ の倍数で、なおかつ $C_{N-1} \ge C_{N}$ となるような最小の $C_{N-1}$ をとる
$A_{N-2} + C_{N-2}$ が $B_{N-2}$ の倍数で、なおかつ $C_{N-2} \ge C_{N-1}$ となるような最小の $C_{N-2}$ をとる
...

という繰り返しをします。

#include <iostream>
#include <vector>
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] >> B[i];

  vector<long long> C(N+1, 0); // C[N] = 0 を番兵としておく
  for (int i = N-1; i >= 0; --i) {
      A[i] += C[i+1]; // とりあえず前回分を足しておく
      long long amari = A[i] % B[i];
      long long need = 0;
      if (amari != 0) need = B[i] - amari; // 追加で必要な分
      C[i] = C[i+1] + need;
  }
  cout << C[0] << endl;
}

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

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

AtCoder AGC 009 A - Multiple Array (3Q, 茶色, 300 点)

問題概要

制約

考えたこと

Greedy

詰め