ヤマカサのプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

ABC093D Worst Case レビュー

AtCoder Java

解説を見直してみる。

もう一度この問題を考えてみました。

D: Worst Case - AtCoder Beginner Contest 093 | AtCoder

$A \leq B$ としても一般性を失いません。

$A = B$ のとき

$x_i y_i \lt A^2$ 　　　　　 ①

を満たす $x_i, y_i$ の組の最大数を考えます。ここで、 $x_i, y_i \neq A$ です。 ①を満たすためには、すくなくとも次の条件が必要です。

$1 \leq x_i \leq A - 1$ 　　　　②

または

$1 \leq y_i \leq A - 1$ 　　　　③

②のとき、 $x_1 = 1$ の場合、 $y_1$ の最大値は $A^2 - 1$ ですがこの選び方をすると機械的に組み合わせを考えることが難しいと思います。

$x_1 = 1$ のとき、 $y_1 = 2A - 1$ と選ぶと、

$A^2 - 1 * (2A - 1) = (A - 1)^2 \geq 0$

となります。

$i = 2$ 以降では、

$A^2 - 2 (2A - 2) = (A - 2)^2 \geq 0$ 　　　 ( $i = 2$ )

　　　　⁝

$A^2 - k (2A - k) = (A - k)^2 \geq 0$ 　　　 ( $i = k$ )

　　　　⁝

$A^2 - (A - 1) (2A - (A - 1))$ 　　　 ( $i = A - 1$ )

$= A^2 - (A - 1)(A + 1)) = 1 \ge 0$

のように選ぶことができます。③のときも同様にして考えると、

$A - 1 + A - 1 = 2A - 2$ が答えとなります。

$A + 1= B$ のとき

$x_i y_i \lt A(A + 1)$ 　　　　　 ①

を満たす $x_i, y_i$ の組の最大数を考えます。ここで、 $x_i \neq A, y_i = A + 1$ です。 ①を満たすためには、すくなくとも次の条件が必要です。

$1 \leq x_i \leq A - 1$ 　　　　②

または

$1 \leq y_i \leq A$ 　　　　③

②のとき、

$x_1 = A - 1$ とすると、 $y_1$ の最大値は $y_1 = A + 2$ となります。このとき、

$A(A + 1) - (A - 1)(A +2) = 2$

となります。 $x_k = k$ では、 $y_k = 2A + 1 -k$ となります。実際に計算何してみると

$A(A + 1) - k (2A + 1 - k)$

$\left ( A - \dfrac{2k - 1}{2} \right)^2 - \dfrac{1}{4}$

となります。ここで、

$f(k) = \left ( A - \dfrac{2k - 1}{2} \right)^2 - \dfrac{1}{4}$

とします。

$1 \leq A$ から $1\leq k \leq A - 1$ です。

$f(k) =\left ( k - A -\dfrac{1}{2}\right)^2 -\dfrac{1}{4}$ の最小値は $k = A - 1$ となります。

変域に制限がない場合、 $k = A + \dfrac{1}{2}$ で最小値を取ります。また、

$f(A) = 0$

から、

$f(A - 1) \gt 0$

となります。

③条件では、 $y_{1} = A$ とすると、 $x_{1} = A - 1$ となってしまうので、②の条件を満たした上で②の条件を考えると、③は

$1 \leq y_i \leq A - 1$ 　　　　③

とする必要があります。

この条件は②の条件と同様に考えればよいので答えは

$A - 1 + A - 1 = 2A - 2$

となります。

上記以外の場合

確認事項

$C^2 \lt AB$ を満たす自然数 $C$ を利用します。下の参考サイトの解説を参考にしています。

$x + y = k$ 　　( $k$ は一定)

とします。このとき、 $xy$ の最大値は、

$xy = (k - x)x$

$xy = - \left ( x - \dfrac{k}{2} \right)^2 + \dfrac{k^2}{4}$

となるので、 $x = y = \dfrac{k}{2}$ のとき $xy$ は最大となります。

したがって、二組の自然数の和が一定のとき、自然数 $m$ を用いて、

$x + y = 2m$ 　ならば　 $x = y = m$

となり、

$x + y = 2m + 1$ 　ならば　 $x = m, y = m + 1$

となります。

解説の検討

AtCoderの解説では、 $C(C+1) \geq AB$ のときの条件を考えていました。 $C(C+2) \geq AB$ の条件を考えなくてよい理由は次になります。 https://img.atcoder.jp/arc094/editorial.pdf

$C^2 \lt AB$ 　　①

①の条件のもとで、

$C(C + 2) = AB$

のとき、 $C = A, B = A + 2$ となります。このときの組み合わせは、

$1 * (2A + 2) \lt A(A + 2)$

$2(2A + 1) \lt A(A + 2)$

　　　　⁝

$(A - 1)(A + 3) \lt A(A + 2)$

$(A + 1)(A + 1) \gt A(A + 2)$

$(A + 3)(A - 1) \lt A(A + 2)$

　　　　⁝

$(2A + 1) * 1 \lt A(A + 2)$

となるので、組み合わせは $2A - 2$ となります。

$C(C + 2) \lt AB$ の検討

次に

$C(C + 2) \lt AB$

の条件を考えると、

$C(C + 2) \lt C(C + 2) + 1 = (C+1)^2 \lt AB$

となるので、

$(C + 1)^2 \lt AB$

より、 $C = C + 1$ とすべきです。等号が入らない理由は $A \lt B$ と仮定しているためです。

一般化

上記より、

$C^2 \lt AB \leq C(C+1)$ 　　②

と

$C^2 \lt C(C + 1) \lt AB$ 　　③

の条件を考えれば良いです。また、

$A \leq C \lt B$ 　　または　 $A \lt C \leq B$

となることに注意します。

$C^2 \lt AB \leq C(C+1)$ 　　②

②のとき、組み合わせは

$1 * (A + B - 1) \lt AB$

$2(A + B - 2) \lt AB$

　　　　⁝

$(A - 1)(B + 1) \lt AB$

$(A + 1)(2C - A - 1) \lt AB$

$(A + 2)(2C - A - 2) \lt AB$

　　　　⁝

$C * C \lt AB$

$(C + 1)(C - 1) \lt AB$

　　　　⁝

$(2C - 1) * 1 \lt AB$

となるので、 $2C - 2$ が答えとなります。

$C^2 \lt C(C + 1) \lt AB$ 　　③

③のとき、

$1 * (A + B - 1) \lt AB$

$2(A + B - 2) \lt AB$

　　　　⁝

$(A - 1)(B + 1) \lt AB$

$(A + 1)(2C - A) \lt AB$

$(A + 2)(2C - A - 1) \lt AB$

　　　　⁝

$C * (C + 1)\lt AB$

$(C + 1)C \lt AB$

　　　　⁝

$2C * 1 \lt AB$

となるので、答えは $2C - 1$ となります。

感想

$C$ を使った解法は思いつかないなあと思いました。この解法で、

$1 * (A + B - 1) \lt AB$

の $A + B - 1$ を $2C$ としていないのは、

$A - 1$ と $2C$ の大小関係が分からないためだと思います。 $1 ~ 2C$ の中に $A$ , $B$ が含まれると含んだ値を除かなくてはいけないので、これを回避するためにそのような記述になったと思います。

まあ、答えが $2C - 2$ となっている条件では、 $1 ~ 2C$ の中でペアを作って $A$ と $B$ を除いたものと一致するので、別にいいのかな。

数学的な内容としては大学受験の問題として出されてもおかしくない内容だと思いました。もちろん、誘導ついてないとかなり難しい問題だと思いますが。

でも、整数とか勉強してる人には有名な問題のような気もします。

それと、 $x + y = k$ ( $k$ は一定) の条件下で考えていましたが、別に一定でなくてもよいので、証明とまではいかなくてもこの解説には抜けがあると思います。

一定でない条件下の組み合わせで解説が見たいですね。九九の表とかを書いて、どのように数え上げれば良いのかとか結構考えたんですが、まとまりませんでした。法則性はなんとなくあるんですが、どうなんでしょ。

参考サイト

banboooo.hatenablog.com