AtCoder Beginner Contest 133 D - Rain Flows into Dams

解説PDFが微妙に見づらかったので自分用にまとめました。

問題概要

atcoder.jp

円形に山が並びその間にたまった水の量が入力される。山に降った雨は左右のダムに均等に流れ込む。各ダムに流れこんだ水の量を参考にして各山に降った雨の量を求める。

概要図

各ダムに流れ込んだ をもとに を求める。

考察

各 についての方程式をたててn元連立方程式を解けばこの問題は解けるのですが、それでは間に合わないので上手くできないか考えます。

試しに1つ目の山に降った雨の量を とおいてみます。そして基準にした から時計回りに各値を求めていくと最終的に は以下のようになることが分かります。

X を基準に時計回りに各値を求める

図の左上にあるとおり、 自身は、基準にした から見て奇数番目の を足して、偶数番目の を引いた値になることが分かりました。（制約より、ダムの数は奇数なのでこれが成り立つ）

これで基準となるが求まったので、あとは各 について、ダム には山 と の降水量の半分ずつが均等に水が流れてくることから
より

• 

の漸化式を求めていけば̪各値が求まります。

実装

上記のことを実装すると以下のようになります。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);    //各ダムの降水量
    vector<int> ans(n);  //各山の降水量
    for(int i=0;i<n;i++){
        cin >> a[i];
        //基準のとなる山の降水量を求める
        //奇数番目は足して偶数番目は引く
        if(i%2==0) ans[0] += a[i];
        else ans[0] -= a[i];
    }
    for(int i=1;i<n;i++){
        //漸化式をもとに代入
        ans[i] = 2*a[i-1]-ans[i-1];
    }
    for(auto&& e:ans) cout << e << " ";
    cout << "\n";
    return 0;
}

終わりに

こういった数学系は、実装はそんなに難しくないけど自分はその発想に至るまでの時間が結構かかるのでもっと慣れていきたいです。