Codeforces #239 Div1 B. Long Path

本番何となくで書いたコードを出したらHackされてしまった。
http://codeforces.com/contest/407/problem/B

問題

1～(N+1)番の点がある。
各点iからは2つの有向辺が出ており、1つは(i+1)、1つはP[i](<=i)番の点への辺である。

初期位置1番から初めて、プレイヤーはグラフ上を以下のように動く。

• その点を訪れるのが奇数回目ならP[i]に移動
• その点を訪れるのが偶数数回目なら(i+1)に移動

N,P[i]が与えられているとき、(N+1)番に到達するまでの移動回数を求めよ。

解法

i番目に到達するのが奇数回目で、そこから(i+1)番に移動するまでの移動回数をDP[i]で求めていく。
最初i番目からP[i]に移動し、そこからDP[P[i]]+DP[P[i+1]]+...+DP[i-1]の回数をかけてi番に戻り、次の移動で(i+1)に移動する。

よってとなる。
N<=1000と小さいので、上の漸化式は特に部分和とか取らなくてもO(N^2)で間に合う。
そして答えはDP[i]の総和。

int N;
int P[1001];
ll mo=1000000007;
ll dp[1002];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
	}
	
	ll ret=0;
	FOR(i,N) {
		dp[i]=2;
		for(j=P[i];j<i;j++) dp[i]=(dp[i]+dp[j])%mo;
		ret+=dp[i];
	}
	cout << ret%mo << endl;
}

まとめ

落ち着いて考えれば割と簡単。