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

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

テク:K以上からK+1以上を引く

AtCoder ABC 352 G - Socks 3 (3D, 橙色, 600 点)

「回数の期待値」は、(k 回以上の確率) の総和に一致する!! あとは有名な「 個の一次関数の積は二分木のような計算順序で の計算量で求められるという話! 問題へのリンク 問題概要 色が であるような靴下が 枚ずつある。いずれも 2 種類以上ある。 これら…

AtCoder ABC 180 F - Unbranched (橙色, 600 点)

結構いろんな考え方のできる問題! 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 自己ループを持たない すべての頂点の次数が 2 以下である 各連結成分のサイズを並べた…

HHKB プログラミングコンテスト 2020 F - Random Max (橙色, 600 点)

時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…

第一回日本最強プログラマー学生選手権-予選- F - Candy Retribution (銅色, 1000 点)

てんぷらたんのこれを思い出した!!! yukicoder.me 問題へのリンク 問題概要 要素からなる非負整数 であって 要素を大きい順に並べたとき、 番目と 番目とが等しい という条件を満たすものの個数を で割ったあまりを求めよ。 制約 考えたこと まず、 以上 …

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

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

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

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

AtCoder ARC 100 E - Or Plus Max (黄色, 700 点)

高速ゼータ変換の練習第二弾! 問題へのリンク 問題概要 長さ の整数列 があります。 を満たすすべての整数 について、以下の問題を解け: を < , を満たす整数とするとき、 の最大値を求めよ。 制約 考えたこと 個の要素を一斉に変換する何かをさせている感…

TopCoder SRM 452 DIV1 Hard - IncreasingNumber (本番 0 人)

SRM 埋めを始めたいと思う! ところでこの問題、こんなの気付かないよ...!! まあ、Petr と tourist も参加したコンテストで誰も AC してない問題なので...。 問題文へのリンク 問題概要 10 進法表記で最高次数から順に広義単調増加であるような整数を Incr…

TopCoder TCO 2018 Round 3B Medium - TestProctoring

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