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

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

確率

AOJ 3182 Umg Kart (HUPC 2020 day3-K)

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

Educational Codeforces Round 81 F. Good Contest (R2600)

座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制約 考えたこと 区間の幅は大きいが、 …

TopCoder SRM 400 D1H CollectingBonuses

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

fiord 君からのトランプ増加列シミュレーション問題

楽しかったので。 問題概要 1 から 13 までの数字が書かれたカードが 1 枚ずつある。これをよくシャッフルして山札として並べて、1 枚ずつ引く。 このとき、引いたカードが「手札カードの数値の最大値」よりも小さかったらそのカードを捨て、そうでなかった…

AtCoder ABC 126 C - Dice and Coin (茶色, 300 点)

確率を確実に 問題へのリンク 問題概要 正の整数 が与えられる。 最初に の整数値をランダムに出力する。以降コインを振って 表が出たら整数値を 2 倍する ( 以上になったら「勝ち」でゲーム終了) 裏が出たら整数値を 0 にする (こうなった時点で「負け」で…

CODE FESTIVAL 2018 Final B - Theme Color (300 点)

さ、300 点!? 問題へのリンク 問題概要 個の中からランダムに選ぶ試行を 回行う。それぞれのものが出た回数が 回になる確率を としたとき、 を満たすような最小の を求めよ。 制約 考えたこと 確率を求めること自体は難しくなくて、 で求められる。が、こ…

AtCoder AGC 021 B - Holes (黄色, 600 点)

駅メモ!駅メモ!駅メモ!!!!! 問題へのリンク 問題概要 座標平面上に 個の頂点がある。各頂点の座標は で与えられる。 原点を中心とする半径 の円内の点をランダムに選び、与えられた 個の点の中から最も近い距離にある点へと移動する。 各点について、…

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

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

AOJ 2237 The Castle (AOJ-ICPC 500 点)

一目見て bitDP なのはわかるのだけど、手こずった...ウチ弱すぎるのん... 問題へのリンク 問題概要 匹の猫をステージ に順番に送り込む 猫 がステージ をクリアできる確率は 猫 がステージ をクリアしたら、次のステージ もその猫で挑まなければならない 猫…