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

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

後退解析

JOI 本選 2007 D - 最悪の記者 (AOJ 0519, 難易度 7)

トポロジカルソートせよ、という問題! 問題へのリンク 問題概要 頂点数 、辺数 の DAG (閉路のない単純有向グラフ) が与えられる。 このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。 制約 考えたこと …

JOI 二次予選 2021 E - スパイ 2 (難易度 10)

面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…

Codeforces Round #684 (Div. 1) B. Graph Subset Problem (R2600)

TLE が厳しくて話題になってた 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ [tex G] が与えられる。また、正の整数 が与えられる。 以下のいずれかの条件を満たすものが存在するかどうかを判定し、存在するならばそれを出力せよ。 type 1: の…

Codeforces Round #681 (Div. 1) E. Black, White and Grey Tree (R3000)

最初まんまと罠にひっかかった 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には 0, 1, 2 のいずれかの色 (0: 灰色, 1: 白色, 2: 黒色) が割り振られている。以下の操作を最小回数行うことで、木を消滅させたい。最小回数を求めよ。 [操作]:残…

AtCoder ARC 097 F - Monochrome Cat (赤色, 800 点)

とにかく重たい... 問題へのリンク 問題概要 頂点のツリーが与えられる。各頂点には「白」か「黒」の色が塗られている。好きな頂点から開始して 今いる頂点の色を flip する 隣接する頂点を 1 つ選んで移動して、その頂点の色を flip する といういずれかの…

Codeforces Round #586 (Div.1 + Div.2) E. Tourism (R2200)

結構好き...だけど、完全既出だったらしい 問題へのリンク 問題概要 頂点 辺の連結な単純無向グラフが与えられる。各頂点 には重み が付いている。頂点 を始点としたウォークであって、ウォーク上のどの辺 に対してもその直後が ではない (直前に通った辺を…

AtCoder AGC 014 D - Black and White Tree (黄色, 900 点)

最高に好きな問題 問題へのリンク 問題概要 頂点数 のツリー上でゲームを行う。高橋君は残った頂点から 1 つ選んで白く塗る。青木君は残った頂点から 1 つ選んで黒く塗る。 この操作をすべての頂点に色が塗られるまで繰り返したとき、黒く塗られたすべての頂…

MUJIN 2018 D - うほょじご (400 点)

いかにもよくわからない操作問題なので、難しいことは考えずに探索に走るべきな雰囲気 atcoder.jp 問題概要 正の整数 に対し、 で を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表す。 正の整数 が与えられる。 なる整数の組 であっ…

AtCoder ARC 038 D - 有向グラフと数 (試験管赤色)

後退解析を用いる問題。queue に不慣れなので、急に queue を使えるように。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えられる。各頂点 には値 X_v が割り振られている。先手と後手とで以下の対戦を行う スタート時には駒を頂点 1 に置く 各プレイ…

AOJ 2891 な◯りカット (AUPC 2018 day3 C)

サイクルが 1 個だけある連結グラフ、すなわち「木」に辺を 1 個くわえてできるグラフのことを、なもりグラフと呼ぶことにする。 問題へのリンク 問題概要 N 頂点のなもりグラフが与えられる。以下の Q 個のクエリに答えよ。 2 頂点 a, b の間を分断するのに…

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) E. Trips (R2100)

こういうの苦手。。。 問題へのリンク 問題概要 整数 k と、N 頂点 0 辺のグラフが最初に与えられる。以下の M 個のクエリに答えよ。 a, b: 辺 (a, b) を追加する。この時点でグラフの各頂点を以下の条件を満たすように白黒に塗る「任意の黒い頂点は、隣接す…