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

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

サイコロ

AtCoder ABC 300 E - Dice Product 3 (水色, 500 点)

確率や期待値を計算する DP をするときは、自己ループを除去することが多いね。 問題へのリンク 「EDPC J - ボール」などは類題と言える。先にこの問題を解いておくと、今回の問題も解きやすいかもしれない! qiita.com 問題概要 以上 以下の整数が等確率で…

Xmas Contest 2020 B - Beterminant

なぜか埋め込みにこだわってしまい、本番 AC できなかった... 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす最大の正の整数 を求めよ (存在しない場合は -1、無限個存在する場合は -2)。 確率 % で表が出るサイコロを 回振るとする 表が出…

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

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

AtCoder ARC 102 E - Stop. Otherwise... (橙色, 700 点)

いろんな解法がありそうなんな 問題へのリンク 問題概要 整数 が与えられる。各 に対して、 どの に対しても を満たす整数組 の個数を で割った余りを求めよ ( 面サイコロを 個振るという設定)。 制約 解法 1: 漸化式を立ててそれを展開 (本番で通した解法) …