問題
https://atcoder.jp/contests/abc147/tasks/abc147_f
考察
普通に全探索すると、列挙だけで\(O(2 ^ N)\)かかるので間に合わない。ここで高橋君の取る要素の数を\(k\)とおくと、\(S - T\)は以下の式で表せる。
$$kX + tD - ((N - k)X + aD)$$
\(t\)は高橋君の選んだ要素の\(D\)の係数を、\(a\)は青木君の選んだ要素の\(D\)の係数を表す。整数列は\(X, X + D, ..., X + (N - 1)D\)であるため、\(D\)の係数は\(\frac{1}{2}N(N - 1)\)になる。よって\(t + a = \frac{1}{2}N(N - 1)\)を満たす。この式を上の式に代入して式変形すると以下の式を得る。
$$2(Xk + Dt) - NX + \frac{D}{2} N(N-1)$$
\(- NX + \frac{D}{2} N(N-1)\)は高橋君の選び方に依らず一定であるため省いても構わない。\(2\)倍する部分も同様に省くと、次の式が得られる。
$$Xk + Dt$$
つまり、\(0 \le k \le N\)を満たすすべての\(k\)について\(Xk + Dt\)の値を列挙し、重複を省いたあとの要素の個数が答えとなる。
\(t\)の取り得る値の範囲を考える。最小値\(l\)は、等差数列の前から\(k\)個取ってきたときの\(D\)の係数の和、最大値\(r\)は、等差数列の後ろから\(k\)個取ってきたときの\(D\)の係数の和である。そして、\(l \le t \le r\)さえ満たせば、\(t\)はどのような整数にもなり得ることがわかる。たとえば\(6(1,2,3)\) → \(7(1,2,4)\) → \(8(1,3,4)\) → \(9(2,3,4)\) → \(...\)のように進めていくと、\(6 \le t \le r\)の範囲の整数を網羅できることがわかる。
ここまでの考察により、重複しない数直線上の点を数える問題へと言い換えられた。
青の点2つと赤の点2つは重複している。このように重複した点が現れる可能性があるのは、\(Xk\)を\(D\)で割った余りが一致する\(k\)である（図では\(X \equiv 3X\ (\mathrm{mod}\ D)\)）。
よって、\(Xk\ \mathrm{mod}\ D\)で\(k\)をグループ分けして、各グループについて区間内の重複を除いた点の個数を数えればいい。この数え上げは、イベントソートを使うことで\(O(N \log{N})\)で行えるため、全体で\(O(N \log{N})\)でこの問題が解けた。
実装
https://atcoder.jp/contests/abc147/submissions/9889610
感想
- \(D = 0\)のときを考慮せずにRuntime Errorが出てしまった
- \(D \lt 0\)のときは\(X\)と\(D\)の符号を逆転できるが、それに気付かずに符号そのままで実装してしまった
- 最後の「重複しない点の数え上げ」で貪欲な方法を選んでしまったため、いくつかWrong Answerが出てしまった（実は今でも、なぜこれで駄目なのかよくわかっていない。ソースコードはこちら）
- 公差\(D\)の等差数列全体を\(D\)で割ると、公差\(1\)の等差数列になる。これに気付くと実装が少し楽になるが、気付けなかった
- \(S + T = U\)とすると、\(S - T = S - (U - S) = 2S - U\)と表せる。\(U\)は変わらないため、\(S\)が何通りあるかだけ数えればいい、という事実に気付けなかった。これに気付いていれば、複雑な計算をすることなく\(Xk + Dt\)という式が得られる
まだまだ考察に穴があるので頑張って埋めていきたい。
