AGC015-A 備忘録 p.31

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

A - A+...+B Problem

考察の流れ

入力例2 より
A > B は あり得えないので 0

入力例3 より
A != B なのに N=1 はあり得ないので 0

入力例4 より
A==B ならば 1 （この場合は N=1 が許される）

最小値と最大値は固定できるから、(B-A+1) H (N-2)　の重複組み合わせか？でもそうすると、
入力例1 のときに "4 x x 6" の "x x" が 4 4, 4 5, 4 6, 5 5, 5 6, 6 6 となるから、4 6 と 5 5 が被ってしまう

和で考えると、 8, 9, 10, 10, 11, 12 になってる
ということは「和の最大値 - 和の最小値 +1」で良さそう

とすると、
最初の A 以外全部 B だった場合 ＝ A+(N-1)*B ＝ 和の最大値 から、
最初の B 以外全部 A だった場合 ＝ B+(N-1)*A ＝ 和の最小値 を引いて
+1 か？

#include <stdio.h>
typedef long long ll;
int main(){
   ll n,a,b;
   scanf("%lld%lld%lld",&n,&a,&b);
   if     ( a >  b ){ printf("0\n"); return 0; }
   else if( a == b ){ printf("1\n"); return 0; }
   else if( n == 1 ){ printf("0\n"); return 0; } 
   printf("%lld\n", a + (n-1)*b - ((n-1)*a + b) + 1 );
   return 0;
}

まとめ

・かなり迂回しながら時間をかけて考え込んでしまった
・解説みたらもっとスマートな式になっていた、反省

引き続き、のんびり精進します。

#備忘録 #AtCoder #AGC #競技プログラミング #競プロ #C言語