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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #353 (Div. 2) E. Trains and Statistic

Codeforces セグメント木

http://codeforces.com/contest/675/problem/E

問題

n 個の駅があり、i 番目の駅からは i+1..a[i] の駅に移動可能である。

ρ(i,j) を駅 i から駅 j への最短ステップ数とする。すべての i<j に対する ρ(i,j) の総和を求めよ。

解法

  • dp[i] := ρ(i,i+1)+ ... +ρ(i,n-1)

とする。dp[i+1]..dp[n-1] が求まっていれば、ここから dp[i] を計算できる。

i→i+1..a[i] は 1 ステップで到達できる。

$$ dp[i] += a[i] - (i+1) + 1 $$

a[i]+1 以降に行くには、i+1..a[i] のうち最も右に飛べる駅を経由するのが最適であるはず。最大の駅を M とすると、

$$ dp[i] += dp[M] + (n-1) - (M+1) + 1$$

M+1..a[i] を余分にカウントしてしまったため、引いておく。

$$ dp[i] -= 2(a[i] - (M+1) + 1) $$

Codeforces Round #353 (Div. 2) E. Trains and Stati ...

データ構造で DP 加速かなと思ったのが運の尽き。