まず、\(\mathrm{memo}_1=T_1, \mathrm{memo}_{i+1}=\mathrm{memo}_i+S_i\) という漸化式で定められる \(\mathrm{memo}_i\) が、高橋君が \(1\) 番目のすぬけ君に直接渡した宝石が \(i\) 番目のすぬけ君に初めて届く時刻です。

\(2,3, \ldots ,N\) 番目のすぬけ君に直接渡した宝石が \(i\) 番目のすぬけ君にいつ届くかについても同じように考えます。

これを愚直に実装することで \(O(N^2)\) で解けますが、実行時間に間に合わないため高速化を考えます。

ここですぬけ君が受け取る宝石の中で \(2\) 番目以降の宝石は無視できることに注目して今までの \(N\) 個の計算を一つにまとめると、以下のようなコードになります。

少なくとも \(2N\) 回ループを回さないといけないことに注意してください。

実装例 (Python)

N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
for i in range(N*2):
    T[(i+1)%N] = min(T[(i+1)%N], T[i%N] + S[i%N])
for ans in T:
  print(ans)

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N; cin >> N;
    vector<int> S(N), T(N);
    for(int i = 0; i < N; i++) cin >> S[i];
    for(int i = 0; i < N; i++) cin >> T[i];
    vector<int> memo = T;
    for(int i = 0; i < N*2; i++) memo[(i+1)%N] = min(memo[(i+1)%N], memo[i%N] + S[i%N]);
    for(int ans: memo) cout << ans << endl;
}