ABC216 D - Pair of Balls
https://atcoder.jp/contests/abc216/tasks/abc216_d
コンテスト中はシミュレーションすることで解答を求めたのですが、 トポロジカルソートで解けるというツイートも見たので考察しました。
解説
ある筒の中に上から { x, y, z } とボールが入っていたとします。 このとき、(各色のボールは2つしかないため)zを取り出すためにはyを取り出す必要があり、yを取り出すためにはxを取り出す必要があります。 したがって、x -> y -> zという依存関係があることになります。 これを全ての筒について見ていくと、依存関係のグラフを構築することができます。
全てのボールが取り出せるかどうかは、この依存関係のグラフがトポロジカルソート可能であるかと同値になります。 したがって、入力からグラフを構築し、トポロジカルソートを試してみることで解答がわかります。
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についてこの満足度を足していけば答えになります。
コンテスト中に提出した解答はこちらです。
ARC125 B - Squares
https://atcoder.jp/contests/arc125/tasks/arc125_b
自分の解法メモです。
問題
整数 が与えられる. 以下の条件を満たす整数の組 の個数を998244353で割った余りを求めよ.
- は平方数(0も平方数とする)
制約
考察
以下、は制約を満たすものとします。
を固定したとき、これを満たす整数の個数は からまでの個。
はを満たす必要があるので、が動く範囲は。
コード概要
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;