読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

UnKoder #03 Frog Jumping

UnKoder #03に参加。2完です。うーん。最近あんまり調子よくないですね。

問題:Programming Problems and Competitions :: HackerRank

解法:左側からのaの累乗の和\sum_{j < i} a^{|x_j−x_i|}と右側からのaの累乗の和\sum_{j > i} a^{|x_j−x_i|}が都会度の値となる。このように左側からの和と右側からの累乗の和を分けて計算すると,簡単に計算をすることができる。
以下ソースコード

int dist[100100];
double ans[100100];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    double a;
    cin >> N >> a;
    for (int i = 0; i < N; i++) cin >> dist[i];
    double sum = 0;
    for (int i = 0; i < N; i++) ans[i] = 0;
    for (int i = 0; i < N; i++) {
        ans[i] += sum;
        double d = pow(a, dist[i+1]-dist[i]);
        sum = d*sum+d;
    }
    sum = 0;
    for (int i = N-1; i >= 0; i--) {
        ans[i] += sum;
        double d = pow(a, dist[i]-dist[max(i-1, 0)]);
        sum = d*sum+d;
    }
    for (int i = 0; i < N; i++) {
        printf("%.15lf\n", ans[i]);
    }
    return 0;
}