B - Bite Eating
https://atcoder.jp/contests/abc131/tasks/abc131_b
配点200点 (難易度250点)
※難易度:この問題に対する主観的な難しさ、他のB問題よりも少し難しい印象。
基本的な考えとして差の絶対値が0に近いとき、それが食べるべきリンゴです。
これを数直線上で考えると3つのパターンに分けられれます。
味の配列が0より下にあるか、0より上にあるか、0をまたいでいるか?
0より下もしくは上の時は0に近いりんごを食べ、0をまたいでいる時は0のりんごを食べます。
解説のPDFを読んだ時はif文の条件がRとLで一つの条件文に2つの変数が用いられていて何だこれと思いましたが、理解して見直してみるとかなり美しいプログラムですね。きっちり考えて作られています。
解説のPDF
Lにリンゴ味の左端の値を入力します。
Rにリンゴ味の右端の値を入力します。
右端が0以下なら右端が食べるリンゴです。
左端が0以下なら左端が食べるリンゴです。
それ以外の値は左端から右端までのリンゴの列は0をまたいでいるので、0が食べるべきリンゴとなります。
林檎の味は公差1の等差数列なのであとは等差数列の公式に代入します。
初項L、末項R、項数R-L+1
(R+L)(R-L+1)/2=総和
計算量 O(1)
# include <bits/stdc++.h>
using namespace std;
int main() {
// 入力
int N, A;
cin >> N >> A;
// 処理
int L = A;
int R = A + N - 1;
int eat;
if (R <= 0)
eat = R;
else if (L >= 0)
eat = L;
else
eat = 0;
int answer = (R + L) * (R - L + 1) / 2 - eat;
// 出力
cout << answer << endl;
return 0;
}
提出時のプログラム
こちらは問題文を整理せずに文章通りにプログラムを書いていますね、
appleSum に合計値を入れる。
nは制約より2以上
Lは0以上と0未満でif文で分岐
Lが0未満の時は、さらにn+Lで0より大きいかそれ以下かで分岐させています。これは読みにくいですねぇ・・反省。
計算量 O(n)
int main() {
// 入力
int n, L;
cin >> n >> L;
int appleSum = 0;
// 処理
if (L >= 0) {
for (int i = 2; i <= n; i++) {
appleSum += L + i - 1;
}
} else if (L < 0) {
if (n + L > 0) {
for (int i = 1; i <= n; i++) {
appleSum += L + i - 1;
}
} else {
for (int i = 1; i < n; i++) {
appleSum += L + i - 1;
}
}
}
// 出力
cout << appleSum << endl;
return 0;
}
※自分のはそのまま書いている典型的なだめプログラムですね・・・
A問題もチラホラとそのまま書くよりも考える(&きれいな)プログラムの書き方が要求される問題が出題されますが、B問題はさらに問題文そのままプログラムに起こすよりも考える力を必要とする問題が出題されているようですね。
プログラムの美しさについて、
他人のプログラムを読むとわかるのですが、問題文に沿ってプログラムを書いていると、条件が複雑な時はプログラムもごちゃごちゃと複雑になっていきます。(この問題のように)問題文のコア部分を理解して整理し直してプログラムを書くと、解説のPDFのプログラムのように綺麗なプログラムになっていきます。