Codeforces Global Round 12 E. Capitalism (R2700)

なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ... 問題へのリンク問題概要頂点数、辺数の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。各頂点に 0 以上の整数値を割…

AtCoder ARC 105 C - Camels and Bridge (青色, 500 点)

難しかった問題へのリンク問題概要体重がであるような体のラクダがいる。ラクダを一列に並べる方法のうち、次の条件を満たすものについて、左端のラクダと右端のラクダの距離として考えられる最小値を求めよ。また、そのようにラクダを並べることが不可…

グラフ問題探索問題全探索 Union-Find 重みつきUnion-Find データ構造コーナーケース IP定式化 AOJ 差分制約系 AOJ-ICPC AOJ-ICPC800点 JAG JAG夏合宿牛ゲー max(pi-pj,0) 双対性

「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。ここのページに僕なりの全探索重み付き Union-Find 木を使いながら判定をした解法を記した。