問題

問題概要

$n$ 頂点 $m$ 辺の無向グラフが与えられる。この各辺について、どちらかに向きを付けなければならない。その時に各頂点からの出次数の最大値が最小になるような割り当て方を答えよ。

$1 \le n \le 5000$
$0 \le m \le min(5000, n(n-1)/2)$
多重辺や自己ループはない

アイデア

各辺について、端点のどちらかに+1をする時に、頂点の持つ値の最大値を最小化するというように見ることが出来る。答えを二分探索することを考える。各頂点は $x$ までは増やすことを許すとする。この $x$ が妥当かどうかをフローを使って解く。フローを考えるグラフは次のように構築する：

$source$ から、 $edge_i$ へ容量1
$edge_i (= (x_i, y_i))$ から、 $V_{x_i}$ と $V_{y_i}$ へそれぞれ容量1
$V_i$ から、 $sink$ へ容量 $x$

このようなグラフを構築し、最大フローを求める。その値が $m$ に一致すればOKとなる。このフローは、Dinicを使えば高速に動作する( $|V| = O(n), |E| = O(n)$ のとき、Karzanov's theoremにより、Dinicは $O(n \sqrt{n})$ で動作するらしい(?)。この辺は理解しきれてない)。

復元は、残余グラフを見れば簡単にできる。

実装(C++)

問題

Contest Page | CodeChef

問題概要

長さ $n$ の数列 $a$ が与えられる。xy平面を考えて、数列に対して $i(1 \le n \le n)$ 番目の要素について、 $(i,0)$ と $(i,a_i )$ を端点とする線分を引く。以下の2種類のクエリが合計で $Q$ 個与えられるのでそれを処理せよ：

+ i X : $a_i += X$
? i L R : x軸に平行な光が、 $R-L+1$ 個発射されると想定する。 $j(1 \le j \le R-L+1)$ 番目の光は、座標 $(i-0.5 , L+j-1.5)$ からx軸正の方向に向けて発射されるが、一度線分にぶつかると光は遮断される。このとき、光が当たっている線分の個数を答える。

2つ目のクエリについては、光はクエリごとに独立で考える → 毎回このクエリごとに光源を設置して、このクエリに答えたらその光源はなくなる。

$1 \le n \le 10^6$
$1 \le a_i \le 10^9$
$1 \le Q \le 10^5$
$0 \le X \le 10000$
$1 \le L \le R \le 10^9$

アイデア

まず、2つ目の幾何的なクエリは分かりにくいので、幾何的な要素を除外する：

$i \le j$ である $j$ について、高さ $k-0.5 (L \le k \le R)$ の光が当たるということは、 $a_j \ge k$ であり、 $i \le l \lt j$ について、 $a_l \lt a_j$ である必要がある。このことから、光が $j$ 番目の線分にあたるための線分の条件は、

$a_j \ge L$ (これ以上無いとそもそも光が当たらない)
$a_l \lt a_j (i \le l \lt j)$
$max(a_l) \lt R (i \le l \lt j)$ (これがないと $j$ 番目の線分に光が届かない)

なので、これを満たすような $j (i \le j)$ の個数を数える、ということになる。

3番目の条件は $R \le a_h$ を満たす最小の $h (i \le h)$ を見つけ、 $h\lt j$ の部分については考えないということにすれば良いので、 $i \le j \le h$ について考えることで、3番目の条件を除外できる。 $h$ を見つけることを考えると、maxを取るsegment tree上を二分探索することで $O(logn)$ で求めることが出来る。

以下、1,2の条件のみを考える。 $R$ はもう関係ないので、今segment tree上で $[l , r)$ にパラメータ $L$ という3つ組のクエリに答えることを考えよう。この区間に対して、 $L = -1$ というパラメータが与えられた場合の答えを $x$ として持っているとする。

区間の要素が1つだけならこのクエリに対する答えは自明で、 $L$ 以上なら1になる。

区間の要素が2つ以上ならば、2つの区間に分けて再帰的に解いていくことになる。左側、右側のそれぞれのノードに対する答えを $x_{left} , x_{right}$ とする。左側の子ノードの区間に対して、その区間の最大値で以下のように場合分け出来る：

最大値が $L$ 未満の場合: 左側の子ノードの区間で光が当たる線分は自明に0本なので、右側の区間にのみ再帰を伸ばしていけばよい。
最大値が $L$ 以上の場合: 左側の子ノードの区間で光が当たる線分は1本以上あるので、左側の区間に再帰を伸ばす。その時に、右側を考えると、パラメータ $L$ に依存せず答えが一定になることがわかる(左側に $L$ 以上の値があれば、そちらがよりstrictな条件になるから)。そして、それは $x - x_l$ で得られる( $x_r$ ではないことに注意)。

つまり、どちらの場合にせよ伸ばす再帰の方向はどちらか1つなので、この再帰はsegment tree上で $O(logn)$ でクエリに答えることが出来る。実際のクエリでは、これが、 $O(logn)$ 個の頂点で発生するので、 $O((logn)^2)$ で処理できる。

また、更新クエリに関しては点更新なので、事前計算で持っておくべき値 $x$ について、計算し直す必要のあるノードが $O(logn)$ 個あるので、 $O((logn)^2)$ で処理できる。

実装(C++)

裏紙

ほぼ競プロ、たまに日記

CF 847 J - Students Initiation

問題

問題概要

アイデア

実装(C++)

Codechef October Challenge 2017 - Shooting on the array

問題

問題概要

アイデア

実装(C++)