Distribution [AtCoder Beginner Contest 214 C]

https://atcoder.jp/contests/abc214/tasks/abc214_c

解説

https://atcoder.jp/contests/abc214/submissions/25034924

今回の問題は少し制約を緩めたものから考えるのがよい。
円周上というのをやめて一直線上で動けるということを考えることにすると、
解法を思いつく人も結構いるかもしれない。

円周をやめる

すると、DPで解けそうな感じがしてくる。
（DPでなくてもいいのだが、DPのコンテキストに乗せると理解が早いと思ってそうした）

dp[i] := i番目に宝石が来る最短時間

1番目のすぬけ君は宝石を直接もらうしかないので、dp[0] = T[0]
それ以降は前のすぬけ君からもらうこともできるので、dp[i] = min(T[i], dp[i - 1] + S[i - 1])となる。
ここが理解できているとかなり解法に近づけている。

円周を入れる

例えば 1 2 3 4 5とすぬけ君がいて、4->5->1->2と宝石が動いて2番目のすぬけ君が最適に受け取るという
ルートもあり得る。なので、問題にもあるように円周を戻してどうなるか考えてみる。
DP構造もループさせてみよう。
つまり、dp[0] = min(T[0], dp[N - 1] + S[N - 1])で更新ができるということである。
仮にこれでdp[0]がより良い結果となった場合、それがdp[1]にも影響する可能性がある。
なので、1度DPを行った場合に2周目を行う必要がある。

しかし、3周目以降は行う必要が無く2週目までで問題ない。
これは1周を超えて宝石を渡すのは自明で無駄な行為であるからである。

DPは必要か？

DPの方が分かりやすい場合はこれで答えてもいいし、DPの更新を見てみると1つ前の要素しか見ていないので、
1つ前の要素、より直接的な表現をすると、これまでの最適解を保持しながら2周分更新処理をやっていけば
答えが求まる。自分の実装はそうなっている。

int N, S[201010], T[201010];
int ans[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, N) cin >> T[i];

    int mi = inf;
    rep(i, 0, N) {
        chmin(mi, T[i]);
        ans[i] = mi;
        mi += S[i];
    }
    rep(i, 0, N) {
        chmin(mi, T[i]);
        chmin(ans[i], mi);
        mi += S[i];
    }

    rep(i, 0, N) printf("%d\n", ans[i]);
}