Codeforces Ozon Tech Challenge 2020 (Div.1 + Div.2) E. Kuroni and the Score Distribution

問題概要

整数 $n, m$ が与えられる。以下の条件を満たす長さ $n$ の数列 $a_{1}, ..., a_{n}$ を1つ構築するか、そのようなものが存在しないことを判定せよ。

各要素は $10^{9}$ 以下の正整数である。
狭義単調増加である。
$i \lt j \lt k$ かつ $a_{i}+a_{j}=a_{k}$ を満たす3つ組 $(i, j, k)$ の個数はちょうど $m$ 個である。

制約

$1 \le n \le 5000$
$0 \le m \le 10^{9}$

解法

$i \lt j \lt k$ かつ $a_{i}+a_{j}=a_{k}$ を満たすような3つ組 $(i, j, k)$ を最も多くできる数列は、 $1, 2, ..., n$ です。これをまず証明します。

$k=1, 2, 3, ...$ と小さい方から見ていきます。このとき $a_{k}$ より手前にある要素は $k-1$ 個であり、これらの中から $a_{i}+a_{j}=a_{k}$ を満たす $(i, j)$ のペアを最大でいくつまで作ることができるか考えます。ここで全ての要素が異なることから「和が同じになる2つのペアが、片方の要素だけ共通している」ということはあり得ないので、条件を満たす $(i, j)$ のペア同士が共通要素を持つことはなく、このような $(i, j)$ は多くとも $\lfloor\frac{k-1}{2}\rfloor$ 個しか作れません。

そして $1, 2, ..., n$ という数列は、以下の図のように任意の $k$ に対して $a_{i}+a_{j}=a_{k}$ を満たす $(i, j)$ が $\lfloor\frac{k-1}{2}\rfloor$ 個存在します。よってこれが最大値を実現する数列となります。

f:id:betrue12:20200304120507p:plain

ということで、これをベースに作りましょう。具体的には要素を $a_{1}=1, a_{2}=2, ...$ と追加していきながら、 $a_{k} = k$ を追加することで条件を満たす3つ組 $(i, j, k)$ がいくつ増えるか（つまり $\lfloor\frac{k-1}{2}\rfloor$ ）を計算し、以下のように場合分けします。

条件を満たす3つ組の個数が既に $m$ である場合

このときは、3つ組作りに絶対に関係しないような大きい値で埋めてしまえば良いです。

増加分 $\lfloor\frac{k-1}{2}\rfloor$ があっても合計が $m$ を超えない場合

このときは、そのまま $a_{k} = k$ を追加すれば良いです。

増加分 $\lfloor\frac{k-1}{2}\rfloor$ があると合計が $m$ を超える場合

このときは、追加する値を後ろにずらすことで調整できます。以下の図のように考えると、 $a_{k} = k + d$ としたときには条件を満たす3つ組 $(i, j, k)$ は $\lfloor\frac{k-1-d}{2}\rfloor$ 個になるので、合計がちょうど $m$ になるまで $d$ を増やして調整すれば良いです。

これまでの連番が崩れますが、次からは「条件を満たす3つ組の個数が既に $m$ である場合」に該当し、あとは大きい値を詰めるだけなので大丈夫です。

f:id:betrue12:20200304120915p:plain

この手順で構築していって、もし $1, 2, ..., n$ まで追加しても $m$ に届かない場合は構築不可能です。

大きい値で埋めるときには、その大きい値同士の差が小さい方で使っている値と一致しないように注意しましょう。例えば埋めるのに $999998000, 999999000$ を使っていて、下の方で $1000$ を使っていたりするとアウトです。下の方を作り終わってからその最大値+1などの間隔で上の方を埋めるか、余裕を持って $20000$ くらいの間隔を取っておけば良いです。