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

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

差分制約系

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

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

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

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

AtCoder ABC 126 E - 1 or 2 (水色, 500 点)

これまた Union-Find を用いる教育的問題!!!!! 問題へのリンク 問題概要 枚のカードがあって、それぞれ 1 か 2 の数値が書かれている。 枚のカードの数値 をすべて当てたい。 現在、以下の形式をした条件が 個与えらている: 整数 に対して、 は偶数であ…

AOJ 2427 ほそながいところ

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

TopCoder SRM 694 D1H SRMDiv0Easy

二段階単体法のデバッグに苦労しました。 問題概要 初期状態が全要素が 0 であるような N 次元ベクトルに対し、 以下のような Q 個の区間クエリを実施して得られる結果が 全要素が等しい N 次元ベクトルとなるようにしたい。区間クエリ i: 閉区間 [ L[i], R[…