AGC 009に参加した

やってみたけどまあ盛大に爆死したよね。

知ってた。Grand Contestだし。

A しか解けてないのでそこまでのメモしか書けない。

A - Multiple Array

まずこのA問題を見て「あれ…A…あれ…？」ってなった。 AGCだからか、Aが普段のABCでのC相当ぐらいの難易度になってるようで。

問題文

N 項からなる数列 A1,…,AN があり、N 個のボタンがあります。 i(1≦i≦N) 個目のボタンを押すと、数列 A の 1 項目から i 項目までの値が 1 ずつ増加します。

数列 B1,…,BN が与えられます。高橋君は、これらのボタンを何回か押して、すべての i に対し、Ai が Bi の倍数になるようにします。

高橋君がボタンを押す回数の最小値を求めてください。

制約

入力はすべて整数である。

• 1≦N≦10⁵
• 0≦Ai≦10⁹(1≦i≦N)
• 1≦Bi≦10⁹(1≦i≦N)

という感じ。

とりあえず素直に挙動をシミュレートする感じのプログラムを書いてみたものの、TLEで弾かれる。

何度試してもTLEから抜け出せず、さてどうしたものか…と悩んでいた。

なにがいけなかったか

素直に問題をシミュレートすると、i番目のボタンを押すたびにAi以下の数が+1される。 さすがにボタンを1回1回押すところまではシミュレートしないにしても、 要素1つ1つに何らかの数値を加算する操作を相当数やる羽目になるので、そりゃ遅くなるよね、という。

対処

よく考えたら数列のすべての値に加算操作を行う必要なんて全くなかった。 今現在操作してる位置の数字とそれまでにボタンの押された回数だけ見ていればよかったのだ。

n = gets.chomp.to_i
a, b = [], []
c = 0
 
n.times do
  input = gets.chomp.split.map(&:to_f)
  a.unshift input[0]
  b.unshift input[1]
end
 
n.times do |i|
  a[i] += c
  next if b[i] == 1 || a[i] % b[i] == 0
  t = b[i] * (a[i] / b[i]).ceil
  diff = t - a[i]
  c += diff.to_i
end
 
puts c

最初は Rational を使おうとしてたけど Float に変えてみたり、 Bi が1の時をスキップしたり、Ai % Bi が0ならスキップさせてみたり、 それ根本的に何も対処できてなくねみたいなそんなことばっかりやってた感。

B 以降の問題は？

全く解ける気がしなかったのでもう手を付けることすらしなかった。 （Bはちょっとやろうとしたけどやっぱり何言ってるか分からなかった）

解説を見たらもうBからDPがー、ってなっていたので、ですよねそりゃ今の私には無理っす、という感じ。

いい加減DPを知るべきなのだろうか。Aで手古摺ってるぐらいだしまだ早い気もする。