roiti46's blog

主に競プロ問題の解説を載せてます

Codeforces #298 Div.2 B: Covered Path

さくっと解けたので満足。

問題はこちら

問題

あなたはt秒間車を走らせることができる。車は1秒目には速度v1、t秒目には速度v2でなければならない(ともに正の整数)。車の速度を毎秒ごとに絶対値で最大dだけ変化させることができる。この条件のもとt秒間で進める距離の最大値を答えよ。

解法

貪欲的に解ける。各秒ごとの速度を持つことにして、まずt秒目まで車をひたすら加速させる。そのあとt秒目から逆向きに見ていき、最終速度におさまるように速度を抑えていけばいい。答えは速度の総和となる。

v1, v2 = map(int, raw_input().split())
t, d = map(int, raw_input().split())
speed = [0]*t
speed[0] = v1
for i in xrange(1,t-1):
    speed[i] = speed[i-1] + d
speed[-1] = v2

for i in xrange(t-2, 0, -1):
    speed[i] = min(speed[i+1]+d, speed[i])

print sum(speed)

まとめ

こういうとりあえず足して最後につじつまを合わせる系の問題は解けるから好きだ

広告を非表示にする