の値が非常に大きくなることがあるため、愚直にシミュレートすると TLE になってしまう可能性があります。
そこで、一度は止まったことのあるマスに止まったら、その後は同じ動きをするという今回の問題におけるすごろくの性質を利用しましょう。
マスの個数は 個であるため、 回以内の行動で必ず一度は止まったことのあるマスに止まります。
よって、一度は止まったことのあるマスに再び止まるまでは愚直にシミュレートし、その後は周期ごとにどれだけすごろくのカウントを増やせるかを計算することにより、この問題を で解くことができます。
実装例(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n, k; cin >> n >> k;
vector<long long> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
vector<long long> check(n + 1, -1), checkcnt(n + 1);
long long actcnt = 0, cnt = 0, now = 0;
while(check[now] == -1){
check[now] = actcnt;
checkcnt[now] = cnt;
actcnt++;
now += a[now];
cnt += now / n;
now %= n;
if(cnt >= k){
cout << actcnt << endl;
return 0;
}
}
long long len = actcnt - check[now], r = cnt - checkcnt[now];
long long ans = actcnt + len * ((k - cnt - 1) / r);
cnt += ((k - cnt - 1) / r) * r;
while(cnt < k){
ans++;
now += a[now];
cnt += now / n;
now %= n;
}
cout << ans << endl;
}