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

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

AtCoder AGC 009 A - Multiple Array (300 点)

教育的 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;
}