ABC 401-500/ABC412F - Socks 4 - 競技プログラミング用 知識集積所

---

問題

ABC412F

必要知識

B以下レベルの内容は省略

• 剰余類環
• 期待値（未作成）
• 動的計画法

考え方

5 1
1 2 3 4 2

という入力を考えてみる。

靴下の持ち替えは、なるべく枚数が多いものを残すことになるのは明らか。
そこで、色4＞色3＞色1＞色2＞色5という優先順位で考えることにしてよい。
（色1は、手元に1枚あるので合計2枚である点に注意）

優先度が高いものから順に、期待値を求めてみる。

まず、色4を持っている場合の期待値。
箪笥には12枚の靴下があって色4は3枚、他の9枚を取り出したら色4を残す。
この場合、確率3/12で手順が終わり、確率9/12で元の状態に戻る。
よって、

E = 1 + ( 9/12*E )

となって、これを解いて

3/12 * E = 1

つまり

E = 12/3 * 1 = 4

となる。

次に、色3を持っている場合の期待値。
箪笥には12枚の靴下があって色3は2枚、色4を取り出したら色4を残し、他の6枚を取り出したら色3を残す。
この場合、確率2/12で手順が終わり、確率4/12で色4に変わり、確率6/12で元の状態に戻る。
よって、

E = 1 + ( 4/12*4 + 6/12*E )

となって、これを解いて

6/12 * E = 1 + 4/12*4

つまり

E = 12/6 * ( 1 + 4/12*4 ) = 14/3

となる。

次に、色1を持っている場合の期待値。
箪笥には12枚の靴下があって色1は1枚、色4を取り出したら色4を残し、色3を取り出したら色3を残し、他の4枚を取り出したら色3を残す。
この場合、確率1/12で手順が終わり、確率4/12で色4に変わり、確率3/12で色3に変わり、確率4/12で元の状態に戻る。
よって、

E = 1 + ( 4/12*4 + 3/12*14/3 + 4/12*E )

となって、これを解いて

8/12 * E = 1 + 4/12*4 + 3/12*14/3

つまり

E = 12/8 * ( 1 + 4/12*4 + 3/12*14/3 ) = 21/4

となる。

Eを求める式だけ抜き出すと、

E = 12/3 * 1 = 4
E = 12/6 * ( 1 + 4/12*4 ) = 14/3
E = 12/8 * ( 1 + 4/12*4 + 3/12*14/3 ) = 21/4

となっているので、実は

• 前にかける分数の分母
• 括弧内の項が1つずつ増えていく

の2ヶ所しか変化がないことがわかる。
よって、動的計画法で優先度が高い靴下から順に期待値を求めていくことが可能である。

答えは998244353で割った余りを要求されているので、剰余類換（未作成）の考えに従って処理する。
また、分数を規約分数にする必要はない。
分母が998244353の倍数になることはないので、そこのケアは不要。

ちなみに、上の例で残り2つの靴下もやると、

E = 12/10 * ( 1 + 4/12*4 + 3/12*14/3 * 2/12*21/4 ) = 21/4
E = 12/12 * ( 1 + 4/12*4 + 3/12*14/3 * 2/12*21/4 * 2/12*21/4 ) = 21/4

となるので、色1、色4、色5の優先度がどんな順番であっても期待値は同じ値が出る。

解答例

解答例

注意点

別解