7K12 blog

猫でも分かるアルゴリズム解説

ABC133 D - Rain Flows into Dams

f:id:tkr987:20200807010019p:plain

https://atcoder.jp/contests/abc133/submissions/15728517

  •  x_1+x_2=n_1, x_2+x_3=n_2, ...と続く方程式は2変数に減らせる
  • 「奇数個」の循環方程式(上記方程式が循環)は1変数に減らせるので答えが分かる

f:id:tkr987:20200807010347p:plain

山iの降水量を x_i、ダムiの水量を a_iとする。

 x_2=2a_1-x_1

 x_3=2a_2-x_2

...

 x_1 = 2a_{i-1} - 2a_{i-2} + 2a_{i-3} - ... - 2a_{2} + 2a_{1} - x_1

となるので、奇数番目の a_iを加算、偶数番目の a_iを減算することに注意して計算すると x_1が分かる。 x_1が分かれば他の x_iも順番に確定する。計算量は O(N)になる。1-indexにするかどうかは微妙なところだが、1-indexにして実装した。基本的に2倍の a_iを計算で使うので入力時点で a_iを予め2倍して処理した。

なお、Nが偶数だと一意に答えが定まらない(らしい)ので、設問でNが奇数個になっている。