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

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

期待値

AOJ 2385 Shelter (AOJ-ICPC 700 点)

ボロノイ図の応用問題! 問題へのリンク editorials 問題概要 頂点数 の凸多角形があって、その内部に 個の点が与えられる。凸多角形の内部に一様ランダムに点を打つとき、以下の値の期待値を求めよ。 「その点 から 個の点までの距離の最小値」を二乗した値…

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

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

yukicoder No.155 生放送とBGM

戻す DP シリーズのトレーニング 問題へのリンク 問題概要 (入力形式は多少改変) 正の整数 と、 個の正の整数 が与えられる。これらをランダムシャッフルする。 を満たす最小の を考える。この値の期待値を求めよ (要求精度は )。 制約 考えたこと 各要素 に…

AtCoder ARC 104 E - Random LIS (赤色, 700 点)

ゲーは確かに面白いかもしれない。 問題へのリンク 問題概要 長さ の整数列 が与えらる。 同じく長さ の整数列 は、 各 について独立に、 を満たす整数の一様分布からランダムに選ばれる。 このとき、 の最長増加部分列の長さの期待値を mod 1000000007 で計…

ACL Contest 1 E - Shuffle Window (橙色, 900 点)

コンテスト中に まで導いておきながら、最後詰めきれなかったのは反省。 問題へのリンク 問題概要 の順列 と、2 以上の整数 が与えられる。 に対して順に以下の操作を行う。 をランダムシャッフルする 回の操作後に得られる順列の転倒数の期待値を、mod 9982…

AOJ 3182 Umg Kart (HUPC 2020 day3-K)

確かに、えでゅふぉのラス問にありそう! 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …

Codeforces CodeCraft-20 (Div. 2) F. Battalion Strength (R2800)

実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…

AtCoder AGC 006 C - Rabbit Exercise (銅色, 800 点)

操作を 回行った結果を求める系、苦手意識あるけど克服したい! 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…

AtCoder ABC 154 D - Dice in Line (茶色, 400 点)

期待値の線形性!!! 問題へのリンク 問題概要 個のサイコロが左から右に一列に並べてある。 番目のサイコロは目が となっていて、これらが当確率に出る。 隣接する 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めよ。…

第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes (青色, 600 点)

期待値の線形性的な。 問題へのリンク 問題概要 体のスライムがそれぞれ の位置にいる (これらは単調増加)。 以下の 通りのスライム合体過程それぞれについて、スライムの移動距離の総和を考える。その総和距離の総和を求めよ。1000000007 で割ったあまりで…

TopCoder SRM 400 D1H CollectingBonuses

ついこの間の AGC でもあった「〜が終了するまでの回数の期待値」に関する問題!!! それにしても数値誤差しゃん... 150 人が提出してAC 2 人という恐ろしい問題。 実はこの回の writer であった ymatux さんから、直接話を聞いたのだった。Petr はこの回 r…

Codeforces 551 DIV2 F - Serval and Bonus Problem (R2800)

こういうのに慣れて行きたい。 問題へのリンク 問題概要 長さ の線分上に、ランダムな区間を 個とったときの、区間が 本以上重なっている部分の長さの期待値を求めよ (998244353 で割った余りの形式で)。 なお、区間のランダムな選び方とは、線分から 2 点ず…

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 で正解し、残…

AOJ 2171 Strange Couple (AOJ-ICPC 600 点)

ランダムウォークな問題! 実数係数の連立方程式の練習に 問題へのリンク 問題概要 頂点の重み付き無向グラフが与えられる。ただし自己ループを含み得る (多重辺はない)。二頂点 が指定されていて、 から へとランダムウォークによって辿り着きたい。 ただし…

みんなのプロコン 2019 決勝 A - Affiches (500 点)

積分した 問題へのリンク 問題概要 サイズ の長方形の紙と、それよりサイズの小さいサイズ の長方形の紙が 2 枚あります。 2 枚の小さいサイズの紙を、それぞれ、大きいサイズの紙の中に包含される範囲内でランダムに配置します (その位置は連続量)。 このと…

キーエンス プログラミング コンテスト 2019 F - Paper Cutting (赤色, 900 点)

このシンプル設定でこの深み...すごい!!! や は順列や組合せを表すものとする。 問題へのリンク 問題概要 長方形の紙があって、水平方向の切れ線が 箇所、垂直方向の切れ線が 箇所ある。 箇所の切れ線から 箇所選んで順に切って行く 通りの方法それぞれに…

AOJ 2336 スプリング・タイル (AOJ-ICPC 600 点)

グリッド系は苦手意識あるけど解けてよかった 問題へのリンク 問題概要 二次元マップが与えられて、各マスは 床 ('.') 壁 ('#') バネ ('*') の 3 つの属性がある。スタート ('s') とゴール ('g') が設定されていて、いずれも床属性である。 s から g へ最速…

TCO 2018 Round 3B Med TestProctoring

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