Official
A - 本棚の整理 / Organizing the Bookshelf Editorial
by
A - 本棚の整理 / Organizing the Bookshelf Editorial
by
physics0523
初心者の方へ
- AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは practice contest の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。
- また、プログラミングコンテストの問題に慣れていない方は、AtCoder Beginners Selection の問題をいくつか解いてみることをおすすめします。
- C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
- Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
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:
