🎉

Atcoder369 A - 369を理解し忘れないようにする

2024/09/07に公開

A

https://atcoder.jp/contests/abc369/tasks/abc369_a

問題概要

A,Bは入力で与えられている。1<=A,B<=100
以下の条件を満たす整数xが何通りあるか求める。

  • A,B,xを並び替えたあとに等差数列になるとき

ポイント

等差数列になるケースを求めるのではなく、等差数列になるxの値が何個あるかを求める。

  • x,A,Bとx,B,Aでどちらも等差数列が成り立っていてもそれは1通りとしてカウントする。

解き方

xを-100~100まで探索して、並び替えた後の以下の6通りでq-p == r-qになることを調べた。

  • a,b,x
  • a,x,b
  • b,a,x
  • b,x,a
  • x,a,b
  • x,b,a

https://atcoder.jp/contests/abc369/submissions/57294971

※ a,b,x(1,2,3)を入れ替えたもの(x,b,a(3,2,1))は試す必要はない。よって、以下の3通りで良い。

  • x,a,b
  • a,x,b
  • a,b,x

別解を見つける

xを全探索しないやり方を探したい。

解説見た

  • A == Bの場合、等差数列が成立するのはxがA,Bと同じ値の時なので答えは1通り
  • A != Bの場合、x,a,bとa,b,xのようなxが端にあるケースなら等差数列にできるので2通りは確定。
    • 少しわかりづらいのでシミュレーションする
      • x,a,bの場合、A == 3,B == 25ならxは-21になると等差数列が成り立つ
      • a,b,xの場合、A == 3,B == 25ならxは47になると等差数列が成り立つ
    • A != Bでかつa,x,bの場合、a+b/2が整数なら等差数列が成り立つ
      • A == 2,B==4なら2+4/2 = 3で等差数列が成り立つ
      • A == 2,B==3ならxは2.5になり小数になるので、3つが整数であるという条件に合致しない
      • A == 2,B==8ならxは5で等差数列が成り立つ

まとめると

  • A == Bなら答えは1
  • A != BかつA+B/2が整数なら答えは3
  • A != BかつA+B/2が小数なら答えは2

B

https://atcoder.jp/contests/abc369/submissions/57304904
大方、解説と同じ解き方をしていたので解説コードのみ

Discussion