脳log[20210716]

2021年07月16日 (金) [AtCoder]「083 - Colorful Graph（★6）」で苦しめられた(20210704p01)ケースが random_clique という名前だった。「045 - Simple Grouping（★6）」でべらぼうに速い tinsep19 さんの提出 #22975499 で気になる MinCliqueCover というクラス名。clique ってグラフ用語だった！ 「Clique (graph theory)」■tinsep19 さんの解答のアイデアは、距離がある長さ以下の点間に辺を張ったグラフを考えるとき、K 以下の Clique で全頂点をカバーできる最短の長さを効率的に求めるものだと思う。でも cover? メソッドの @sign と k 乗がまだ全然わからない。もうちょっと考える。■今思えば自分は最初にこの問題を考えたとき、UnionFind を使ってクリークの数が K 以下になる辺の長さを見つけようとしていた。クリークという概念も知らないまま。でも UnionFind でわかるのは連結成分なのであって、連結成分をクリークに分解できないとクリークの数は数えられないんだよね。連結成分を構成する頂点の数と辺の数を見比べて何か見えたりしないか、とか考えてた。