日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）D,E,F問題メモ

日本最強プログラマー学生選手権～Advance～ -予選- （AtCoder Beginner Contest 412）

D - Make 2-Regular Graph

• $N$ 頂点 $M$ 辺の単純無向グラフ $G$ があります。頂点には $1, 2, \ldots, N$ の番号が付けられており、$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結ぶ無向辺です。
• あなたは、以下の $2$ つの操作を好きな順序で好きな回数繰り返すことができます。
  • $G$ に無向辺を $1$ つ追加する
  • $G$ から無向辺を $1$ つ削除する

• $G$ をすべての頂点の次数が $2$ である単純無向グラフにするために行う操作回数として考えられる最小値を求めてください。

• $3 \leq N \leq 8$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• 入力で与えられるグラフ $G$ は単純無向グラフ
• 入力される値はすべて整数

意外と時間かかった。
次数が全て2ということを上手く使うには少し知識が要る。

次数が全て2のグラフは、置換グラフ（を無向辺にしたもの）に限られる。

• 置換グラフ:
  • 順列 $P$ に対し、$i→P_i$ に辺を張った有向グラフ
  • 全ての連結成分はサイクルとなる

$N$ が小さく $8!=40320$ 程度なので、 全ての順列について、それから生成される置換グラフになるように辺を追加したり削除したりすると 操作回数はいくつになるか、を実際に試せる。

• 全ての既存の辺を削除してから、置換グラフの辺を追加すると $N+M$ 回の操作が必要
• 置換グラフの辺が初めから存在していたら、そこから削除+追加の2回を節約できる

と考えると、1回の順列の試行は $O(N)$、全体 $O(N!)$ となる。

ただし、$P[P[i]]=i$ となるような $i$ が存在する順列は、単純グラフにならないので除外する必要がある。

Python3

E - LCM Sequence

• 正整数 $n$ について $A_n$ を $1, 2, \dots, n$ の最小公倍数として定義します。
• 正整数 $L, R$ が与えられます。数列 $(A_L, A_{L+1}, \dots, A_R)$ の中には何種類の整数が含まれますか？

• $1 \leq L \leq R \leq 10^{14}$
• $R - L \leq 10^7$
• $L, R$ は整数

区間篩、難しいわけじゃないし制約も特徴的なのに、出されるといっつも忘れてるね。
（ミラーラビンでごにょごにょしようとしていた）

2数 $a,b$ が素因数分解して $a=p^{x1}q^{y1}r^{z1}$、$b=p^{x2}q^{y2}r^{z2}$ となるとき、 $\mathrm{LCM}(a,b)=p^{\max(x1,x2)}q^{\max(y1,y2)}r^{\max(z1,z2)}$ である。
素因数ごとに、肩に乗っている指数の最大値が使われる。

これを踏まえると、$n$ が $A_n$ を更新するのは、 「$n$ の素因数分解の結果に、$n$ 未満のどの整数よりも指数の大きな素数がある」場合に限られる。

言い換えると、「ある単一の素数 $p$ と1以上の整数 $x$ を使って、$p^x$ と表せる数」に限られる。

$x=1$ と $x \ge 2$ で場合分けする。

$x=1$ の時は、つまり素数である。
区間篩で素数を $O((\sqrt{R}+D)\log\log{R})$ で列挙できる。（$D=R-L$ とする）

$x=2$ の時は、$p \le \sqrt{R}$ である。
$\sqrt{R}$ 以下の素数を列挙し、$x$ を $R$ を超えるまで1ずつ増やし、$L \le p^x \le R$ のものを記録しておけばよい。
$P_R$ を $\sqrt{R}$ 以下の素数の個数とし、$O(\sqrt{R}+P_R \log{R})$ で求められる。

あとは、$L+1～R$ の中にある“$A_n$ を更新する値”の個数+1が答えとなる。
（$L$ は、$A_n$ を更新する値かどうかに関わらず必ず1種類に数えられる点に注意）

Python3

F - Socks 4

• 高橋君のタンスの中には $N$ 色の靴下があり、色 $i$ の靴下は $A_i$ 枚あります。
• 高橋君ははじめこれらの靴下とは別に色 $C$ の靴下を $1$ 枚タンスの外に持っており、操作を終える条件を満たすまで以下の操作を繰り返します。
  • タンスから靴下を $1$ 枚一様ランダムに選んで取り出す。
  • その後、タンスの外に持っている $2$ 枚の靴下が同じ色ならば操作を終える。
  • そうでないならば、片方の靴下を選んでタンスに戻す。
    • ただし、高橋君は常に今後の靴下を取り出す回数の期待値が最小となるようにタンスに戻す靴下を選ぶ。

• 操作を終えるまでに靴下を取り出す回数の期待値を $\bmod\ 998244353$ で求めてください。

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq C \leq N$
• $1 \leq A_i \leq 3000$
• 入力される値はすべて整数

$S = \sum_i{A_i}$（タンスの中の靴下の数）とする。

また、これ以降、$A_C+=1$ とし、$A$ はタンスの外を含め全体の靴下の枚数を示すとする。

ある操作で取り出した靴下の色が違うなら、 期待値の上では枚数が多い方を残すのが明らかによい。
同率の場合はどちらでも変わらないが、適当に全ての大小関係をつけておく。

$A_i$ を降順に並べ替える。（$C$ も、並べ替えた後の対応する index に変化するとする）

その上で、以下に示す $E_1,E_2,...,E_C$ を順に求めていける。

• $T_i:=$ 色 $i$ の靴下を持った状態
• $E_i:=$ 色 $i$ の靴下を持った状態からの残り回数期待値

• $j \lt i$ なる $j$ に対しては、確率 $\frac{A_j}{S}$ で $T_j$ に遷移する。
• 色 $i$ を確率 $\frac{A_i-1}{S}$ で引くと、終了する。
• $i \lt j$ なる $j$ に対しては、引き続き $T_i$ のままとなる。

• $\displaystyle E_i = \sum_{j \lt i}{\frac{A_j}{S}E_j} + \frac{A_i-1}{S} \times 0 + \frac{その他の個数}{S}E_i +1$

i   1  2  3  4  5  6  ...
E   *  *  *<-*
    ^  ^-----|
     `-------'
     
   ~~~~~~~~~                ... Σ(jへの遷移確率 × Ej)
               ~~~~~~~      ... i=4以降の靴下を引く確率 × Ei

$E_i$ が右辺にも左辺にも登場するので、適宜式変形して解く。

• 現在の $j \lt i$ なる $j$ に対する $\frac{A_j}{S} \times E_j$ の総和
• 現在の $j \lt i$ なる $j$ に対する $A_j$ の累積金額

あたりを更新しながら $i$ を進めていくと、1回当たり $O(1)$ または $O(\log{mod})$ の計算量で解ける。

Python3