zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC131-B「Bite Eating」です。
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
int N=0, L=0, cnt=0, ans_sum=0;
int main(){
cin >> N >> L;
// とりあえず累積和を計算
// あとで食べたりんご分を引けばOK
rep(i, N){
ans_sum += L + cnt;
cnt ++;
}
// 味の最小値が0よりも大きい場合はそのりんごを食べる
if (L > 0) cout << ans_sum - L << endl;
// 味の最大値が0よりも小さい場合はそのりんごを食べる
else if(L + N - 1 < 0) cout << ans_sum - (L + N - 1) << endl;
// 味の範囲が0を含んでいる場合は味が0のりんごを食べる
else cout << ans_sum << endl;
}ポイント
今回おさえるべき内容
累積和を使いこなす
定番の累積和の問題ですね。今回は1つだけ要素を削除するのですが，削除というのは一般に計算が遅い操作のため，一度全部足し上げてからいらない要素を引くというアプローチを取ろうと思います。
味のレンジが0を含むか，含まないかによって場合分けをして，0を含む場合は0を，そうでない場合は味の絶対値が小さいりんごを食べるようにすればOKです。味のレンジが0を含まない場合は，最小値が0よりも小さい場合と最大値が0よりも大きい場合に分けることで，効率よく出力を行うことができます。
コメント