けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 015 A - A+...+B Problem (茶色, 200 点)

確かに 200 点かもしれないけど、AGC-A は時々こういう注意力系が出るね。

問題へのリンク

問題概要

 N 個の整数であって、最小が  A、最大が  B であるようなものについて、その総和として考えられる値が何通りあるかを求めよ。

制約

  •  1 \le N, A, B \le 10^{9}

考えたこと

この手の問題で重要なこととして、とりうる値は  x 以上  y 以下の整数という具合に、区間になっていることがあげられる。つまり、 6 が作れて  8 も作れるなら  7 も作れるのだ。

こういう風に、取りうる値が区間になることを見越した考察は、より高難易度な問題であっても、すごくたくさん出てくる。で今回は  A \le B とは言っていないことに注意。

  •  A \gt B のとき解なしなので 0
  •  A \le B のとき、最小が  (N-1)A + B で最大が  A + (N-1)B なので答えは、 (A + (N-1)B) - ((N-1)A + B) + 1 = (N-2)(B - A) + 1 になる...のだが、 N = 1 の場合に注意!!!!!!!
  •  N = 1 のときは例外処理を行う。 A = B なら 1 で、それ以外だと 0
#include <iostream>
using namespace std;

int main() {
    long long N, A, B; cin >> N >> A >> B;
    if (A > B) cout << 0 << endl;
    else if (N == 1) cout << (A == B ? 1 : 0) << endl;
    else cout << (N-2) * (B-A) + 1 << endl;
}