geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 298 メモ

ABC 期待値DP Segment Tree

コンテストページ: TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298) - AtCoder
コンテスト中AC: A〜F

E - Unfair Sugoroku
F - Rook Score

E - Unfair Sugoroku

期待値や確率の問題はメモ化再帰で解ける場合が多いです。

状態遷移を考えた時、

遷移する確率×遷移先で得られた確率

の総和により答えを計算できます。具体的には、

$f(a,b,t):=$ 高橋くんがマス $a$ 、青木くんがマス $b$ で、手番の状態が $t$ の時に高橋くんが勝つ確率
但し、 $t\in \{0,1\}$ であり、 $t=1$ のときは高橋くんの手番、 $t=0$ のときは青木くんの手番とします。

$f(a,b,t)$ からは以下のように遷移します。

$t=1$ の時
$f(a+1,\ b,\ 0),\ f(a+2,\ b,\ 0),\ \cdots ,\ f(a+P,\ b,\ 0)$
$t=0$ の時
$f(a,\ b+1,\ 1),\ f(a,\ b+2,\ 1),\ \cdots ,\ f(a,\ b+Q,\ 1)$

今回遷移する確率は等確率なので、

$t=1$ の時
$f(a,\ b,\ t)=\frac{1}{P}f(a+1,\ b,\ 0)+\frac{1}{P}f(a+2,\ b,\ 0)+\cdots +\frac{1}{P}f(a+P,\ b,\ 0)$
$t=0$ の時
$f(a,b,t)=\frac{1}{Q}f(a,\ b+1,\ 1)+\frac{1}{Q}f(a,\ b+2,\ 1)+\cdots +\frac{1}{Q}f(a,\ b+Q,\ 1)$

です。
再帰の終了条件は、 $a\geq N$ なら高橋くんの勝ちなので $f(a,b,t)=1$ 、 $b\geq N$ なら青木くんの勝ちなので $f(a,b,t)=0$ です。

後は、メモ化再帰して、 $f(A,\ B,\ 1)$ を解けばよいです。

計算量は、ワーストケースで状態数が $200^2$ で、各状態につき遷移に $10$ かかるので、 $4\times 10^5$ であり問題ありません。

実装: Submission #40661914 - TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298)

F - Rook Score

行のスコアの最大値+列のスコアの最大値を答えとできれば単純ですが、このようにはいきません。なぜなら、行 $r$ と列 $c$ を選んだ時、マス $(r,c)$ の整数が2回足されるため、この整数を引かなければいけないためです。

計算量的に選ぶ行を全探索することは可能です。後は、行を固定したときの列のスコアの最大値が高速にわかれば解くことができます。

やや大雑把ですが、例とともに解法を説明します。行 $r$ を選んだとします。
列 $i$ の整数の和が $s_i$ であるような数列を $s$ とします。また、 $r$ 行には列 $1,3,10$ に整数 $x_1,x_2,x_3$ が書かれていたとします。
今求めたいのは、元の $s$ から同じ行の整数を引いた

$max(s_1 - x_1,\ s_2,\ s_3-x_2,\ \cdots ,\ s_{10}-x_3,\ \cdots ,\ s_{10^9})$

です。
列の座標圧縮をします。仮に、

$\{1,2,3,...,10,...,10^9\}\rightarrow \{1,2,3,...,6,...,m\}$

と変換されたとします。求めたいものは、

$max(s_1 - x_1,\ s_2,\ s_3-x_2,\ \cdots ,\ s_{6}-x_3,\ \cdots ,\ s_{m})$

となります。
座標圧縮後の $m$ は $N$ 以下なので、配列として保持できるサイズとなります。そのため、Segment Treeにより、区間最大のクエリに答えることで最大値を得ることが可能です。

後は、同じ行に存在する整数を引く部分ですが、これは各行毎に以下のように処理します。

同じ行の整数を $s$ から引く
最大値を得る
同じ行の整数を $s$ に足し、元に戻す

各整数につき、引く・足すが1回ずつしか行われないので、Segment Treeの値更新を考えても $O(NlogN)$ で処理できます。

実装: Submission #40675301 - TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298)