問題概要
正整数の集合が次の条件を満たすとき，k-smooth であるとする．
- 任意の 2 要素 $A, B$ ($A \neq B$) について $A \leq kB$
正整数の集合を表す配列 $a$ と正整数 $k$ が与えられる．条件
- 部分集合の全ての 2 要素 $A, B$ ($A \neq B$) について，|A - B| からなる集合が k-smooth である
を満たす部分集合の内，最も要素数が多いものの要素数を求めよ．
- $2 \leq |a| \leq 50$
- $1 \leq a_i \leq 10^9$
- $a_i \neq a_j$ ($i \neq j$)
- $1 \leq k \leq 10^9$
解法
$|a|$ を $N$ とします．また，$a$ の順序には意味が無いので，扱い易いように予め昇順ソートしたとします．
k-smooth であるための条件，$A \leq kB$ は，$A$ を集合の最大元，$B$ を最小元としても成り立っていなければなりません．逆に，そのときに成り立つならば任意の 2 要素について条件を満たします．つまり，集合が k-smooth であるとは「最大元は最小元の $k$ 倍以下である」ということです．
次に，問われている条件について考えます．集合要素の差を集めた集合が k-smooth であることは，先程の言い換えから最大元・最小元をそれぞれ対応する差に置き換えればよいので「もとの集合の最大元と最小元の差が，最も差の小さい 2 要素間の差の $k$ 倍以下である」ことと同値です．最大元を $u$ ，最小元を $l$ とすれば，「任意の要素の差は $\frac{ u - l }{ k }$ 以上である」とも言えます．最大元（の上限）と最小元（の下限）を固定すれば，使える値の範囲と許容される差の最小値が決まります．
この条件下で部分集合を最適に選ぶには，使える要素を小さい方（別に大きい方でもよいけど）から Greedy に選べばよいです．使える要素の内最小のものについて考えたとき，この要素をスルーして後続の要素を入れたとしても，後の選択肢（要素）との差が小さくなって選択肢が減る（または変化無し）ので得にならないからです．この処理は，直前に採用した要素を覚えつつ配列を走査すれば，$O( N )$ 時間でできます（$a$ はソート済みと仮定していました）．
ということで，最大元と最小元の取り方全てについて最適な部分集合を求め，それらの要素数の最大値を求めることで問題を解くことができます．
この解法には，まず $a$ のソートに $O( N \log N )$ 時間がかかります．その後，最大元・最小元の取り方 $O( N^2 )$ 通りに対し，$O( N )$ 時間かけて部分集合を構築するので，全体では $O( N^3 )$ となります．
コード
using LL = long long; using VI = vector< int >; #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__ ) #define ALL( c ) begin( c ), end( c ) #define SZ( v ) ( (int)( v ).size() ) template < typename T > inline bool chmax( T &a, const T &b ){ if ( a < b ) { a = b; return true; } return false; } class CliqueParty { public: int maxsize( vector <int> A, int K ) { const int N = SZ( A ); sort( ALL( A ) ); int res = 0; REP( i, N ) { REP( j, i + 1, N ) { chmax( res, solve( A, K, i, j ) ); } } return res; } int solve( const VI &A, const LL K, const int lb, const int ub ) { const int mi = ( A[ ub ] - A[ lb ] + K - 1 ) / K; int res = 1, p = lb; REP( i, p + 1, ub + 1 ) { if ( mi <= A[i] - A[p] ) { ++res; p = i; } } return res; } };
