けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

包除原理

「〜がすべて終わるまでの試行回数の期待値」を求める一般的なフレームワーク

0. プロローグ 期待値にまつわる有名事実として、以下のことが一般によく知られていて、競プロでも過去何度も出題例がある!!! 確率 で成功する試行を成功するまで続けたとき、成功するまでの回数の期待値は である 個の品物がランダムに出力されるコンプ…

AOJ 2935 赤黒そーるじぇむ (RUPC 2019 day3-F)

楽しい!!!好き!!! 問題へのリンク 問題概要 頂点のグラフを作って各頂点に赤黒に色をつけたい。そのような 通りの方法のうち、以下の条件を満たすような方法が何通りあるか で割ったあまりを求めよ。 どの赤い頂点も、なんらかの黒い頂点とつながって…

yukicoder No.802 だいたい等差数列

面白い!!!!!!!!! 問題へのリンク 問題概要 長さ の整数列 であって、 を満たすものの個数を 1000000007 で割ったあまりを求めよ。 制約 まずは変数変換 まずは数列 の差分に注目してみることにする。 とする ( とする)。そうすると、条件は () とい…

全国統一プログラミング王決定戦 本選 E - Erasure (700 点)

700 点は絶対落とさないのん!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間がある。 これ…

AtCoder ARC 064 F - Rotated Palindromes (赤色, 1000 点)

約数系包除。かなり教育的要素の多い問題だと思った!!!!! 操作によって何通りできるのかを問う問題の取り組み方 約数系包除の考え方 問題へのリンク 問題概要 以上 以下の整数からなる数列のうち、以下のようにしてつくられるものは何通りあるか、10000…

QUPC 2018 I - Buffalo

楽しいけど重くて、重いけど楽しい 問題へのリンク 問題概要 要素から成る数列 が与えられる。 個から 2 個選んでできる 通りのペア のうち、以下の条件を満たすものを数え上げよ。 容量が の容器を用意して、以下の操作によって水の量 を汲み取れる 操作 1:…

AOJ 2136 Webby Subway (JAG 夏合宿 2008 day2-F)

最大 22 頂点のグラフの彩色数を求める問題 問題へのリンク 問題概要 本の折れ線が与えられる。折れ線に対応した 頂点のグラフを考える。対応する折れ線同士が交差するところに辺を張る。 このグラフの彩色数を求めよ。 制約 解法 前半の幾何は虚無。実質的…

AtCoder EDPC Y - Grid 2

座圧に見えてしまった 問題へのリンク 問題概要 のグリッドがあります。グリッドのうち マスに壁があって壁の位置は で与えられます。壁のあるマスには行けません。 マス からマス へと至る最短経路が何通りあるか、 で割ったあまりを求めよ。 制約 考えたこ…

JOI 春合宿 2011 day2-2 Keycards (難易度9)

包除原理と聞いて 問題へのリンク 問題概要 JOI の春合宿が行われる施設の宿泊棟の部屋の鍵は,カードに穴がいくつか開いた形状をしている.穴を開ける位置の候補は N 個あり,これらのうちいくつかに穴を開けた 2N 枚の異なる鍵が作られた. あなたは,JOI …

AtCoder ARC 102 E - Stop. Otherwise... (橙色, 700 点)

いろんな解法がありそうなんな 問題へのリンク 問題概要 (ARC 102 E) 整数 が与えられる。各 に対して、 どの に対しても を満たす整数組 の個数を で割った余りを求めよ ( 面サイコロを 個振るという設定)。 制約 解法 1: 漸化式を立ててそれを展開 (本番で…

TCO 2018 Round 3B Medium - TestProctoring

楽しい!!!!!!!!!すごく勉強になったん!!!!! 大きく 2 つのやり方があって、高速ゼータ変換を用いた O(3n) から O(n2n) への高速化や、期待値に関する重要な考察をするなど色々やれるん。 問題概要 人がテストを行う。 毎秒ごとに 番目の人がテ…

みんなのプロコン 2018 決勝 A - Uncommon (包除原理)(600 点)

包除原理練習第二弾なん! という制約の意味に気がつくのにかなり時間がかかったん。これのおかげで「 の中に の倍数が何個あるか」というのが、 ではなく でできるのんな。 Uncommon へのリンク 問題概要 個の相異なる整数 と、整数 が与えられる。各 に対…

AtCoder AGC 005 D - ~K Perm Counting (赤色, 900 点)

包除原理勉強会の一環。なんか最初、0〜N-1 を 2K で割った余りで類別したところで鎖を作って、そこでのサイズ i のマッチングの個数を数えたりしたのだけど、それをマージするのに NTT を使うとか血迷った^^; https://beta.atcoder.jp/contests/agc005/subm…

スターリング数と、問題まとめ

この間分割数の記事についての記事を書いたときに続けてスターリング数も次回書くつもりですっかり忘れていたので書こうと思い立ちました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含…