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

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

包除原理 の検索結果:

AtCoder Grand Contest 005: D. ~K Perm Counting

…]-i|=Kを使って包除原理を行う。 たとえば K=2 だった場合、それぞれの事象は次のように表せる。 A[1]: a[1]=-1 または 3 A[2]: a[2]=0 または 4 <=== A[3]: a[3]=1 または 5 A[4]: a[4]=2 または 6 A[5]: a[5]=3 または 7 A[6]: a[6]=4 または 8 <=== ... A[2] の発生と A[6] の発生は依存関係があるが、A[2] と A[4] の発生には依存関係はない。一般に依存関…

TopCoder SRM 691 (Div. 2) Hard. Undiv2

…-|A \cap B|-|A \cap C| + |A \cap B \cap C| $$ 最後の式変形は包除原理を使った。包除原理が分からなくてもベン図で OK。 1..n の整数のうち k の倍数は $\lfloor n/k \rfloor$ 個である。このことを使えば f(i,j) も高速に計算できる。 i,j≦100 はあくまで計算量の見積もりの話で、実際は 109 をオーバーしたらループを終えるようにした方がオーバーフローしなくて安心。 med より簡単な気がする。

TopCoder Open 2016 Round 2B Easy. TriangleTriples

…。 これは、機械的に包除原理に放り込んでみたら気がついた。 ということで $$ a+b \le c $$ となる (a,b,c) の数を数える問題を考えてみよう。これは次の領域に含まれる格子点の数に等しい。 大きな三角錐から小さな三角錐を引いてあげれば格子点の数が求まる。A,Bが小さすぎて小さな三角形が重なってしまったら、重複分をキャンセルするように三角錐を足してあげればいい。 gist.github.com こういう数式系苦手なので、ひたすらそれっぽい式を立てて愚直解と比較…

yukicoder No.329 全射

DP

…め方 全射の個数はスターリング数から計算できるので、スターリング数を計算しよう。 スターリング数の漸化式と3つの意味 | 高校数学の美しい物語 ちなみに包除原理でも求まる。 全射の個数の証明とベル数 | 高校数学の美しい物語 こっちだと 200 * 200 * 1000 * log2(1000) 程度のループが回るため多分 TLE する。(自分は TLE した。でも、冪乗を前計算すれば間に合う)。 yukicoder No.329 全射 問題イメージがなかなか捉えられず苦戦。