ichinoseac’s diary

一ノ瀬朱紅の競プロ日記です🌟

ABC216 D - Pair of Balls

https://atcoder.jp/contests/abc216/tasks/abc216_d

コンテスト中はシミュレーションすることで解答を求めたのですが、 トポロジカルソートで解けるというツイートも見たので考察しました。

解説

ある筒の中に上から { x, y, z } とボールが入っていたとします。 このとき、(各色のボールは2つしかないため)zを取り出すためにはyを取り出す必要があり、yを取り出すためにはxを取り出す必要があります。 したがって、x -> y -> zという依存関係があることになります。 これを全ての筒について見ていくと、依存関係のグラフを構築することができます。

全てのボールが取り出せるかどうかは、この依存関係のグラフがトポロジカルソート可能であるかと同値になります。 したがって、入力からグラフを構築し、トポロジカルソートを試してみることで解答がわかります。

解答例:Submission #25476247 - AtCoder Beginner Contest 216

ABC216 E - Amusement Park

https://atcoder.jp/contests/abc216/tasks/abc216_e

解説

その時点で楽しさの最も高いアトラクションに乗り続ければよいのは明らかです。 以下、Aは大きい順にソートされているとします。

最初に乗るアトラクションはA[0]ですが、A[0]にいつまで乗り続けられるかというと、 A[0]とA[1]が等しくなるまで、すなわちA[0]-A[1]回です。

A[0]とA[1]が等しくなると、今度はこれらの値がA[2]に等しくなるまで 2つのアトラクションに乗り続けることになります。 アトラクションに乗る回数は (A[1]-A[2]) * 2 回です。

同様に、i=0, 1, 2, ... として 初期値A[i]のアトラクションの楽しさがA[i+1]になるまでA[i]-A[i+1]回乗る×(i+1)台として、 この回数の合計がKに達するまでアトラクションに乗ることを考えればよいです。 (回数がKに達する前に全てのアトラクションの楽しさが0になったらその時点で終了します。Aの末尾に番兵として0を加えると楽)

あるアトラクションの楽しさがxからyに変化したとき、この間に獲得した満足度はx+(x-1)+...+(y+1)ですので、 上記のそれぞれのiについてこの満足度を足していけば答えになります。

コンテスト中に提出した解答はこちらです。

https://atcoder.jp/contests/abc216/submissions/25443359

ARC125 B - Squares

https://atcoder.jp/contests/arc125/tasks/arc125_b

自分の解法メモです。

問題

整数  N が与えられる. 以下の条件を満たす整数の組  (x, y) の個数を998244353で割った余りを求めよ.

  •  x^ 2 - y は平方数(0も平方数とする)

制約

  •  1 \leq x, y \leq N
  •  1 \leq N \leq 10^ {12}

考察

以下、 x, y, N は制約を満たすものとします。


∃x,y [ x^ 2 - yが平方数 ] \\
⇔∃x,y,k [ 0 < k \leq x かつ x^ 2 - y = (x-k)^ 2 ] (以下 k は整数) \\
⇔∃x,y,k [ 0 < k \leq x かつ x^ 2 - (x-k)^ 2 = y ] \\
⇔∃x,k [ 0 < k \leq x かつ 1 \leq x^ 2 - (x-k)^ 2 \leq N ] ( \because 1 \leq y \leq N ) \\
⇔∃x,k [ 0 < k \leq x かつ \frac{k^ 2 + 1}{2k} \leq x \leq \frac{k^ 2 + N}{2k} ] \\
⇔∃x,k [ 0 < k \leq x \leq \frac{k^ 2 + N}{2k} ] ( \because k = \frac{k^ 2 + k^ 2}{2k} \geq \frac{k^ 2 + 1}{2k} )

 k を固定したとき、これを満たす整数 x の個数は  k から \lfloor \frac{k^ 2 + N}{2k} \rfloor までの \lfloor \frac{k^ 2 + N}{2k} \rfloor - k + 1 個。

 k  k \leq \frac{k^ 2 + N}{2k} を満たす必要があるので、 k が動く範囲は k=1, \ldots , \lfloor \sqrt{N} \rfloor

コード概要

long long total = 0;
for(long long k = 1; k * k <= N; ++k) {
  total += (k * k + N) / (2 * k) - k + 1;
  total %= MOD;
} 
cout << total << endl;

https://atcoder.jp/contests/arc125/submissions/25288020