プログラミング

【競プロ精進日記】ABC131-B

本記事は管理人が競技プログラミングを始めたため,その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。記事目次は以下をご覧ください。

内容は管理人の推測や恣意的な感想を大いに含みます。もし間違い等ありましたらご指摘ください。あくまでも参考程度にお願い致します。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

概要

今回の問題はABC131-B「Bite Eating」です。

定番の累積和の問題ですね。今回は1つだけ要素を削除するのですが,削除というのは一般に計算が遅い操作のため,一度全部足し上げてからいらない要素を引くというアプローチを取ろうと思います。

味のレンジが0を含むか,含まないかによって場合分けをして,0を含む場合は0を,そうでない場合は味の絶対値が小さいりんごを食べるようにすればOKです。味のレンジが0を含まない場合は,最小値が0よりも小さい場合と最大値が0よりも大きい場合に分けることで,効率よく出力を行うことができます。

c++

#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;
}

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です