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

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

2019-03-23から1日間の記事一覧

Codeforces #548 Div. 2 D - Steps to One (R2300)

これだった!!! drken1215.hatenablog.com もちろん高速ゼータ変換はいらなくて、愚直な包除原理で間に合う。 問題概要 整数 が与えられる。空の vector があって 以上 以下の整数の中から一様ランダムに 1 つ選び、 それを vector に push する このとき …

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

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

AtCoder ABC 078 C - HSI (ARC 085 C) (茶色, 300 点)

期待値に関するセンスがちょっと求められる問題 問題へのリンク 問題概要 高橋君はテストケースが ケースある Yes/No 判定問題に対して、ソースコードを提出したところ 問で TLE して、残りの 問は正解しました。 そこで「 問については 100ms で正解し、残…

Educational Codeforces 62 C - Playlist (R1600)

楽しかった 問題へのリンク 問題概要 個のアイテムがあって、それぞれ時間 と美しさ の属性がある。今、 個の中から 個選びたい。選んだアイテムたちのスコアは (選んだアイテムの時間の総和) × (選んだアイテムの美しさの最小値) で決まる。このスコアの最…

Educational Codeforces 62 E - Palindrome-less Arrays (R2200)

楽しかった 問題へのリンク 問題概要 未完成の数列 が与えられる。未完成部分には が書かれている。完成部分には 以上 以下の整数が書かれている。 のところを 以上 以下の整数を埋める方法であって、整数列が奇数長の回文を含まないものは何通りあるか? 制…