3匹の猫

みみねこの競プロ精進メモ

AtCoder Regular Contest 114参加記(~B問題)

早解きの巻

f:id:mmnkblog:20210315012932p:plain

A - Not coprime

互いに素でないということは、X_iYに共通の素因数が存在するということと同値である。制約より、Yは最大でも50以下の素数の積(およそ6.1\times 10^{17})にしかならない。さらに、50以下の素数それぞれに対して「Yに含めるか」「含めないか」の2択を選ぶbit全探索をして全通り試してもも実行時間制限にも十分間に合う。
ちなみに50以下の素数15個。素数リストを実行時に生成してもよかったが、ライブラリを引っ張り出してくるより暗記しているものを書き出したほうが早かった。

計算量は、O(N \pi(\max(X)) 2^{\pi(\max(X))})

B - Special Subsets

全射の整数集合が与えられていて、その部分集合のうち全単射であるものはいくつあるか?という問題。(たぶん)
この集合と関数の関係は、a\to f(a)へと有向辺を生やしたグラフと等価である。このグラフは、頂点数と辺数がそれぞれNで等しい。
また、関数が全単射であるとき、有向グラフはいくつかの重複しない閉路のみからなるグラフとなる(必ずしも連結とは限らない)。
つまり元のグラフのなかに閉路がいくつ存在するかがわかればよい。これは単純にDFSで閉路判定をすればよいし、「頂点数と辺数が等しいグラフの閉路の数は、連結成分の数に等しい」という定理をもちいてUnionFindなどを用いて連結成分の数を持つだけでも良い。
閉路の数をCとすれば、答えは2^C - 1である。

計算量は、O(N)

感想

Cは解けなかった。サンプルが合わなかった。
D問題をみて「貪欲かな~」と思ったけど、順位表を見るとD-EのAC数が逆転していたのでC問題をずっとにらんでいた。貪欲は嘘解法らしく一安心。

個人的に早解きで暖まるのは申し訳ない気持ちになる。