UnKoder #03 Frog Jumping
UnKoder #03に参加。2完です。うーん。最近あんまり調子よくないですね。
問題:Programming Problems and Competitions :: HackerRank
解法:左側からのaの累乗の和と右側からのaの累乗の和が都会度の値となる。このように左側からの和と右側からの累乗の和を分けて計算すると,簡単に計算をすることができる。
以下ソースコード
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; }