AGC015A - A+...+B Problem

A - A+...+B Problem

提出AC
Submission #8512600 - AtCoder Grand Contest 015

int main()
{
	cout <<setprecision(10);
	ll n , a, b;
	cin >> n >> a >> b;
	ll ans = 1;
	if(n == 1){
		if(a != b){
			ans = 0 ;//要素は1個なのに、最小と最大が違うようなものは存在しない
		}
	}
	else if(n >= 2){
		if(a > b){
			ans = 0 ;
		}
		else{
			ans = (b-a)*(n-2)+1;
		}
		//最大b < 最小a となるとき、作り方は存在しないので0
	}
 
	cout << ans << endl;
}

解法
基本的に、n個の要素のうち二つはa,bに割り当てなければいけない

整数の総和が問題なので、
aが何個…b-2 が何個…bが何個…
見たいな組み合わせの問題ではない
まずは例外について
・a > b
最小がa,最大がbと言っているが、このような入力も与えられることに注意
・要素数が1 つまりnが1のとき、 a と bが一緒じゃないといけない

nが2以上のときについて
a < b が成立しているならば
まず要素二つはaとｂに固定してしまう。
残りのn-2個の要素をどうするか考えると
n-2個の要素の和を考えると
最小は全部がaのとき
最大は全部がbのときである。

n-2個の要素の和について(n-2)* a から (n-2)*bがすべて作れる。
これは、まずすべてaで和を(n-2)*a にする
それより一つ大きくしたいなら,一つだけ要素を1＋してあげればよい。

この操作で n - 2 個の要素について(n-2)* a から (n-2)*bがすべて作れる。