AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC133 D - Rain Flows into Dams

問題原文

atcoder.jp

問題要旨

円形に  N 個の山が、並んでいて、各山の間にはダムが1つずつある。
ある山に  2x リットルの雨が降ると、その両隣のダムに  x リットルずつ雨が流れ込む。 ある日、各山に正の偶数リットル雨が降ったあとのダムに貯まった雨量が与えられるので、各山に何リットルの雨が降ったかを復元せよ。
この問題の制約下では解が一意に定まることが保証される。

  •  N は奇数。
  •  3 \leq N \leq 10^{5}

解法

ある1つの山について、正しい雨量をおくことができれば、あとは芋づる式に答えが求められる。
ある1つの山の雨量を特定する方法はいくつかある。

山1のに降った雨量を0と仮定する

山1に降った雨量を0とすると、芋づる式に山2 ~ 山N の雨量を仮定できる。 (そして、当然山1と山Nの間のダム以外は必ず雨量との整合性が取れている状態になる。)
山1と山Nの間のダムについて整合性が取れていなかった場合、その原因は山1に雨量0を仮定したことにある。実験すると、ズレ1につき山1の雨量を1調整する非強いがあることがわかるので、解ける。

f:id:AT274:20200106205412p:plain
ある山を仮定してズレを測る方法

式を立てて求める

 i の雨量を  X_i とすると、明らかに  \sum_{i=1}^{N} A_i = \sum_{i=1}^{N} X_i なのはわかる。 これを  S とする。

また、  \frac{Xi}{2} + \frac{X_{i+1}}{2} = A_i より、  Xi + X_{i+1}  = 2A_i となる。
これより、  X_1 = S - (X_2 + X3 + ... + X_N) = S - 2(A_2 + A_4 + ... + A_{N - 1}) が導ける。

1つの山の雨量が求められたので、あとは芋づる式に求められる。

実装

1つ目の方法でやっています。

N = int(input())
A = list(map(int, input().split()))
 
dam_prob = 0
for i in range(N - 1):
    dam_prob = (A[i] - (dam_prob // 2)) * 2
 
 
start_dam = (A[-1] - (dam_prob // 2))
ans = [start_dam]
for i in range(N - 1):
    ans.append((A[i] - (ans[-1] // 2)) * 2)
 
print(*ans, sep=' ')

感想

円は苦手だ。。。(静的寿司とかね)
こういう立式がばばばとできるようになりたいですね。