CodeForces

閉路の偶奇

グラフの閉路を検出するのはDFSなりベルマンフォードなりで適当に出来ますよね。 今日奇数長の閉路の検出が出来ずに困ってしまったのでメモ。 全然今まで気付かなかったのですが 「偶数長の閉路しかない⇔2部グラフ」 です。あとはこれより、2部グラフかどう…

Counting Sort

ちょいちょい勉強したことでも書き留めておこうと思います。 Counting Sortというのを知りました。 sortなんてquick sortとmerge sortだけ知ってりゃ十分やとか思ってたんやけど、CFでこれを使う問題が解けんくて悔しかったから書いときます。 この方法は数…

Codeforces Round #284 B Name That Tune

問題概要 N種類の曲があり、それらを順番に流す。聞いている側が曲名が分かり次第流す側に伝える。 流す側は伝えられたらすぐに次の曲を流す。 各曲には認知度p[i]があり毎秒ごとにp[i]%の確率で、そこから1秒で曲名がわかる。 また、各曲の歌詞には曲名がは…

Codeforces Round #FF Div2 E DZY Loves Fibonacci Numbers

最初みたとき解法が全然わからなかったけど以下の2点に気づくだけだった ・フィボナッチ数列同士を足した数列もフィボナッチ数列である ・初項、第2項がa,bのフィボナッチ数列の第n項は基本のフィボナッチ数列をfib[n]としてa*fib[n-1]+b*fib[n-2]とO(1)で求…

最近解いた問題たち

Codeforces #239 C Curious Array 解法がわかった時感動した。問題は至ってシンプルで(l,r,k)のクエリがたくさん飛んでくるから配列のlからr番目までに(j-l+k)C(k)(l≦j≦r)を足す。初期値は関係ないので後で足せばOK。 最初nCr=n-1Cr+n-1Cr-1を使って色々変形…

Codeforces Round #239

これからはCFやTCのメモを書いていこうと思います。(あくまで自分で見返す用なので適当になるとは思いますが許してください) あと、テンプレはもう書きませんが許してください。 A やるだけ。 int a[105]; int main() { int n; cin >> n; for(int i=0;i<n;i++)cin >> a[i</n;i++)cin>…