この問題を解きました。ネタバレを含みます。
あとこれは全く関係のない情報なんですが、ずっと乾燥機付きの洗濯機が欲しいと思っていてとうとう思い切って30万円もする洗濯機を買いました。
支払いのとき身体がガクガク震えて喉はカラカラでした。すぐ壊れたりしませんように...
だめだった解法
山iに雨が降った量を xi とすると、x1/2 + x2/2 = A1 つまり x1 + x2 = A1 * 2 という形になります。
ここからさらに掃き出し法で単位行列を作ると(紙の上では)解がでましたが、
計算量が抑えられそうになかったので諦めて解答を見てしまいました。
未だに400点問題の自力ACはめったに出せません...
この問題を解くために気付く必要があるポイントは以下の3つだったと思います。
- 辺に重みが与えられているN頂点のグラフで、各頂点の値を求める問題だと考える
- 各頂点の値は雨が降った量そのままではなく、降雨量/2と考える
- どこかの頂点を固定して考える（とすべての頂点の値を求めるための式が作れる）
重要なのは2と3ですね。
入力例１ を例に考えます
3 2 2 4
まずはx1がわかっているものだと仮定して他の頂点を求めるための式を作ります。
A2はx1とx2の和で2です。
x2 = 2 - x1
つぎに、A3はx2とx3の和で2です。
x3 = 2 - x2
つまり以下のようになります。
x3 = 2 - 2 + x1
A3はx3とx1の和で4です。
X1 = 4 - x3
つまり
x1 = 4 - 2 + 2 - x1
整理すると
2*x1 = 4 - 2 + 2 = 4
これでx1の値がわかったので、残りの頂点について式のx1に2を代入するとO(N)で答えが出ます。
提出したコード
