ABC133 D - Rain Flows into Dams
問題原文
問題要旨
円形に 個の山が、並んでいて、各山の間にはダムが1つずつある。
ある山に リットルの雨が降ると、その両隣のダムに リットルずつ雨が流れ込む。
ある日、各山に正の偶数リットル雨が降ったあとのダムに貯まった雨量が与えられるので、各山に何リットルの雨が降ったかを復元せよ。
この問題の制約下では解が一意に定まることが保証される。
- は奇数。
解法
ある1つの山について、正しい雨量をおくことができれば、あとは芋づる式に答えが求められる。
ある1つの山の雨量を特定する方法はいくつかある。
山1のに降った雨量を0と仮定する
山1に降った雨量を0とすると、芋づる式に山2 ~ 山N の雨量を仮定できる。 (そして、当然山1と山Nの間のダム以外は必ず雨量との整合性が取れている状態になる。)
山1と山Nの間のダムについて整合性が取れていなかった場合、その原因は山1に雨量0を仮定したことにある。実験すると、ズレ1につき山1の雨量を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=' ')
感想
円は苦手だ。。。(静的寿司とかね)
こういう立式がばばばとできるようになりたいですね。