競プロ解法メモ

自分用のメモが主目的なので厳密性は求めないでください

ABC210 F - Coprime Solitaire

問題:F - Coprime Solitaire

きちんとした解法や証明は公式解説で。ここでは主に計算量削減パートをメモ。多分、解説動画でsnukeさんが最初にACした方針。

 ・解法の大まかな流れ

① すべてのカードの表と裏を頂点としたグラフを考える(つまり頂点数がカード枚数の2倍になる)

② 「頂点uを使ったら頂点vも使わなくてはならない」という関係を有向辺u→vで表す

③ 強連結成分分解(SCC)をして、同一成分内に同じカードの表と裏が含まれていなければ"Yes"、含まれていれば"No"

ここで問題となるのが②。問題の条件より

頂点a,b,c,d,e,fのうち、使えるのは1つ

 という状況が生まれる。頂点aの反対の面を頂点\overline{a}とする。このとき、例えば頂点cからの辺は次のようになる。

f:id:mkawa2:20210720130415j:plain

頂点cを使う場合、頂点a,b,d,e,fは使えない。よって、頂点a,b,d,e,fの反対の面を使うしかなくなる。すると、上の図のような辺になる。

これを残りの頂点a,b,d,e,fからもやるのだが、この通りすべてやると

辺の本数がO\left( N^{2}\right)となってTLE

してしまう。ここからが本題。では、どのように辺を張ればよいか。

まずは次のような準備をする。以下のように、反対の面の頂点1つにつき2つの頂点を増やす。 

f:id:mkawa2:20210720130422j:plain

そして、右向き用の辺(赤)と左向き用の辺(青)を張る。

f:id:mkawa2:20210720130425j:plain

これで準備完了。先程の頂点cからの辺は以下のような2本で済む。

f:id:mkawa2:20210720130418j:plain

どの頂点からも2本か1本の辺で済むので

辺の本数がO\left( N\right)で抑えられる

(※1つの頂点が素因数ごとに何度か登場するので厳密にはO\left( N\right)ではないと思うが、それはブログタイトル下のコメント通り。)見ての通り頂点と辺が結構増えるので、定数倍が重い気がするが、元々Nが小さめであるし、1秒ちょっとで通ったので気にしない。

提出コード:Submission #24389859 - AtCoder Beginner Contest 210