読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, Single Round Match 669, Division 1, Level 1 - SubdividedSlimes

問題概要

 整数 $S$ が与えられる.
 最初,$S$ のみを含む多重集合が手元にあり,以下の操作を(それが可能な限りにおいて)好きなだけ行うことができる.

  1. 集合の元を一つ選んで $z$ とする.ただし $2$ 以上のものしか選べない.
  2. $x + y = z$ となる正整数 $x, y$ を自由に選ぶ
  3. 集合から $z$ を取り除き,$x$ と $y$ を加える
  4. $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;
	}
};