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

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

補集合を考える

全国統一プログラミング王決定戦 本選 E - Erasure (700 点)

700 点は絶対落とさないのん!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間がある。 これ…

AtCoder ABC 117 C - Streamline (茶色, 300 点)

ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…

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

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

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 (二部グラフ判定からの部分和ナップサックが酷…