hotpepsiの練習帳

SRM 684

22:16

https://competitiveprogramming.info/topcoder/srm/round/16688/div/1

Div1 Easy (250) CliqueParty

問題

• 数値の集合Sが与えられる
• 任意の要素A,Bが常にA <= k×Bを満たすとき、良い集合とする
• Sの部分集合Xの任意の要素A,Bの差|A-B|からなる集合をDとする
• Dが良い集合となるXの要素数の最大値を求める

方針

• ソートしておき、区間[i,j]をすべて試す
• 2要素を取り出したとき、差は一つで、これは必ず成立する
• 区間(i,j)の要素を一つずつ試し、成立するなら追加していく
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_684/CliqueParty.cpp

結果

o-- 103.15pt 188th/386 rating 1442 -> 1474 (+32)

問題文に出てくるk-smoothは、数学用語だと、最大の素因数がk以下の数のことらしい。

http://togetter.com/li/947324