Official

B - 郵便配達と手紙の重み / Mail Delivery and Letter Weights Editorial by physics0523 Editorial for printing


「手紙の通数だけ疲労度が増加する」を「手紙のある地点の番号を \(1\) 増やすのに疲労度が \(1\) かかる」と捉えます。
すると、地点 \(i\) に届ける手紙に疲労度を最低でも \(i-1\) 費やす必要があることから、 \(1 \times B_2 + 2 \times B_3 + \dots \) の疲労度が必要であることが分かります。
また、例えば手紙を一通ずつ運ぶことで子の疲労度を実際に達成できます。

よって、答えは \(\displaystyle \sum_{i=2}^{N} (i-1) \times B_i\) であり、これは時間計算量 \(O(N)\) で求値できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N;
  cin >> N;
  ll res=0;
  for(ll i=1;i<N;i++){
    ll B;
    cin >> B;
    res+=B*i;
  }
  cout << res << "\n";
  return 0;
}

posted:
last update: