問題概要
整数 $S$ が与えられる．
最初，$S$ のみを含む多重集合が手元にあり，以下の操作を（それが可能な限りにおいて）好きなだけ行うことができる．
- 集合の元を一つ選んで $z$ とする．ただし $2$ 以上のものしか選べない．
- $x + y = z$ となる正整数 $x, y$ を自由に選ぶ
- 集合から $z$ を取り除き，$x$ と $y$ を加える
- $xy$ のスコアを得る
累計スコア $M $ 以上を獲得するために必要な操作回数の最小値を求めよ．不可能な場合は $-1$ で示せ．
- $2 \leq S \leq 1{,}000$
- $1 \leq M \leq 10^9$
解法
まず解の上限について考えます．$z$ の取り方より，多重集合が $S$ 個の $1$ になってしまうとそれ以上操作できません．従って，操作回数の最大値は $S - 1$ となります．解の候補は $O( S )$ 個ということなので，操作の回数（= 最後に残る元の個数 - 1 ）を決めたときに得られるスコアの最大値を（それなりに効率的に）求めることができれば，$1$ から $S - 1$ を総当りすることで解を探索できます．
ところで，この多重集合というのは $S$ の分割なので，以降そのように呼びます．
分割の要素数を決めたときのスコア
では，最終的な分割の要素数 $K$ を決めたときに得られるスコアについて考えていきます．
分割の各要素を $a_0, a_1, \dots, a_{ K - 1 }$ と呼ぶことにします．$\sum a = S$ です．
分割の手順は $S$ を根，各 $a_i$ を葉とする二分木で表すことができます．内部節点には途中の分割が対応して，$x, y, z$ に対して $z$ が親，$x, y$ が子となります．この各内部節点に対して，$xy$ を計算して足し上げたものが，その分割手順から得られるスコアです．ところで，ある葉 $a_i$ に着目すると $a_i$ がスコアに関係するのは $a_i$ の祖先にあたる内部節点だけです．それらの内部節点について，$a_i$ を部分木に含まない方の子に着目すると，$i \neq j$ なる $a_j$ が丁度一回ずつ出現します．従って，$a_i$ によるスコアへの寄与は $\sum \{ a_ia_j \mid i \neq j \}$ となります．全ての $i$ について同様のことが言えて，結局スコアは $$\sum_{ i = 0 }^{ K - 1 }\sum_{ j = i + 1 }^{ K - 1 } a_ia_j$$ となります．つまり，分割が決まるとスコアは途中の手順に依らず一意に決まります．
ところで，以降簡単のために上の式ではなくて $\sum \{ a_i a_j \mid i \neq j \}$ で考えます．添字をひっくり返したもの（値は同じ）ものを足しているだけなので，$2$ で割ると元の式の値に一致します．これで計算して後から $2$ で割ることにしても問題ありません．
最適な分割
では，要素数 $K$ を決めたときの最適な分割とはどのようなものでしょうか？
今，ある（てきとーな）分割 $a$ が決まっているとして，$a$ を弄ることでよりよい分割を得ることを考えます．2 つの要素 $a_p, a_q$ を選んで，片方を +1 ，もう片方を -1 すると考えます（操作が可能なように要素を選ぶと仮定します）．すなわち，$a_p \to a_p + 1$, $a_q \to a_q - 1$ と置き換えます．そうしたときのスコアの変化は，着目する要素の添字と $p, q$ との関係によって場合分けすると，
- $a_p a_q \to ( a_p + 1 )( a_q - 1 ) = a_p a_q - a_p + a_q - 1$
- $a_p a_k \to ( a_p + 1 ) a_k = a_p a_k + a_k$ ( where $k \neq q$ )
- $a_k a_q \to a_k ( a_q - 1 ) = a_k a_q - a_k$ ( where $k \neq p$ )
と変化します．
変更前との差分に着目するとそれぞれ，
- $-a_p + a_q - 1$
- $a_k$ ( where $k \neq q$ )
- $-a_k$ ( where $k \neq p$ )
となりますが，冷静に考えると下 2 つの $a_k$ の総和は同じ値です（添字が $p, q$ 以外の全てを通る）．正負で打ち消し合うので残るのは 1 番目の場合の差分 $$-a_p + a_q - 1$$ だけということになります．式の意味を考えると，2 箇所選んで +1, -1 すると，スコアは -1 される要素の分増えて，+1 される要素の分 + 1 だけ減るということになります．明らかに $a_p < a_q$ の方が得なのでそのように仮定し，$d = a_q - a_p$ とします．$d$ を使って差分を書き直すと，$$\begin{align} -a_p + a_q - 1 &= -a_p + ( a_p + d ) - 1\\ &= d - 1 \end{align}$$ となります．つまり，$d \geq 2$ のとき，分割を変更した方がスコアがよくなります．任意の要素対について差が $2$ 以下になるまで変更を繰り返すと，それ以上スコアを改善できなくなって最適な分割が得られます．要するに，なるべく均等に分けた方がよいということが言えます．
スコアの計算
最適な分割の仕方が分かったので，$K$ を与えられたときのスコアを計算する方法について考えます．
まず，$\lfloor \frac S K \rfloor = n$ とすると，分割のどの要素も $n$ 以上となっています．これだけだと $S - Kn$ だけ余っているので，それらを $1$ ずつ別々の要素に振り分けます．そうすると分割の各要素は $n$ または $n + 1$ となります（先程の $d$ の条件に違反しない均等な分割）．で，$n + 1$ の個数 $g$ は $S \bmod K$ で，$n$ の数 $l$ は残りなので $K - g$ です．$n$ のスコアへの寄与は 1 つあたり $n ( S - n )$ なので全部で $ln ( S - n )$，$n + 1$ のスコアへの寄与は 1 つあたり $( n + 1 )( S - n - 1 )$ なので全部で $g ( n + 1 )( S - n - 1 )$ です．これらを足してから $2$ で割れば，欲しい（題意通りの）スコアとなります．
まとめ
あとは，分割の要素数 $K$ を小さい方から総当りして，スコア $M $ 以上を達成できるものを見つけたらそれを return すればよいです．$S$ まで試しても見つからなければ不可能なケースなので $-1$ を return します．
この解法は，試すべき解の候補が $O( S )$ 通りあって，それぞれに対するスコアの計算は $O( 1 )$ 時間でできるので，全体で $O( S )$ 時間となります．
コード
#define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) class SubdividedSlimes { public: int needCut( int S, int M ) { REP( i, S ) { if ( M <= calc( S, i + 1 ) ) { return i; } } return -1; } int calc( const int S, const int K ) { const int n = S / K, b = S % K, a = K - b; return ( a * n * ( S - n ) + b * ( n + 1 ) * ( S - n - 1 ) ) / 2; } };
