Official

A - 本棚の整理 / Organizing the Bookshelf Editorial by physics0523


初心者の方へ


TL;DR: 本をどのような順に並べても、ブックエンドの左端から右端の本の右端までの長さは \(S+D_1+D_2+\dots+D_N+NK\) です。

  • ブックエンドの左端からブックエンドの右端までの長さは \(S\) です。
  • ブックエンドの右端から \(1\) 冊目の本の左端までの長さは \(K\) です。 (長さをこれより大きくするのは過剰です)
  • \(1\) 冊目の本の厚みだけ長さが伸びます。
  • \(1\) 冊目の本の右端から \(2\) 冊目の本の左端までの長さは \(K\) です。(長さをこれより大きくするのは過剰です)
  • \(2\) 冊目の本の厚みだけ長さが伸びます。
  • \(2\) 冊目の本の右端から \(3\) 冊目の本の左端までの長さは \(K\) です。(長さをこれより大きくするのは過剰です)
  • \(\dots\)

これを全ての本について繰り返すと、ブックエンドの幅および各本の厚みが \(1\) 回ずつ寄与し、間隔を \(K\) 空けるという行為を \(N\) 回行うことになります。
その結果、 (空ける間隔を \(K\) で固定した場合) ブックエンドの左端から右端の本の右端までの長さは本を並べる順番によらず \(S+D_1+D_2+\dots+D_N+NK\) です。

求める値の計算は、各 \(D_i\) の値を受け取るための for ループと四則演算等を組み合わせることで実現可能です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

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

posted:
last update: