京セラプログラミングコンテスト2022 (AtCoder Beginner Contest 271) G - Access Counter (600)
簡単な場合を考えると、
全て高橋君がアクセスするなら0%
全て青木君がアクセスするなら100%
$ 24 \times 24の正方行列を考える
$ nが大きいので愚直に求められないので行列累乗で高速化する
これは$ i 時に$ k回目のアクセスがあったときに$ k+1回目のアクセスが$ j時になる期待値
1時間後になる確率は$ p_{i+1}
$ p_iは$ xか$ yのどちらか
2時間後になる確率は$ (1-p_{i+1})p_{i+2}
24時間後になる確率は$ (1-p_{i+1})\cdots(1-p_{i+23})p_i
25時間後以降はループして1時間後の確率で考えられる
1-24時間後までの確率の和が1になる必要があるのでそのように正規化する
また0回目の確率については初回が0時なので23時にいることにしておく
行列の計算で$ n回目がどの時間になるかの確率が求まるので青木君がアクセスする時間のみ足し合わせたのが答え