結果

問題 No.3030 Kruskal-Katona
ユーザー magurofly
提出日時 2025-02-21 21:55:33
言語 Ruby
(3.4.1)
結果
AC  
実行時間 113 ms / 2,000 ms
コード長 1,061 bytes
コンパイル時間 545 ms
コンパイル使用メモリ 7,936 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2025-02-21 21:55:44
合計ジャッジ時間 4,246 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

main = -> {
	n, i = gets.split.map(&:to_i)
	ans = []
	i.downto(1) do |j|
		m = (j ..).bsearch { |k| k.nCr(j) > n }
		ans << m - 1
		n -= (m - 1).nCr(j)
		break if n == 0
	end
	puts ans.join(" ")
}

class Integer
  def div_ceil(y); (self + y - 1) / y end
  def mod_inv(mod = MOD); pow(mod-2, mod) end
  def mod_div(y, mod = MOD); self * y.mod_inv(mod) % mod end
  def mod_nCr(r, mod = MOD); x = y = 1; (1..r).each { |i| x = x * (self + 1 - i) % mod; y = y * i % mod }; x.mod_div(y, mod); end
  def factorial(mod = MOD); (2..self).inject(1) { |f, x| f * x % mod } end
  def popcount; x = self; c = 0; while x > 0; c += 1 if x & 1 == 1; x >>= 1 end; c end #TODO: faster
  def bitbrute(&block); (1<<self).times(&block) end
  def nCr(r); x = 1; (1..r).each { |i| x *= self + 1 - i; x /= i }; x; end
  def each_divisor; return Enumerator.new { |y| each_divisor { |k| y << k } } unless block_given?; k = 1; while k * k < self; if self % k == 0; yield k; yield self / k end; k += 1; end; yield k if k * k == self end
  def divisors; each_divisor.to_a end
end

main.call
0