トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

順列・組み合わせ

[アルゴリズム]

練習のための問題は 競技プログラミングの履歴

順列・組み合わせ

  順列(N!)

  • Rubyでベンチマークをとってみる
require 'benchmark'

def perm_bench(n)
  elements = (1..n).to_a
  result = Benchmark.realtime do
    elements.to_a.permutation do |picked|
    end
  end
  puts sprintf( "time: %.3f => %s", result, elements)
end

for i in 1..11
  perm_bench(i)
end
  • 結果
    • 1 <= N <= 8 ならばまだ競技プログラミングで使えそう
    • N = 9 で 0.06s
    • N = 10 で 0.66s
    • N = 11 で 7.29s
ruby perm-1.rb 
time: 0.000 => [1]
time: 0.000 => [1, 2]
time: 0.000 => [1, 2, 3]
time: 0.000 => [1, 2, 3, 4]
time: 0.000 => [1, 2, 3, 4, 5]
time: 0.000 => [1, 2, 3, 4, 5, 6]
time: 0.001 => [1, 2, 3, 4, 5, 6, 7]
time: 0.007 => [1, 2, 3, 4, 5, 6, 7, 8]
time: 0.067 => [1, 2, 3, 4, 5, 6, 7, 8, 9]
time: 0.660 => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
time: 7.292 => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

  組み合わせ(nCr)

繰り返し2乗法と階乗のmod逆元を使って求めるやり方

階乗のmod逆元 - 組み合わせ

動的計画法

  • nCrを動的計画法で求めるやり方

動的計画法 - 組み合わせ

  順列・組み合わせの周辺概念

期待値の線形性

お名前: コメント: