ABC 397
Table of Contents
https://atcoder.jp/contests/abc397
A. Thermometer
https://atcoder.jp/contests/abc397/tasks/abc397_a
B. Ticket Gate Log
https://atcoder.jp/contests/abc397/tasks/abc397_b
C. Variety Split Easy
https://atcoder.jp/contests/abc397/tasks/abc397_c
D. Cubes
https://atcoder.jp/contests/abc397/tasks/abc397_d
解説 AC
$d = x-y$ とすると
\begin{align*} x^3 - y^3 &= (d+y)^3 - y^3 \\ &= d^3 + 3d^2y + 3dy^2 + y^3 - y^3 \\ &= d^3 + 3d^2y + 3dy^2 \\ &= N \end{align*}
となる。ここで $3d^2y + 3dy^2 > 0$ だから $d^3 < N$ である。
さらに
\begin{align*} &x^3 - y^3 = N \\ &(x-y)(x^2 + xy + y^2) = N \\ &d((d+y)^2 + (d+y)y + y^2) = N \\ &(d^2 + 2dy + y^2) + (dy + y^2) + y^2 = N/d \\ &3y^2 + 3dy + d^2 - N/d = 0 \end{align*}
\begin{align*} y = \frac{-3d + \sqrt{9d^2 - 4(3)(d^2 - N/d)}}{2 \times 3} ~~~ (\because y > 0) \end{align*}
より、$d$ について全探索し、条件を満たす正整数 $y$ を求めれば良い。
ここで $y$ は二分探索で探すことができる。
\begin{align*} 3y^2 + 3dy + d^2 - N/d &= 3 \left( y^2 + dy + \frac{d^3 - N}{3d} \right) \\ &= 3 \left\{ \left( y + \frac{d}{2} \right)^2 - \frac{d^2}{4} + \frac{d^3 - N}{3d}\right\} \end{align*}
より、この2次関数は $y = -d/2$ で最小値を取る。よって、$y>0$ においてこの関数は単調増加し、解となる $y$ の値で符号がマイナスからプラスに変わる。
ll sol(ll a, ll b, ll c) {
ll wa = -1, ac = INF;
while (abs(ac - wa) > 1) {
ll wj = (wa + ac) / 2;
if (a * wj * wj + b * wj + c >= 0) {
ac = wj;
} else {
wa = wj;
}
}
return ac;
}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
for (ll d = 1; d * d * d < N; d++) {
if (N % d)
continue;
ll y = sol(3, 3 * d, d * d - N / d);
if (y <= 0)
continue;
ll x = d + y;
if (x * x * x - y * y * y == N) {
cout << d + y << ' ' << y << endl;
return;
}
}
cout << -1 << endl;
}
E. Path Decomposition of a Tree
https://atcoder.jp/contests/abc397/tasks/abc397_e
F. Variety Split Hard
https://atcoder.jp/contests/abc397/tasks/abc397_f