Multiple Array [AtCoder Grand Contest 009 A]

atcoder.jp

i 番目のボタンを押すと、数列の A(0) から A(i) までの項が全て +1 されます。ボタンを押した項だけだと勘違いしてました。

仮に長さ2の数列があり、0番目の項はボタンを100回押せばよく、1番目の項はボタンを10回押せばよいとします。このとき、どちらの項を先に操作するべきでしょうか。

0番目の項を先に操作すると、操作回数は合計110+@回になります。0番目のボタンを100回押したあと、1番目のボタンを10回押すことになりますが、この過程で0番目の項は +110 されます。本来であれば0番目の項は +100 でよかったはずなのに、1番目のボタンを後に押す関係で +110 されてしまい、さらに、B(0) の倍数でなくなってしまう可能性もあります。

ようするに、数列の先頭から操作していく場合、 i 番目の項を最小操作回数で B(i) の倍数にしたとしても、i 番目以降の項を操作する際に i 番目の項も変化してしまうので、数列の先頭から操作回数を求めていくことは不可能ということになります。

よって解説にもあるように、この問題は一番最後の項から最初の項へと操作していくのが最適です。

変数 ans を「i 番目の項を操作し終わった時点での操作回数」とし、これを一番最後から順に求めていきます。そして、肝心の「A を B の倍数にするための必要操作回数」ですが、これは、

・A+ans が B で割り切れるとき　→　0
・上記以外のとき　→　B - (A+ans)%B

となります。A=4, B=9 の場合だと、

・oooo/oooo/oxxx/xxxx/xxxx........

のようなイメージです。3番目の区間の "o" が 9%4=1 に相当します。区間の長さが4なので、そこから余りの個数を引いてあげればいいわけですね。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		int[] A = new int[n], B = new int[n];
		for (int i=0; i<n; i++) {
			A[i] = sc.nextInt();
			B[i] = sc.nextInt();
		}
		
		long ans = 0;
		for (int i=n-1; i>=0; i--) {
			long temp = (A[i] + ans) % B[i];
			ans += temp==0? 0 : B[i] - temp;
		}
		
		System.out.println(ans);
		
	}
}