D - Worst Case Editorial by kyopro_friends
\(A_i,B_i\) を単に \(A,B\) と書きます。
必要なら \(A,B\) をswapすることで \(A\leq B\) としてよいです。\(N=AB\) とおきます。問題の目的は、\((x_i,y_i)\) の集合であって次の条件を全て満たす最大の集合のサイズを求めることです。
- \(x_i\) に重複がない
- \(y_i\) に重複がない
- 全ての \(i\) で\(x_iy_i \leq N-1\)
- 全ての \(i\) で \(x_i \neq A\)
- 全ての \(i\) で \(y_i \neq B\)
\(K=\lfloor \sqrt{N-1}\rfloor\) とします。\(xy<N\) であるためには、「\(x\leq K\) または \(y\leq K\)」が必要です。したがって、\((1,*),(2,*),\ldots,(K,*),(*,1),(*,2),\ldots,(*,K)\) という形で条件を満たす集合を作ることができればそれが最大になります。これら \(2K\) 個の組に対して、\(*\) の決め方を考えます。
予め次の2つの処理をしておきます。
- \(K\) 以下の値は “予約” されているので、\(*\) には可能な限り \(K+1\) 以上の値を割り当てたいです。しかし、\(K(K+1)>N-1\) のときには、\(x=K\) に対して \(y\) を \(K+1\) 以上にすることはできません。つまり \((K,*)\) は \((*,1),(*,2),\ldots,(*,K)\) のいずれかと一致します。\(y=K\) の場合も同様であることを考慮すると、\((K,K)\) という組を作るのが良さそうです（\(K*K \leq \lfloor \sqrt{N-1}\rfloor^2\leq \sqrt{N-1}^2=N-1 \) なのでこの組は有効です）。
現時点ではまだ「\((K,K)\) という組を作ったとき、残りがうまく決められるならこれが最善」としか言っておらず、残りがうまく決められるかどうかには言及していないことに注意してください。 - \(A\leq K\) のとき、\((1,*),(2,*),\ldots,(K,*)\) のいずれか\(1\) つは使えません。よって、そのようなものは予め取り除いておきます。これは、\(*\) の決め方に依りません。
上記処理ののち、\((i,*)\) に対しては \((i,\lfloor \frac{N-1}{i}\rfloor)\)、 \((*,i)\) に対しては \((\lfloor \frac{N-1}{i}\rfloor,i)\) と値を決めます。(\(K\) 以下の値は”予約”されているので、出来るだけ大きな値を使おう、という気持ちで作られています)
こうして出来た組は条件を満たします。
証明
冒頭に挙げた5つの条件を満たすか順に確かめます。
1番目
「$\lfloor \frac{N-1}{i}\rfloor$ の中に重複がないこと」と「$\lfloor \frac{N-1}{i}\rfloor$ たちと $1,2,\ldots,K$ が重複しないこと」を示せば良い。
$i < K$ において $\frac{N-1}{i}- \frac{N-1}{i+1}=\frac{N-1}{i(i+1)} >\frac{N-1}{K^2} \geq1$ なので、$\lfloor \frac{N-1}{i}\rfloor$ は $i=1,\ldots,K$ において相異なる。
また、$i\leq K-1$ のとき、$\lfloor \frac{N-1}{i}\rfloor \geq \lfloor \frac{N-1}{K-1}\rfloor\geq K+1>K$ であることから、$\lfloor \frac{N-1}{i}\rfloor$ は $1,\ldots,K$ とは異なる。さらに、$N-1\geq K(K+1)$ であれば $\lfloor \frac{N-1}{K}\rfloor\geq K+1>K$ であることから、$\lfloor \frac{N-1}{K}\rfloor$ は $1,\ldots,K$とは異なる。
よって $x_i$ は相異なる。
2番目は1番目と全く同様
3,4番目は作り方から明らか
5番目
$B\leq K$ となることはないので、$\lfloor \frac{AB-1}{i}\rfloor=B$ となる $i$ が存在しないことを示せば良い。 $\frac{AB-1}{i}$ は $i$ について単調減少であり、$i=A-1$ のとき $\frac{AB-1}{i}=B+\frac{B-1}{A-1}\geq B+1$、 $i=A$ のとき $\frac{AB-1}{i}=B-\frac{1}{A}< B$ なので、そのようなものは存在しない。
以上より、最初の処理により取り除かれる組の個数によって、答えは \(2K,2K-1,2K-2\) のいずれかとなります。
posted:
last update: