Codeforces Round #557 (Div. 1) D. Palindrome XOR (R2400)

面白かった。重み付き Union-Find を使った。問題へのリンク問題概要 0 と 1 と ? のみからなる長さの文字列が与えられる。先頭の文字が 1 であることが保証されている。以下の条件を満たす整数の組 () の個数を求めよ。はともに回文数である (11 や 1…

Codeforces Round #616 (Div. 1) C. Prefix Enlightenment (R2400)

Union-Find を使いこなす！！！問題へのリンク問題概要 (意訳) 個の 0-1 変数が与えられていて、最初はそれらの値について特に制約はない。いま、個の制約が順に与えられる。各制約はそれぞれ 1 つの変数と 0 か 1 の値 w を指定して、とする 2 つの変…

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

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