More than 3 years have passed since last update.

AtCoderログ：0082 - ABC 214 C

Posted at 2021-08-18

問題

問題文

$N$ 人のすぬけ君が円周上に並んでおり、反時計回りに $1,2,\cdots,N$ の番号がついています。
$i~(1 \le i \le N)$ 番目のすぬけ君は時刻 $t$ に宝石をもらうと $S_i$ 単位時間後、すなわち時刻 $t+S_i$ にその宝石を $(i+1)$ 番目のすぬけ君に渡します。ただし、$(N+1)$ 番目のすぬけ君とは $1$ 番目のすぬけ君のことを指すとします。
また、高橋君は時刻 $T_i$ に $i$ 番目のすぬけ君に宝石を渡します。
全ての $i~(1 \le i \le N)$ について、$i$ 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

・$1 \le N \le 200000$
・$1 \le S_i,T_i \le 10^9$
・入力は全て整数である。

回答

回答1 (AC)

すぬけ君がはじめてもらう宝石は(1)となりのすぬけ君から渡される場合,と(2)高橋君から渡される場合,の2通りがあります。$i$ 番目のすぬけ君が宝石をはじめてもらう時刻を $R_i$ とすると、$i$ 番目のすぬけ君が(1)の方法で宝石を渡される時刻は $R_{i-1}+S_i$、(2)の方法で宝石を渡される時刻は $T_i$ なので、$R_i={\rm min}(R_{i-1}+S_{i-1}, T_i)$ となります。あとは $i$ を小さい方から変化させていけば全ての $R_i$ が求まります。

ところが、最初のすぬけ君がはじめて宝石を渡される時刻 $R_1$ を求めるのが少し面倒です。というのも、すぬけ君たちは円周上に並んでいるため、$R_1$ を求めるには $N$ 番目のすぬけ君がはじめて宝石を渡される時刻 $R_N$ が必要になるのです。$R_N$ を求めるには $R_{N-1}$ が必要で...と考えていくと、どこから手をつけて良いかわからなくなってしまいます。

そこで、暫定的に $R_1$ の初期値を $T_1$ に設定し、この初期値で各 $R_i$ を $2$ 周計算していけば正しい値を求めることができます。というのも、そもそも $R_1=T_1$ ならば $1$ 周目で正しい値が求まるので、計算を $2$ 周させても問題ありません。また、$R_1=R_N+S_N$ となるならば、$1$ 番目のすぬけ君は $N$ 番目のすぬけ君から宝石を渡されたことになります。その宝石は $i$ 番目のすぬけ君が高橋君から受け取ったとすると、$1$ 週目の計算で $R_i,R_{i+1},...,R_N$ は正しく計算できているので、もう $1$ 周すればすべての $R_i$ を正しく計算できます。

以上の考察をまとめたコードは以下のようになりました。

abc214c-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;

  vector<int> s(n);
  for ( int i=0; i<n; i++ ) {
    cin >> s.at(i);
  }

  vector<int> t(n);
  for ( int i=0; i<n; i++ ) {
    cin >> t.at(i);
  }

  vector<int> r(n);
  r.at(0) = t.at(0);
  for ( int i=1; i<n; i++ ) {
    r.at(i) = min( r.at(i-1)+s.at(i-1), t.at(i) );
  }
  r.at(0) = min( r.at(n-1)+s.at(n-1), t.at(0) );
  for ( int i=1; i<n; i++ ) {
    r.at(i) = min( r.at(i-1)+s.at(i-1), t.at(i) );
  }
  
  for ( int i=0; i<n; i++ ) {
    cout << r.at(i) << endl;
  }
}