問題

atcoder.jp

考えたこと

まず条件を整理

順位付けとは「全単射」
1回目i位の人が、2回目でp(i)位を取ったとする。
i×p(i) < ABになるiの個数を最大化。
ただし、p(i)は相異なり、p(A) = B.

貪欲法に帰着 → 実験

p(i)の値域を考えると、
S(i) = {j | j: int, j >= 1, i×j < AB, j≠B} if i≠A
S(A) = {B} if i = A として
p(i) in S(i)なるiの個数を最大化。
i < jについて、S(i)はS(j)を包含。iが大きいほど選択肢は狭い。
厳密なことはさておき、iが大きい方から見て、「S(i)から選べるなら選ぶ（＆最も小さいのを選ぶ）」としてよさそう。
ここまで分かれば、とりあえず実験できますね。
- うーん、分からん。
  A=4, B=5の実験

対称性

忘れてたけど、対称性よりA <= Bを仮定して良いですね。
以降は、A <= Bを仮定します。

重要そうな条件を式で表してみる

A = 5, B = 5, 6, 7, …などで
貪欲法の実験をしていると、iがある値以下ならp(i) in S(i)が常に成立していそう（多分i <= A - 1？）に思えた。
これを示したい気持ちになると、
「S(i)がB + 1を含む条件 (Bが邪魔にならない）」
「S(i)の大きさが狭義単調増加な条件（p(i+1)が邪魔にならない）」
を知りたくなる。

まず、ij < AB ⇔ j < AB / i ⇔ j <= [(AB - 1) / i]
ここでは、[]で小数点以下切捨てを表します。

定式化：
+ i: int, i >= 1
+ [(AB - 1) / i] > B
+ [(AB - 1) / i] > [(AB - 1) / (i + 1)]
(箇条書きにならない。help！）

[(AB - 1) / i] > B

(AB - 1) / i >= B + 1
AB - 1 >= i(B + 1)

i = Aのとき
A(B + 1) > AB - 1よりNG.

i = A - 1のとき
(A - 1)(B + 1) = AB + A - B - 1
A <= Bを仮定すると
AB + (A - B) - 1 <= AB - 1
よりOK.
A <= Bを仮定すると、1つ目の条件は単に「i < A」と言える。

[(AB - 1) / i] > [(AB - 1) / (i + 1)]

AB - 1 = pi + r (p, r: int, 0 <= r < i)
AB - 1 = q(i + 1) + s (q, s: int, 0 <= s < i + 1)
として、p > qになる条件を探せばよい。
まず、p = [AB / i] >= [AB / (i + 1)] = qなので、p >= q.

pi + r = q(i + 1) + s
pi + r = qi + (q + s)
より、p = qならば、r = q + s. つまり, q + s >= iが条件.

i < Aのとき、i + 1 <= A.
q = [(AB - 1) / (i + 1)] >= [(AB - 1) / A] >= B - 1.
A <= Bを仮定すると、q >= A - 1.
よって、「i < A」のときは常に成立

中間まとめ

以上より、i < Aのときは、p(i) > Bかつp(1), …, p(A-1)を相異なるように構成できる。
i > Aのときの取れる個数が本質になった。

i > Aのとき

そもそも[(AB - 1) / i] < Bなので、「Bを取っちゃダメ」という条件を無視して考えられる。
あと、「段差が1以下」が成り立っていると都合が良いな～って思っているので、
それが成り立つ十分条件を定式化してみる。

定式化：
・(AB - 1) / i - (AB - 1) / (i + 1) <= 1
(AB - 1) * (i + 1) - (AB - 1) * i <= i(i + 1)
(AB - 1) <= i(i + 1)
これは、i > Aで常に成立…しません！！！（一敗）
でもこれが成り立つ最小のiは2分探索で求められる。
i >= i0で成立するような最小のi0 (i0: int) を取ると、(i0 <- max(A + 1, i0)をしておく）
・i >= i0までで、1 ～ [(AB - 1) / i0]まで取られる。
・A + 1 <= i < i0では、異なる値がしっかり取られる。

まとめ

対称性より、A<=Bとする（重要）
i<Aとi>Aを別々に最大化できる
i<Aでは常にp(i) in S(i)にできる
i>Aでは、(AB - 1) <= i(i + 1), i>=A+1なる最小のiをi0とおくと
- i>=i0までで、1～[(AB-1)/i0]まで取られる
- i<i0では、相異なる値がしっかり取られる
- i0は2分探索で求められる. Aではダメ、ある値からOKで、B+1ではOK.
  - A = Bのとき、i0 <= Bを仮定できないことに注意（一敗）

よって、i0を求め、[(AB-1) / i0] - (i0 - 2)を出力すればよい。
（i0 - 2はi in {1,2,…,i0-1} - {A} なるiの個数）

ソースコード

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

signed main() {
    int q, a, b;
    cin >> q;
    while (q--) {
        cin >> a >> b;
        if (a > b) swap(a, b);
        int ng = a, ok = max(a + 1, b);
        while (ok - ng >= 2) {
            int mid = (ng + ok) / 2;
            if (mid * (mid + 1) >= a * b - 1) ok = mid;
            else ng = mid;
        }
        cout << ((a * b - 1) / ok) + ok - 2 << endl;
    }
    return 0;
}

感想

これ、難しくないですか？
条件を定式化する力を求められているように感じました。

式変形をしてから気付いたけど、貪欲法に帰着するパートで「最小順位」ではなくて「最大順位」を取るようにすると（そのようにしてもOK）、解法と同じ構成になっているから、もっと分かりやすかったかもしれない。
これに気付くには、「逆に〇〇したらどうだろうか」をするか、「(AB - 1) / iのグラフの性質を活かすには、最小（途中）を取るよりも、最大（一番上）を取る方がよさそう」をすると良いのかなあと思った。

startcpp’s blog

ARC 094 D. Worst Case

問題