ABC210 F - Coprime Solitaire
きちんとした解法や証明は公式解説で。ここでは主に計算量削減パートをメモ。多分、解説動画でsnukeさんが最初にACした方針。
・解法の大まかな流れ
① すべてのカードの表と裏を頂点としたグラフを考える(つまり頂点数がカード枚数の2倍になる)
② 「頂点uを使ったら頂点vも使わなくてはならない」という関係を有向辺u→vで表す
③ 強連結成分分解(SCC)をして、同一成分内に同じカードの表と裏が含まれていなければ"Yes"、含まれていれば"No"
ここで問題となるのが②。問題の条件より
頂点のうち、使えるのは1つ
という状況が生まれる。頂点の反対の面を頂点とする。このとき、例えば頂点からの辺は次のようになる。
頂点を使う場合、頂点は使えない。よって、頂点の反対の面を使うしかなくなる。すると、上の図のような辺になる。
これを残りの頂点からもやるのだが、この通りすべてやると
辺の本数がとなってTLE
してしまう。ここからが本題。では、どのように辺を張ればよいか。
まずは次のような準備をする。以下のように、反対の面の頂点1つにつき2つの頂点を増やす。
そして、右向き用の辺(赤)と左向き用の辺(青)を張る。
これで準備完了。先程の頂点cからの辺は以下のような2本で済む。
どの頂点からも2本か1本の辺で済むので
辺の本数がで抑えられる
(※1つの頂点が素因数ごとに何度か登場するので厳密にはではないと思うが、それはブログタイトル下のコメント通り。)見ての通り頂点と辺が結構増えるので、定数倍が重い気がするが、元々が小さめであるし、1秒ちょっとで通ったので気にしない。
提出コード:Submission #24389859 - AtCoder Beginner Contest 210