AtCoder Beginner Contest 352 F,G問題メモ

F - Estimate Order

問題

  • $N$ 人の人が競争して、$1~N$ の順位が付いた(同率無し)
  • 以下のような $M$ 個の条件が与えられる
    • ($A_i$ の人の順位)-($B_i$ の人の順位)=$C_i$ である
    • 矛盾するような条件は与えられない
  • 人 $1,...,N$ について、「与えられた条件だけで順位が一意に定まる」場合はその順位を、定まらない場合は '-1' を答えよ
  • $2 \le N \le 16$

解法

やること自体は手計算でも十分にパズルとして解けるような内容だが、実装にちょっと迷走してしまった。

与えられた条件をグラフのように結ぶと、連結成分ごとに1つの「パズルのピース」ができる。

Ai  Bi  Ci
 1   2   3        ①・・②・④・③  条件により結びついた人達の間で、
 2   3   4    →  |--3--||---4---|  この位置関係は変わらない
 1   4   5        |----5----|

              →  1 0 0 1 0 1 0 1   bitフラグで表しておく
              
他の連結成分からも、  1  や  101  などのピースができる

で、各人の順位を求めるのは、長さ $N$ の 0000…00 という“枠”にこれらのピースを、1 が重ならないように全て当てはめるという操作になる。
制約上、必ず1通りは正しい当てはめ方がある。

一意に決まるかどうかは、以下のように確かめる。

0000000000  長さNの枠

10010101    ピースAの1つを試しに置く

 1    1001  残りのピースの置き方を全探索し、
  101   1   残りを全て埋める方法があるか?をチェック
            →埋められた(1つ見つかれば、即終了してよい)

 10010101   ピースAの位置をずらして、
  10010101  他の場合も、残りを全て埋められるかチェック

で、「残りを全て埋められるピースAの初期位置」が1箇所だけだったら、ピースAに属する人の順位は全て決まる。

2箇所以上「残りを全て埋められる、ピースAの初期位置」があったら定まらない。

$N$ が小さいので、全てのピースについて、この全探索を実行しても間に合う。

Python3

G - Socks 3

問題

  • タンスに靴下がいっぱい入っている。種類 $i$ の靴下は $A_i$ 枚入っている
  • 今日はく靴下を取り出すために、以下の操作を行う
    • ランダムに等確率で靴下を1枚取り出すことを繰り返す(一度取り出した靴下は戻さない)
    • 同じ種類の靴下が2枚取り出された時点で、取り出すのをやめる
  • 靴下を取り出す回数の期待値を求めよ
  • $1 \le N \le 3 \times 10^5$
  • $2 \le A_i \le 3000$

解法

このように操作回数の期待値を求める問題において、「ちょうど」の期待値は、「○○回以上」の確率の和に置き換えられる。

主客転倒の一種。

ゲームの確率遷移の例(この問題とは関係ない)

        1回      2回     3回 ...
1  →  1/4 --→ 1/8[終]
 |        `--→ 1/8[終]
 |-→  1/2 --→ 1/3 --→ 1/6[終]
 |        |       `---→ 1/6[終]
 |        `--→ 1/6[終]
 `-→  1/4[終]
 
 操作回数の期待値 = [終]のノードが表す回数 × そのノードに至る確率 の総和
   1*1/4 + 2*(1/8+1/8+1/6) + 3*(1/6+1/6)
 
 これは、[終]に限らない、全てのノードの確率の合計と一致する
   1/4 + 1/8 + 1/8 + 1/2 + 1/3 + 1/6 + 1/6 + 1/6 + 1/4

元の問題に戻る。

$A_i$ の総和を $S$ とする。

たとえば「3枚」取り出してもまだ揃っていない場合というのは、全て別々の種類から取り出すということなので、

  • 取り出す靴下の種類と順序を固定 (例)$A_1→A_4→A_3$
  • 1回目、$\dfrac{A_1}{S}$
  • 2回目、$\dfrac{A_4}{S-1}$
  • 3回目、$\dfrac{A_3}{S-2}$
  • → $\dfrac{A_1A_4A_3}{S(S-1)(S-2)}$

というのを、全ての靴下の種類・順序について足し合わせたものとなる。

これは形式的冪級数を用いて

  • $F(x)=(1+A_1x)(1+A_2x)(1+A_3x)...(1+A_Nx)$

とすると、$x^3$ の係数が、相異なる全ての組 $(i,j,k)$ についての $A_iA_jA_k$ を足し合わせたものとなる。
(同様に、$x^p$ の係数が、全ての $p$ 個組についての $A_iA_jA_k...$ を足し合わせたものとなる)

順序を考慮するための階乗をかけて、以下を足し合わせたものが、操作が終わっていない状態全ての確率の和となる。

  • $\dfrac{[x]F(x) \times 1!}{S}$
  • $\dfrac{[x^2]F(x) \times 2!}{S(S-1)}$
  • $\dfrac{[x^3]F(x) \times 3!}{S(S-1)(S-2)}$
  • $\dfrac{[x^N]F(x) \times N!}{S(S-1)(S-2)...(S-N+1)}$

最後に、操作終了のための1枚を加えて、答えとなる。

$F(x)$ を求める際はFFTを用いるが、二分木の要領で、隣り合う要素同士を順次マージして なるべく長い配列を何度もマージしないように工夫すると、全体を $O(N \log^2{N})$ で求められる。

Python3

programming_algorithm/contest_history/atcoder/2024/0502_abc352.txt · 最終更新: 2024/06/03 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0