2016-10-28

RCO アルゴリズムイントロダクション輪読会 26. 最大フロー 2

先週のページ

kenkoooo.hatenablog.com
少し被りがあります。

先週のまとめ

$|f \uparrow f'| = |f|+|f'|$
G の任意のフロー f の値は G の任意のカット容量によって上から抑えられる。

定理 26.6 最大フロー最小カットの定理

fはGの最大フローである。
残余ネットワーク Gf は増加可能経路を含まない。
Gのあるカット(S,T)に対して|f|=c(S,T) である。

証明

最大フローであるにも関わらず増加可能経路を持つと仮定すると、 $f_p$ が定まり、|f| より値が大きいGのフローが得られるので矛盾する。

Gf が増加可能経路を持たないとき、Gfにはsからtへの道が存在しない。

$S=\{ v \in V: G_f に s から v への道が存在する \}, T=V-S$ と定義する。

明らかに $s\in S$ であり、 $G_f$ にはsからtへの道が存在しないので $t\not\in S$ である。よって、この分割(S,T)はカットである。

$u\in S$ かつ $v\in T$ かつ $(u,v) \in E$ であるようなu, v を考える。
$f(u,v)\not= c(u,v)$ ならば $(u,v)\in E_f$ であり、 $v\in S$ となり矛盾する。よって $f(u,v)= c(u,v)$ である。

$f(v,u)\not=0$ ならば $c_f(u,v)=f(v,u)$ で $(u,v)\in E_f$ だから $v\in S$ となり矛盾する。よって $f(v,u)=0$

$\begin{eqnarray} f(S,T) &=& \sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in S}\sum_{v\in T}f(v,u) \\ &=& \sum_{u\in S}\sum_{v\in T}c(u,v)-\sum_{u\in S}\sum_{v\in T}0 \\ &=&c(S,T) \end{eqnarray}$

全てのカット(S, T) に対して $|f| \leqq c(S,T)$ である。よって $|f| = c(S,T)$ はfが最大フローであるための十分条件である。

Ford-Fulkersonのアルゴリズム

Ford-Fulkerson(G, s, t)
    for (u, v) in G.E
        (u, v).f = 0
    while 残余ネットワーク G_f に s から t への道 p が存在する
        c_f(p) = min([c_f(u, v) for (u, v) in p])
        for (u, v) in p
            if (u, v) in G.E
                (u, v).f = (u, v).f + c_f(p)
            else
                (v, u).f = (v, u).f - c_f(p)

基本 Ford-Fulkerson の解析

増加可能経路を見つけるための DFS が O(E)
最大フローが f* とすると、ループは最悪で |f*| 回走る。
よって O(E|f*|)

余談

高速な最大フローのアルゴリズムは $O(V^3)$ で動作するが、最大フローの値が十分小さければ Ford-Fulkerson の方が速くなることがある。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2016Day3&pid=F

2 部グラフの最大マッチング問題

プッシュ再ラベルアルゴリズム

今までは頂点にフローを溜め込むことができない条件のみを考えてきた。

頂点 u に流入するフローと頂点 u から流出するフローの合計が等しかった。
$\begin{eqnarray} \sum_{v \in V-\{s\}} f(v,u) - \sum_{v \in V-\{s\}}f(u,v) = 0 \end{eqnarray}$

これを緩和して、流入量が流出量を超えることが出来るものとする。
$\begin{eqnarray} \sum_{v \in V-\{s\}} f(v,u) - \sum_{v \in V-\{s\}}f(u,v) \geq 0 \end{eqnarray}$

このような条件でのフローをプリフローと呼ぶ。

この過剰量を e(u) とする。

$u\in V-\{s\}$ について、
$\begin{eqnarray} e(u) = \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \end{eqnarray}$

$e(u)>0$ となるような頂点 $u \in V-\{s,t\}$ をオーバーフロー頂点と呼ぶ。

高さ関数

$h(s)=|V|, h(t)=0$ であり、残余辺 $(u,v)\in E_f$ について、 $h(u)\leq h(v)+1$ が成り立つような高さ関数 h を考える。

プッシュ操作

以下の条件を満たす残余辺 (u, v) について、u から v にフローをプッシュする。
$\begin{eqnarray} \begin{cases} h(u)=h(v)+1 \\ c_f(u,v)>0 \\ e(u) > 0 \end{cases} \end{eqnarray}$

Push(u, v)
    # 適用条件: u がオーバーフロー頂点で、c_f(u, v) > 0 かつ h(u) = h(v) + 1
    df = min(e(u), c_f(u, v))
    if (u, v) in E
        (u, v).f = (u, v).f + df
    else
        (v, u).f = (v, u).f - df
e(u) -= df
e(v) += df

プッシュ後に $c_f(u,v)=0$ となるようなプッシュを飽和プッシュと呼ぶ。

再ラベル操作

$e(u)>0$ かつ $(u,v) \in E_f$ の全ての v について $h(u) \leq h(v)$ であるとき、u の高さを上げる。

Relabel(u)
    # 適用条件: u がオーバーフロー頂点、かつ、h(u) <= h(v)
    h(u) = 1 + min([h(v) for (u, v) in E_f])

基礎アルゴリズム

Initialize-Preflow(G, s)
    for v in V
        h(v) = 0
        e(v) = 0
    for (u, v) in E
        (u, v).f = 0
    h(s) = |V|
    for v in G[s]
        (s, v).f = c(s, v)
        e(v) = c(s,v)
        e(s) -= c(s, v)

これによって s から出る全ての辺に容量上限までフローを流す。
つまり、s から出る辺は残余グラフに含まれなくなる。
よって全ての残余辺 $(u,v) \in E_f$ について $h(u) \leq h(v)+1$ が成り立つ。
（全ての $u \in V-\{s\}$ について $h(u)=0$ だから）

Generic-Push-Relabel(G)
    Initialize-Preflow(G, s)
    while 適用可能な push か relabel がある
        適用可能な push か relabel を選び、実行する

Push-Relabel の正当性

アルゴリズムが停止したときプリフロー f が最大フローであることと、アルゴリズムが停止することを示す。

補題 26.14

u がオーバーフロー頂点であれば、push か relabel が実行可能である。

証明

u から push が実行可能でない場合、全ての残余辺 $(u, v) \in E_f$ について、 $h(u) < h(v)+1$ である。
このとき、 $h(u) \leq h(v)$ であり、relabel が実行可能である。

補題26.15

Generic-Push-Relabel の実行中、h(u) は減少しない。

証明

h(u) は relabel 以外では変化せず、relabel では適用のたびに必ず 1 以上増える。

補題26.16

Generic-Push-Relabel は h を高さ関数として維持する。

証明

初期状態では h が高さ関数制約を満たしている。

u から出る辺 (u, v) を考える。
Relabel(u) を行った後は $h(u) \leq h(v)+1$ が保証される。

u に入る辺 (w, u) を考える。
Relabel(u) の前に $h(w) \leq h(u) +1$ が成立していたならば、操作後は $h(w) < h(u) +1$ が成立する。

よって Relabel(u) は高さ制約を維持する。

Push(u, v) を実行することを考える。

Push(u, v) によって $f(v, u)$ が減少するとき、 $c_f(v,u)$ が増加する。
これは $E_f$ に (v, u) が加わると考えられる。
このとき $h(u)=h(v)+1$ だから $h(v)=h(u)-1< h(u)+1$ である。
新しい残余辺 (v, u) について $h(v) \leq h(u)+1$ が成り立つ。

Push(u, v) によって $c_f(u,v)$ が減少するとき、 $E_f$ から (u, v) が取り除かれると考える。
このときは、制約が取り除かれるので、再び h は高さ関数である。

補題26.17

f をプリフローとする。このとき残余グラフ $G_f$ には s から t への道はない。

証明

矛盾を導くために $G_f$ における s から t への道 $p = < v_0,v_1,...,v_k >$ が存在すると仮定する。
$v_0=s, v_k=t$ である。
一般性を失うことなく $k<|V|$ と仮定する。

$i=0,1,...,k-1$ に対して $(v_i,v_{i+1}) \in E_f$ である。
$i=0,1,...,k-1$ に対して $h(v_i)\leq h(v_{i+1}) +1$ である。
よって $h(s)\leq h(t)+k$ である。
ここで $h(t)+k=0+k=k$ だから $h(s)\leq k <|V|$ となり、高さ関数制約 $h(s)=|V|$ に矛盾する。

補題26.18

Generic-Push-Relabel を実行して停止したとき、プリフロー f は最大フローである。

証明

Initialize-Preflow 実行後の f はプリフローである。

while ループ内では push と relabel が実行される。
relabel は f に影響しない。
push 実行前に f がプリフローならば、実行後も f はプリフローである。

補題 26.14 より、停止したときは $V-\{s,t\}$ にオーバーフロー頂点は存在しない。
よって $v \in V-\{s,t\}$ について e(v)=0 である。
よって、プリフロー f はフローである。

補題 26.17 より、残余ネットワーク $G_f$ には s から t への道が存在しない。
よってフロー f は最大フローである。

Push-Relabel の解析

補題 26.19

f をプリフローとする。この時、残余ネットワーク $G_f$ の任意のオーバーフロー頂点 u から s への単純道が存在する。

証明

オーバーフロー頂点 x について、 $U=\{v: G_f において xからvへの単純道がある\}$ とする。
s が U に含まれることを示す。

矛盾を導くために $s \not\in U$ を仮定する。
$\overline{U}=V-U$ とする。

$\begin{eqnarray} e(u) = \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \end{eqnarray}$
より、
$\begin{eqnarray} \sum_{u\in U}e(u) &=& \sum_{u\in U}\big( \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \big) \\ &=& \sum_{u\in U}\big( \big( \sum_{v \in U} f(v,u) + \sum_{v \in \overline{U}} f(v,u) \big) - \big( \sum_{v \in U} f(u,v) + \sum_{v \in \overline{U}} f(u,v) \big) \big) \\ &=& \sum_{u\in U}\sum_{v \in U}f(v,u)+ \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)-\sum_{u\in U}\sum_{v \in U}f(u,v)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v)\\ &=& \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v)\\ \end{eqnarray}$

$e(x)>0, x \in U$ かつ、s以外のすべての頂点が非負の過剰を持ち、 $s\not\in U$ だから、 $\sum_{u\in U}e(u)>0$ である。

したがって
$\begin{eqnarray} \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v) > 0 \end{eqnarray}$

フローは非負だから
$\begin{eqnarray} \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u) > 0 \end{eqnarray}$

よって $f(v',u')>0$ となる $u' \in U, v' \in \overline{U}$ が存在する。
よって残余ネットワーク $G_f$ には残余辺 $(u',v')$ が存在する。

よって道 $x\leadsto u' \to v'$ が存在する。これは $v' \in U$ となり矛盾。

補題 26.20

Generic-Push-Relabel 実行中はすべての頂点 u で $h(u) \leq 2|V| -1$ が成り立つ。

系 26.21

relabel の回数は頂点当たり高々 $2|V|-1$ 回である。

補題 26.22

飽和プッシュ回数は $2|V||E|$ 回である。

補題 26.23

非飽和プッシュ回数は $4|V|^2(|V|+|E|)$ 回である。

次回予告

Push-Relabel の解析

フロント移動

練習問題

おまけ

実装落ちてた。
github.com

2016-10-21

RCO アルゴリズムイントロダクション輪読会 26. 最大フロー 1

資料

フローネットワーク

各辺 $(u, v) \in E$ が、容量 $c(u,v) \geqq 0$ を持つ有向グラフである。入り口 s と出口 t が設定されている。

非負の値を取る量 $f(u,v)$ を頂点 u から頂点 v へのフローと呼ぶ。

フローは以下の 2 条件を満たす。

容量制限: 全ての $u,v \in V$ に対して、 $0 \leqq f(u,v) \leqq c(u,v)$ でなければならない。
フロー保存則: 全てのに対して、でなければならない。
- 頂点 u に入ってくるフローと、頂点 u から出ていくフローの量が等しい。

最大フロー問題は s から t への最大の値を持つフローを求める問題である。

逆平行辺

f:id:kenkoooo:20161021042256j:plain

逆平行辺を持つネットワークは簡単に逆平行辺を持たないグラフに構成し直すことが出来るので、議論を簡明にするため逆平行辺を禁止することにする。

複数の入口と出口

f:id:kenkoooo:20161021041928j:plain

複数の入口があっても超入口を作ってそこから各入口に容量無限の辺を張れば、入口 1 つのネットワークとして扱える。出口についても同様。

練習問題

1-1.

フローネットワーク G の辺 (u, v) を分割し、新しい頂点 x を導入して (u, x) と (x, v) に置き換え、c(u, x) = c(x, v) = c(u, v) と定義した G' を考える。G' の最大フローが G の最大フローと同じ値を持つことを示せ。

$f(u, x) = f(x, v)=f(u,v)$ であるため、G の最大フローの値 $|f| = \sum_{v \in V} f(s, v) -\sum_{v \in V}f(v, s)$ は辺を分割しても変わらないため。

1-2.

複数の入口や出口を持つフローネットワークの任意のフローは、超入口や超出口を追加して出来る単一の入口や出口を持つネットワークと同一であることを示せ。

超入口から張られる辺の容量は無限なので、流したいだけ流すことが出来る。そのため、超入口を与える前のグラフに比べて辺のフローは影響を受けない。

1-3.

$s \rightsquigarrow u \rightsquigarrow t$ となる道が存在しないような頂点 u が存在するとき、全ての頂点 $v \in V$ について $f(u,v)=f(v,u)=0$ を満たす最大フロー f が存在することを示せ。

1-5.

最大フロー問題を線形計画問題として記述せよ。

$\begin{eqnarray} maximize & \sum_{(s, u) \in E} f(s, u) -\sum_{(u, s)\in E}f(u, s) \\ subject\ to & \sum_{(v, u) \in E} f(v, u) = \sum_{(u, v)\in E}f(u, v) & (u \in V-\{s, t\}) \\ & f(u, v) \leqq c(u, v) & ((u, v) \in E) \\ & f(u, v) \geqq 0 & ((u, v) \in E) \end{eqnarray}$

Ford-Fulkerson 法

Ford-Fulkerson-Method(G, s, t)
    フロー f を 0 に初期化する
    while 増加可能経路 p が残余ネットワークに Gf に存在する
        フロー f を p に沿って増やす
    return f

残余ネットワーク

辺 (u, v) に追加でどのくらいフローを流すことが出来るかを残余容量 $c_f(u, v)=c(u,v)-f(u,v)$ で表す。

$(v,u) \in E$ にフローが f(v, u) 流れているとき、フローを削減できることを表現するため、 $c_f(u,v)=f(v,u)$ と表せる。

これをまとめると、
$c_f(u,v) = \begin{cases} c(u,v)-f(u,v) & (u,v) \in E \\ f(v,u) & (v,u) \in E \\ 0 & それ以外 \end{cases}$

増加

f(u,v) 流れているフローを変化させることを考える。f を G におけるフロー、f' を残余容量からなる残余ネットワーク $G_f$ のフローとすると、変化後のフローは以下のように表される。

$(f \uparrow f')(u,v) = \begin{cases} f(u,v) + f'(u,v) - f'(v,u) & (u,v) \in E \\ 0 & それ以外 \end{cases}$

補題 26.1

$|f \uparrow f'| = |f|+|f'|$ を示せ

まず、容量制限を満たすことを示す。
$\begin{eqnarray} (f \uparrow f')(u,v) &=& f(u,v)+f'(u,v)-f'(v,u) \\ &\geqq& f(u,v)+f'(u,v)-f(u,v) \\ &=& f'(u,v) \\ &\geqq& 0 \end{eqnarray}$

$\begin{eqnarray} (f \uparrow f')(u,v) &=& f(u,v)+f'(u,v)-f'(v,u) \\ &\leqq& f(u,v)+f'(u,v) \\ &\leqq& f(u,v)+c_f(u,v) \\ &=& f(u,v) +c(u,v) -f(u,v) \\ &=& c(u,v) \end{eqnarray}$

http://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf

全ての $u\in V$ について以下の式が成り立つことを示す。
$\sum_{v \in V}(f\uparrow f')(u,v)- \sum_{v \in V}(f\uparrow f')(v,u) = \sum_{v \in V}f(u,v)-\sum_{v \in V}f(v,u)+\sum_{v \in V}f'(u,v)-\sum_{v \in V}f'(v,u)$

u から出る辺のもう一方の端点の集合を $V_1(u) = \{ v:(u,v) \in E \}$ と表す。
また、u へ向かう辺のもう一方の端点の集合を $V_2(u) = \{ v:(v,u) \in E \}$ と表す。

G には逆平行辺を含まれないので、 $V_1(u) \cap V_2(u)=\emptyset$

$\begin{cases} (f \uparrow f')(u,v)>0 & v \in V_1(u) \\ (f \uparrow f')(v,u)>0 & v \in V_2(u) \end{cases}$

$\begin{eqnarray} \sum_{v \in V}(f\uparrow f')(u,v)&-& \sum_{v \in V}(f\uparrow f')(v,u)\\ &=& \sum_{v \in V_1(u)}(f\uparrow f')(u,v)- \sum_{v \in V_2(u)}(f\uparrow f')(v,u) \\ &=& \sum_{v \in V_1(u)}(f(u,v)+f'(u,v)-f'(v,u))- \sum_{v \in V_2(u)}(f(v,u)+f'(v,u)-f'(u,v)) \\ &=& \sum_{v \in V_1(u)}f(u, v) - \sum_{v \in V_2(u)}f(v, u) + \sum_{v \in V_1(u)}f'(u, v) + \sum_{v \in V_2(u)}f'(u, v) - \sum_{v \in V_1(u)}f'(v,u) - \sum_{v \in V_2(u)}f'(v, u) \\ &=& \sum_{v \in V_1(u)}f(u, v) - \sum_{v \in V_2(u)}f(v, u) + \sum_{v \in V_1(u) \cup V_2(u)}f'(u, v) - \sum_{v \in V_1(u) \cup V_2(u)}f'(v,u) \end{eqnarray}$

$\begin{eqnarray} |f \uparrow f'| &=& \sum_{v \in V}(f \uparrow f')(s,v) -\sum_{v \in V}(f \uparrow f')(v,s) \\ &=& \sum_{v \in V}f(s,v)- \sum_{v \in V}f(v, s) + \sum_{v \in V}f'(s,v)- \sum_{v \in V}f'(v, s) \\ &=& |f|+|f'| \end{eqnarray}$

増加可能経路

残余ネットワーク $G_f$ 上での s から t への経路。

増加可能経路 p の各辺に沿って増やすことの出来るフローの最大値を p の残余容量とし、以下のように定義する。
$c_f(p) =min\{c_f(u,v): (u, v) は p 上にある \}$

補題 26.2

関数 $f_p$ を以下のように定義する。

$f_p(u, v)= \begin{cases} c_f(p) & (u,v) が p 上にあるとき \\ 0 & それ以外 \end{cases}$

このとき、 $f_p$ は $G_f$ のフローで $|f_p|=c_f(p) > 0$ である。

$| f \uparrow f_p| =|f|+|f_p| > |f|$ より、 $f_p$ を $f$ に加えると、より最大値に近い f を得られる。

フローネットワークのカット

V を $s \in S$ と $t \in T$ を満たす S と T=V-S に分割する。これをカット (S, T) とする。

カット(S,T) と交差する純フローを
$f(S,T) =\sum_{u\in S} \sum_{v\in T}f(u,v) -\sum_{u\in S} \sum_{v\in T}f(v,u)$
と定義する。

カットの容量は $c(S,T)=\sum_{u\in S}\sum_{v\in T} c(u,v)$ である。

最小カットは、カット(S, T)の中で、容量が最小のカットである。

補題 26.4

カット(S, T)と交差する純フローは f(S, T)=|f| である。

証明

$\begin{eqnarray} | f | &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s)\\ &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) +\sum_{u \in S-\{s\} }\big( \sum_{v\in V}f(u,v)- \sum_{v\in V}f(v,u) \big)\\ &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) +\sum_{u \in S-\{s\} } \sum_{v\in V}f(u,v)- \sum_{u \in S-\{s\} }\sum_{v\in V}f(v,u) \\ &=& \sum_{v \in V} \big( f(s,v) +\sum_{u \in S-\{s\} } f(u,v)\big) - \sum_{v \in V} \big( f(v,s) +\sum_{u \in S-\{s\} } f(v,u)\big) \\ &=& \sum_{v \in V} \sum_{u\in S}f(u, v)- \sum_{v \in V} \sum_{u\in S}f(v, u) \\ &=& \sum_{v \in S} \sum_{u\in S}f(u, v) + \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in S} \sum_{u\in S}f(v, u) - \sum_{v \in T} \sum_{u\in S}f(v, u) & (V=S \cup T かつ S \cap T = \emptyset だから)\\ &=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u) +\big( \sum_{v \in S} \sum_{u\in S}f(u, v) - \sum_{v \in S} \sum_{u\in S}f(v, u) \big) \\ &=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u) \\ &=& f(S,T) \end{eqnarray}$

系 26.5

G の任意のフロー f の値は G の任意のカット容量によって上から抑えられる。

証明

$\begin{eqnarray} |f| &=& f(S,T)\\ &=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u)\\ &\leqq& \sum_{v \in T} \sum_{u\in S}f(u, v) \\ &\leqq& \sum_{v \in T} \sum_{u\in S}c(u, v) \\ &=&c(S, T) \end{eqnarray}$

定理 26.6 最大フロー最小カットの定理

fはGの最大フローである。
残余ネットワーク Gf は増加可能経路を含まない。
Gのあるカット(S,T)に対して|f|=c(S,T) である。

証明

最大フローであるにも関わらず増加可能経路を持つと仮定すると、 $f_p$ が定まり、|f| より値が大きいGのフローが得られるので矛盾する。

Gf が増加可能経路を持たないとき、Gfにはsからtへの道が存在しない。

$S=\{ v \in V: G_f に s から v への道が存在する \}, T=V-S$ と定義する。

明らかに $s\in S$ であり、 $G_f$ にはsからtへの道が存在しないので $t\not\in S$ である。よって、この分割(S,T)はカットである。

$f(v,u)\not=0$ ならば $c_f(u,v)=f(v,u)$ で $(u,v)\in E_f$ だから $v\in S$ となり矛盾する。よって $f(v,u)=0$

$\begin{eqnarray} f(S,T) &=& \sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in S}\sum_{v\in T}f(v,u) \\ &=& \sum_{u\in S}\sum_{v\in T}c(u,v)-\sum_{u\in S}\sum_{v\in T}0 \\ &=&c(S,T) \end{eqnarray}$

全てのカット(S, T) に対して $|f| \leqq c(S,T)$ である。よって $|f| = c(S,T)$ はfが最大フローであるための十分条件である。

Ford-Fulkersonのアルゴリズム

Ford-Fulkerson(G, s, t)
    for (u, v) in G.E
        (u, v).f = 0
    while 残余ネットワーク G_f に s から t への道 p が存在する
        c_f(p) = min([c_f(u, v) for (u, v) in p])
        for (u, v) in p
            if (u, v) in G.E
                (u, v).f = (u, v).f + c_f(p)
            else
                (v, u).f = (v, u).f - c_f(p)

つづく

続きは来週やります。

2016-10-19

Codeforces Round #377 (Div. 2) F. Tourist Reform

Codeforces 競技プログラミング

問題

http://codeforces.com/contest/732/problem/F

N 頂点 M 辺の連結な無向グラフが与えられます。すべての辺の向きをそれぞれどちらか 1 方向に限定した時に頂点 i から到達可能な頂点の数を mi とします。mi の最小値を最大化するとき、その値と、その時の各辺の向きを出力してください。

解法

2重辺連結成分の中では上手く巡回するように辺の向きを決めると、連結成分内の全ての頂点を行き来することができます。逆に、橋となる辺の向きを固定するとき、連結成分 v->u へ橋の向きを固定することを考えると、mi の最小値 m は必ず m<=|u| となります。よって、最大の連結成分 u を選び、各連結成分からは u に向けて橋を固定すれば良いです。

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/

public class F {
  private static class Task {
    long N;
    TreeMap<Long, int[]> direction = new TreeMap<>();
    ArrayList<ArrayList<Integer>> graph;

    void disconnectedDfs(int v, int p, boolean[] vis) {
      vis[v] = true;
      for (int u : graph.get(v)) {
        if (u == p) continue;
        if (direction.containsKey(edgeValue(u, v))) continue;
        direction.put(edgeValue(u, v), new int[]{v, u});
        if (!vis[u]) {
          disconnectedDfs(u, v, vis);
        }
      }
    }

    void superDfs(int v, int p, int[] ord) {
      for (int u : graph.get(v)) {
        if (u == p) continue;
        ord[u] = ord[v] + 1;//v <- u
        superDfs(u, v, ord);
      }
    }

    void solve(FastScanner in, PrintWriter out) throws Exception {
      N = in.nextInt();
      int M = in.nextInt();
      int[][] edges = new int[2][M];
      graph = new ArrayList<>();
      for (int i = 0; i < N; i++) graph.add(new ArrayList<>());
      for (int i = 0; i < M; i++) {
        int u = in.nextInt() - 1;
        int v = in.nextInt() - 1;
        graph.get(u).add(v);
        graph.get(v).add(u);
        edges[0][i] = u;
        edges[1][i] = v;
      }

      int k;
      int[] cmp;
      ArrayList<int[]> bridges;
      {
        BiconnectedComponents bic = new BiconnectedComponents(graph);
        k = bic.k;
        cmp = bic.cmp;
        bridges = bic.bridges;
      }
      for (int i = 0; i < N; i++) graph.get(i).clear();

      int[] sizes = new int[k];
      for (int c : cmp) sizes[c]++;
      int maxSize = 0;
      int maxComponentId = 0;
      for (int i = 0; i < sizes.length; i++)
        if (maxSize < sizes[i]) {
          maxSize = sizes[i];
          maxComponentId = i;
        }

      for (ArrayList<Integer> g : graph) g.clear();

      for (int[] bridge : bridges) {
        int u = bridge[0];
        int v = bridge[1];
        graph.get(cmp[u]).add(cmp[v]);
        graph.get(cmp[v]).add(cmp[u]);
      }
      int[] ord = new int[k];
      superDfs(maxComponentId, -1, ord);
      for (ArrayList<Integer> g : graph) g.clear();

      for (int[] bridge : bridges) {
        int u = bridge[0];
        int v = bridge[1];
        if (ord[cmp[v]] < ord[cmp[u]]) {
          //u->v
          direction.put(edgeValue(u, v), new int[]{u, v});
        } else {
          //v->u
          direction.put(edgeValue(u, v), new int[]{v, u});
        }
      }

      for (int i = 0; i < M; i++) {
        if (!direction.containsKey(edgeValue(edges[0][i], edges[1][i]))) {
          graph.get(edges[0][i]).add(edges[1][i]);
          graph.get(edges[1][i]).add(edges[0][i]);
        }
      }

      boolean[] vis = new boolean[(int) N];
      for (int i = 0; i < N; i++) {
        if (!vis[i]) disconnectedDfs(i, -1, vis);
      }

      out.println(maxSize);
      for (int i = 0; i < M; i++) {
        int[] vu = direction.get(edgeValue(edges[0][i], edges[1][i]));
        out.println((vu[0] + 1) + " " + (vu[1] + 1));
      }

    }

    long edgeValue(int u, int v) {
      return N * Math.min(u, v) + Math.max(u, v);
    }

    class BiconnectedComponents {

      private int[] order;
      private ArrayDeque<Integer> stack = new ArrayDeque<>();
      private ArrayDeque<Integer> path = new ArrayDeque<>();
      private boolean[] inStack;
      private int idx;
      private int k;
      private final ArrayList<ArrayList<Integer>> G;

      public ArrayList<int[]> bridges = new ArrayList<>();
      public int[] cmp;

      BiconnectedComponents(ArrayList<ArrayList<Integer>> g) {
        int n = g.size();
        this.G = g;
        idx = 0;
        k = 0;
        order = new int[n];
        Arrays.fill(order, -1);
        inStack = new boolean[n];
        cmp = new int[n];

        for (int v = 0; v < n; v++) {
          if (order[v] == -1) {
            dfs(v, n);

            // [v, N] が追加されてしまっているので削除
            bridges.remove(bridges.size() - 1);
          }
        }
      }

      private void dfs(int v, int p) {
        order[v] = idx++;
        stack.addLast(v);
        inStack[v] = true;
        path.addLast(v);
        for (Integer to : G.get(v)) {
          if (to == p) continue;

          if (order[to] == -1)
            dfs(to, v);
          else if (inStack[to])
            while (order[path.peekLast()] > order[to]) path.pollLast();
        }

        if (v == path.peekLast()) {
          bridges.add(new int[]{p, v});
          while (true) {
            int w = stack.pollLast();
            inStack[w] = false;
            cmp[w] = k;
            if (v == w) break;
          }
          path.pollLast();
          ++k;
        }
      }
    }

  }

  /**
   * ここから下はテンプレートです。
   */
  public static void main(String[] args) throws Exception {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}

2016-10-18

Codeforces Round #377 (Div. 2) E. Sockets

Codeforces 競技プログラミング

問題

Problem - 732E - Codeforces

N 台のパソコンがあり、パソコン i の消費電力は Pi です。ソケットが M 個あり、ソケット j の供給電力は Sj です、消費電力と供給電力が等しいとき、パソコンをソケットに接続できます。1 つのソケットには 1 台のパソコンしか接続できません。アダプタを 1 個使うと、ソケットの供給電力を (Sj+1)/2 にします。できるだけ多くパソコンを繋いだ時のパソコンの台数とアダプタの最小値を求めてください。

解法

消費電力の大きいパソコンから見てソケットとペアを作り、使われなかったソケットはアダプタを追加していきます。制約が大きいので、高速化の工夫として、3つの変数を1つにすると良いです。他に、sort の代わりに radixsort を使う、ヒープを自前で実装する、などの工夫があります。

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/

public class E {
  private static class Task {

    void solve(FastScanner in, PrintWriter out) throws Exception {
      long start = System.currentTimeMillis();

      int N = in.nextInt();
      int M = in.nextInt();
      int[] P = in.nextIntArray(N);
      int[] S = in.nextIntArray(M);
      int[][] powers = new int[N][2];
      for (int i = 0; i < N; i++) {
        powers[i][0] = P[i];
        powers[i][1] = i;
      }
      Arrays.sort(powers, (o1, o2) -> -(o1[0] - o2[0]));

      System.err.println(System.currentTimeMillis() - start);

      long[] sockets = new long[M * 31];
      long bit32 = 1L << 32;
      long bit18 = 1L << 18;

      int pos = 0;
      for (int id = 0; id < M; id++) {
        long s = S[id];
        long x = s * bit32 + 30 * bit18 + id;
        sockets[pos++] = -x;
        for (int adapter = 1; adapter <= 30; adapter++) {
          if (s == 1) break;
          s = (s + 1) / 2;
          long y = s * bit32 + (30 - adapter) * bit18 + id;
          sockets[pos++] = -y;
        }
      }
      System.err.println(System.currentTimeMillis() - start);
      Arrays.sort(sockets);

      System.err.println(System.currentTimeMillis() - start);

      int c = 0;
      int adapters = 0;
      int[] A = new int[M];
      int[] B = new int[N];
      boolean[] used = new boolean[M];

      int cur = 0;
      for (int[] power : powers) {
        int p = power[0];

        while (cur < pos) {
          long socket = -sockets[cur];
          long s = socket / bit32;
          if (s < p) break;

          long adapter = (socket - s * bit32) / bit18;
          int id = (int) (socket - s * bit32 - adapter * bit18);
          adapter = 30 - adapter;

          if (used[id]) {
            cur++;
          } else if (s == p) {
            c++;
            adapters += adapter;
            A[id] = (int) adapter;
            B[power[1]] = id + 1;
            used[id] = true;
            cur++;
            break;
          } else {
            cur++;
          }
        }
      }

      System.err.println(System.currentTimeMillis() - start);
      StringBuilder builder = new StringBuilder();
      builder.append(c).append(" ").append(adapters).append("\n");
      for (int i = 0; i < M; i++) {
        if (i > 0) builder.append(" ");
        builder.append(A[i]);
      }
      builder.append("\n");
      for (int i = 0; i < N; i++) {
        if (i > 0) builder.append(" ");
        builder.append(B[i]);
      }
      builder.append("\n");
      out.println(builder.toString());
      System.err.println(System.currentTimeMillis() - start);
    }
  }

  /**
   * ここから下はテンプレートです。
   */
  public static void main(String[] args) throws Exception {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}

2016-10-14

Jupyter Notebook 上で autopep8 のフォーマッタを実行できる nbextension を公開しました

その他

Jupyter autopep8

github.com

これは何

Jupyter Notebook の Cell 内で使えるコードフォーマッタです。コード編集中に Ctrl+L を押すと autopep8 を使ってコードが整形されます。

インストール方法

pip install autopep8
jupyter nbextension install https://github.com/kenkoooo/jupyter-autopep8/archive/master.zip --user
jupyter nbextension enable jupyter-autopep8-master/jupyter-autopep8

2016-10-02

Intel Code Challenge Elimination Round D. Generating Sets

Codeforces 競技プログラミング

問題

Problem - D - Codeforces

相異なる自然数を N 個もった集合 X があります。X の各要素 $x_i$ に対して、以下の操作を行うことができます。

$x_i$ を X から取り除き、 $x_i *2$ を X に加える。
$x_i$ を X から取り除き、 $x_i *2+1$ を X に加える。

集合 X に何回か操作を加えて Y にすることができる X のうち、集合内の最大値が最も小さいXを出力してください。

解法

$y_i$ にすることができる $x_i$ の候補は、 $y_i /2, y_i/4, ... , 1$ です。これを予め列挙しておき、ある値 M を二分探索し, M 以下で X を作れるかどうか調べる問題を解く事を考えます。

実は二分探索の中身は貪欲に解くことができます。各 $y_i$ について、 $y_i /2, y_i/4, ... , 1$ のうち、まだ選択されていないM以下の最大のものを選べば良いです。

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/

public class D {
  private static class Task {
    long[][] table;
    int N;
    TreeSet<Long> used = new TreeSet<>();
    boolean check(long x) {
      used.clear();

      for (int i = 0; i < N; i++) {
        for (int j = 0; ; j++) {
          if (table[i][j] > x) continue;
          if (used.contains(table[i][j])) continue;
          if (table[i][j] == 0) return false;
          used.add(table[i][j]);
          break;
        }
        if (used.size() != i + 1) return false;
      }
      return true;
    }

    void solve(FastScanner in, PrintWriter out) throws Exception {
      N = in.nextInt();
      int K = 30;
      long[] Y = new long[N];
      for (int i = 0; i < N; i++) {
        Y[i] = in.nextInt();
      }

      table = new long[N][K];
      for (int i = 0; i < N; i++) {
        long y = Y[i];
        int k = 0;
        while (y > 0) {
          table[i][k] = y;
          y /= 2;
          k++;
        }
      }

      long high = 1L << 32;
      long low = 0;
      while (high - low > 1) {
        long mid = (high + low) / 2;

        if (!check(mid)) {
          low = mid;
        } else {
          high = mid;
        }
      }

      check(high);
      for (long a : used) out.print(a + " ");
      out.println();

    }
  }

  /**
   * ここから下はテンプレートです。
   */
  public static void main(String[] args) throws Exception {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }

  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}

2016-09-29

HackerEarth July Circuits : Benny and the Universe

HackerEarth 競技プログラミング

問題

https://www.hackerearth.com/july-circuits/algorithm/benny-and-the-universe/

N 個の整数が与えられます。Q 個の整数 X が与えられるので、各Xがこれらの整数の線形和（係数は非負整数）でできるかどうか判定してください。

解法

ダイクストラします。

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/

class TestClass {
  private static class Task {
    class Edge implements Comparable<Edge> {
      int to;
      long cost;
      Edge(int to, long cost) {
        this.to = to;
        this.cost = cost;
      }
      @Override
      public int compareTo(Edge o) {
        return Long.signum(this.cost - o.cost);
      }
    }
    void solve(FastScanner in, PrintWriter out) throws Exception {
      int N = in.nextInt();
      int Q = in.nextInt();

      int[] d = in.nextIntArray(N);
      int min = Integer.MAX_VALUE;
      for (int e : d) min = Math.min(min, e);
      int[] q = in.nextIntArray(Q);

      long[] dist = new long[min];
      Arrays.fill(dist, Long.MAX_VALUE / 2);
      PriorityQueue<Edge> queue = new PriorityQueue<>();
      for (int e : d) {
        queue.add(new Edge(e % min, e));
        dist[e % min] = Math.min(dist[e % min], e);
      }
      while (!queue.isEmpty()) {
        long v = queue.poll().cost;
        for (int u : d) {
          long next = v + u;
          int to = (int) (next % min);
          if (dist[to] > next) {
            dist[to] = next;
            queue.add(new Edge(to, next));
          }
        }
      }
      for (int x : q) {
        int r = x % min;
        if (dist[r] <= x) out.println("YES");
        else out.println("NO");
      }
    }
  }

  public static void main(String[] args) throws Exception {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }

    public int[][] nextIntMap(int n, int m) {
      int[][] map = new int[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextIntArray(m);
      }
      return map;
    }
  }
}

先週のページ

先週のまとめ

定理 26.6 最大フロー最小カットの定理

証明

Ford-Fulkersonのアルゴリズム

基本 Ford-Fulkerson の解析

余談

Edmonds-Karp アルゴリズム

補題26.7

証明

定理26.8

証明

2 部グラフの最大マッチング問題

プッシュ再ラベルアルゴリズム

高さ関数

プッシュ操作

再ラベル操作

基礎アルゴリズム

Push-Relabel の正当性

補題 26.14

証明

補題26.15

証明

補題26.16

証明

補題26.17

証明

補題26.18

証明

Push-Relabel の解析

補題 26.19

証明

補題 26.20

系 26.21

補題 26.22

補題 26.23

次回予告

Push-Relabel の解析

フロント移動

練習問題

おまけ

フローネットワーク

逆平行辺

複数の入口と出口

練習問題

1-1.

1-2.

1-3.

1-5.

Ford-Fulkerson 法

残余ネットワーク

増加

補題 26.1

増加可能経路

補題 26.2

フローネットワークのカット

補題 26.4

証明

系 26.5

証明

定理 26.6 最大フロー最小カットの定理

証明

Ford-Fulkersonのアルゴリズム

つづく

問題

解法

コード

問題

解法

コード

Jupyter autopep8

これは何

インストール方法

問題

解法

コード

問題

解法

コード