けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

補グラフ

AtCoder AGC 032 B - Balanced Neighbors (700 点)

三角形、四角形、、、と順に作って行って、五角形の場合を作るのに苦労した!!! 問題へのリンク 問題概要 頂点番号が な単純無向であって、以下の条件を満たすものを 1 つ構築せよ: どの頂点についても、その頂点に隣接している頂点の番号の和が等しい 制…

AOJ 1393 Eulerian Flight Tour (ICPC アジア 2018 E)

面白い!!!!!!! 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる (連結とは限らない)。 このグラフに何本かの辺を付け加えることで「連結なオイラーグラフ」にすることができるかどうかを判定し、できるならば一例を示せ。ただし多重辺…

POJ 3692 Kindergarten (ARC 099 E の類題として)

ARC 099 E - Independence の類題という感じなん。具体的には「補グラフをとって二部グラフを考えて...」みたいなところのが似てるん。 POJ 3692 Kindergarten 問題概要 G 人の女の子と、B 人の男の子がいて、「女の子同士」「男の子同士」はすべて互いに知…

AtCoder ARC 099 E - Independence (700 点)

いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たいのん。こういうのを素早く通せるようになりたいん。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷…