AGC015 A. A+...+B Problem

概要

AGCの過去問を解き、どういった思考で解いたのかをできるだけそのまま書いてみた

問題

atcoder.jp

問題文
すぬけ君は、整数を N 個持っています。このうち最小のものは A、最大のものは B です。
すぬけ君が持っている整数の総和としてありうる値は何通りあるでしょうか。

制約1≦N,A,B≦10^9
A,B は整数である

解法

入力例1を用いて実際に考えてみる。

4 4 6

最小値 4で最大値 6ということで間に入る数値は{4, 5, 6}(種類はB-A+1種類) 最小値と最大値が決まっていることから間の文字は2個(N-2個)

問題では整数の総和としてありうる値なので、最小値と最大値を無視し、間の値にのみ注目すればいいことが分かる

よって全組み合わせは{4-4, 4-5, 4-6, 5-5, 5-6, 6-6}の6通り この際に総和が等しくなってしまう組み合わせは{4-6 & 5-5}である

以上の事から出力は 5となる

なるほど、分からん…

10⁹ということで全探索はあきらめる

他の入力例をみるも特殊なケースしかないので、自分で考える必要がありそうだ

4 4 7

の入力の時を考えてみることにする
間に入る数値は{4, 5, 6, 7}の4種類
間の文字の個数は2個

全組み合わせは{4-4, 4-5, 4-6, 4-7, 5-5, 5-6, 5-7, 6-6, 6-7, 7-7}の10種類
この際に総和が等しくなってしまう組み合わせは{4-6 & 5-5, 5-7 & 6-6, 4-7 & 5-6}である

仮説をたててみる

仮説: 左側の数値を iとすると i+2以上の数と組み合わせてしまうと被ってしまうので i - i+1 で組み合わせを作る。

i - i+2 の組み合わせは i+1 - i+1 と等しい
i - i+3でも i+1 - i+2 と等しい

この仮説をもとに再度入力例1のケースで考えると

4 4 6

仮説をもとにした組み合わせ{4-4, 4-5, 5-5, 5-6, 6-6}の5種類となり上手くいく

4 4 7

の際も{4-4, 4-5, 5-5, 5-6, 6-6, 6-7, 7-7}の7種類で上手くいく

B-A+1種類の数値の中で最大値以外は2個組み合わせを持てるので

(B-A)*2+1

が答えになりそうだ

後はイレギュラーな A>Bまたは N=1だったりとあてはまらないケースを外してコードにすると

N,A,B = [int(i) for i in input().split()]
 
hanni = B-A+1
N -= 2
 
if A == B:
    print(1)
    exit()
 
if hanni <= 0 or N <= 0:
    print(0)
else:
    ans = (hanni-1)*2+1
    print(ans)

あっ．．． N = 4のケースしか考えていなかった．．．

N = 5のテストケースを自分で考えてみた結果

(B-A)*(N-2)+1

で良さそうなことが分かる

よって

N,A,B = [int(i) for i in input().split()]

hanni = B-A+1
N -= 2

if A == B:
    print(1)
    exit()

if hanni <= 0 or N <= 0:
    print(0)
else:
    ans = (hanni-1)*N+1
    print(ans)

というわけでAC

結果:18分と1WAで解けた

1WA がとても勿体ない形だったのでサンプルケースがしっかりと揃ってないときは自分でいったん落ち着いて吟味することが必要そう

一番短いコード

N,A,B = map(int,input().split())
print(max((B-A)*(N-2)+1,0))

なるほど．．．の一言につきる