D - Rain Flows into Dams(ABC133)

問題

atcoder.jp

感想

わからないものがあったら変数おいて解こうね

解法

サンプルケースの２がわかりやすいのでそれを用いて解説する。

5

3 8 7 5 5

山が５個のパターンですね。 まず、求める山の水量をX1,X2,...X5とし、またダムの水量もA1,A2,...A5とする。 ダムの水量を立式すると

1. 2A1=(X1+X2)
2. 2A2=(X2+X3)
3. 2A3=(X3+X4)
4. 2A4=(X4+X5)
5. 2A5=(X5+X1) となる。

X1,X2,X3について解くと、

1. X1=A1-A2+A3-A4+A5
2. X2=A1+A2-A3+A4-A5
3. X3=-A1+A2+A3-A4+A5

ここでb+aをするとX2=2A1 - X1という結果が得られる。同様にしてX3=2A2 - X2とX1が決まればすべての値の結果が得られる。 なので、実装方針としては最初にX1を求め、そこからすべての値を順に求めていけばよい。

• まとめ 変数おいて考察。あとは式を解こうね。。。焦ってはいけない。