Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) D. Felicity's Big Secret Revealed
問題
http://codeforces.com/contest/757/problem/D
0と1からなるn文字の文字列が与えられます。この文字列の好きな位置(先頭や末尾も含むN+1個)に仕切りを入れることができます。仕切りはいくつ入れても構いませんが、同じ位置に2個以上入れることはできません。仕切りを入れ終わったら、仕切りに挟まれている数字を10進数になおし、setに入れます。setの最大の数字をmとした時に、setに1〜mが全て含まれているような仕切りの入れ方をvalidとします。validな仕切りの入れ方をmod 1e9+7 で答えてください。
解法
nが75以下なので、mは最大でも20であることが分かります。
次のようなbitDPを考えます。
dp[pos][status] := pos文字目まで見た時に、[1, 20] の数字を含む状態のbitが status であるような組合せ
どこから始めても良いので初期状態は dp[i][0]=1 (0<=i
コード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class D { private final int MOD = (int) (1e9 + 7); private void solve(FastScanner in, PrintWriter out) { int N = in.nextInt(); String S = in.next(); int M = 1 << 20; int[][] dp = new int[N + 1][M]; for (int pos = 0; pos < N; pos++) { dp[pos][0] = 1; } for (int pos = 0; pos < N; pos++) { int cur = 0; for (int end = pos + 1; end <= N; end++) { cur = cur * 2 + (S.charAt(end - 1) - '0'); if (cur > 20) break; if (cur == 0) continue; for (int state = 0; state < M; state++) { int next = state | (1 << (cur - 1)); dp[end][next] += dp[pos][state]; dp[end][next] %= MOD; } } } long ans = 0; for (int end = 0; end <= N; end++) { for (int h = 1; h <= 20; h++) { int state = (1 << h) - 1; ans += dp[end][state]; ans %= MOD; } } out.println(ans); } public static void main(String[] args) { FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(System.out); new D().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; } } }
Codeforces Round #390 (Div. 2) D. Fedor and coupons
問題
http://codeforces.com/contest/754/problem/D
[l, r] のような範囲の組が N 個あります。このうちK個を選び、K個すべてが重なる範囲を最大にしたいです。最大値と、その時選ぶ範囲のidを出力してください。
解法
非想定解法っぽい Treap
コード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; import java.util.Random; public class D { private void solve(FastScanner in, PrintWriter out) { int N = in.nextInt(); int K = in.nextInt(); long[] l = new long[N]; long[] r = new long[N]; long min = 0; for (int i = 0; i < N; i++) { l[i] = in.nextInt(); r[i] = in.nextInt(); min = Math.min(min, l[i]); } for (int i = 0; i < N; i++) { l[i] -= min; r[i] -= min; l[i] = l[i] * 2 * N + i; r[i] = r[i] * 2 * N + i + N; } long[][] events = new long[2 * N][2]; for (int i = 0; i < N; i++) { events[2 * i][0] = l[i]; events[2 * i][1] = i; events[2 * i + 1][0] = r[i]; events[2 * i + 1][1] = -i - 1; } Arrays.sort(events, (o1, o2) -> { if (o1[0] == o2[0]) return Long.compare(o1[1], o2[1]); return Long.compare(o1[0], o2[0]); }); Treap treap = new Treap(); long from = -1; long max = 0; long[] range = null; int coupons = 0; for (long[] e : events) { int i = (int) e[1]; if (i >= 0) { coupons++; treap.insert(l[i]); if (coupons == K) { from = l[i] / (2 * N); } } else { i = -(i + 1); long tr = r[i] / (2 * N); long tl = l[i] / (2 * N); if (tl <= from && coupons >= K) { long curRange = tr - from + 1; if (max < curRange) { max = curRange; range = new long[]{from, tr}; } treap.erase(l[i]); if (coupons > K) { long kth = treap.rank(K - 1); from = kth / (2 * N); } } else { treap.erase(l[i]); } coupons--; } } out.println(max); if (max == 0) { for (int i = 0; i < K; i++) { out.print((i + 1) + " "); } out.println(); return; } for (int i = 0; i < N; i++) { long L = l[i] / (2 * N); long R = r[i] / (2 * N); if (L <= range[0] && range[1] <= R) { out.print((i + 1) + " "); K--; if (K == 0) break; } } out.println(); } public class Treap { Random random = new Random(); private class Node { Node left, right; long key; int priority; int count; Node(long key) { this.key = key; priority = random.nextInt(); left = null; right = null; count = 1; } } private Node root = null; public void clear() { root = null; } public boolean isEmpty() { return count(root) == 0; } private int count(Node n) { return n == null ? 0 : n.count; } private void update(Node c) { c.count = 1 + count(c.left) + count(c.right); } private Node leftRotate(Node c) { Node r = c.right; c.right = r.left; r.left = c; update(c); return r; } private Node rightRotate(Node c) { Node l = c.left; c.left = l.right; l.right = c; update(c); return l; } private Node insert(Node c, long key) { if (c == null) return new Node(key); if (c.key < key) { c.right = insert(c.right, key); if (c.right.priority < c.priority) c = leftRotate(c); } else { c.left = insert(c.left, key); if (c.left.priority < c.priority) c = rightRotate(c); } update(c); return c; } private Node getMinNode(Node c) { while (c.left != null) c = c.left; return c; } private Node erase(Node c, long key) { if (key == c.key) { if (c.left == null) return c.right; if (c.right == null) return c.left; Node minNode = getMinNode(c.right); c.key = minNode.key; c.right = erase(c.right, minNode.key); } else { if (c.key < key) c.right = erase(c.right, key); else c.left = erase(c.left, key); } update(c); return c; } public void insert(long key) { if (contains(key)) return; root = insert(root, key); } public void erase(long key) { root = erase(root, key); } public int size() { return count(root); } public boolean contains(long key) { return find(root, key) >= 0; } public int find(long key) { return find(root, key); } private int find(Node c, long key) { if (c == null) return -1; if (c.key == key) return count(c.left); if (key < c.key) return find(c.left, key); int pos = find(c.right, key); if (pos < 0) return pos; return count(c.left) + 1 + pos; } private Node rank(Node c, int rank) { while (c != null) { int leftCount = count(c.left); if (leftCount == rank) return c; if (leftCount < rank) { rank -= leftCount + 1; c = c.right; } else { c = c.left; } } return null; } public long rank(int rank) { if (root == null) throw new NullPointerException(); Node r = rank(root, rank); if (r == null) throw new NullPointerException(); return r.key; } } public static void main(String[] args) { FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(System.out); new D().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; } } }
Push-Relabel による最大フローアルゴリズム
はじめに
この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの23日目の記事として書かれました。
最初に、一般的なフローネットワークについて触れてます。これは始点と終点を除く頂点について、入ってくるフローと出ていくフローが常に等しい状態であるもので、Ford-Fulkerson 法などを理解するために必要です。最小カット最大フローの定理についても触れます。
次に、条件を緩和して過剰フローを許したプリフローについて考えます。高さ関数制約を導入してプッシュ操作と再ラベル操作を定め、Generic-Push-Relabel のアルゴリズムを考えます。プリフローネットワークに対して処理をしていくと最終的に最大フローが得られることを確認し、再ラベル操作、飽和プッシュ操作、非飽和プッシュ操作の回数の上界を調べます。
さらに、開栓操作を加えた Relabel-To-Front を考えることで、計算量をに改善します。ここに Highest-Label Rule を導入して、まで改善します。
最後に実装も載せました。
この記事に書いてあることは "Introduction to Algorithms" という本にそのまま書いてあります。
フローネットワーク
各辺 が、容量 を持つ有向グラフである。入り口 s と出口 t が設定されている。
非負の値を取る量 を頂点 u から頂点 v へのフローと呼ぶ。
フローは以下の 2 条件を満たす。
- 容量制限: 全ての に対して、 でなければならない。
- フロー保存則: 全ての に対して、でなければならない。
- 頂点 u に入ってくるフローと、頂点 u から出ていくフローの量が等しい。
最大フロー問題は s から t への最大の値を持つフローを求める問題である。
逆平行辺
逆平行辺を持つネットワークは簡単に逆平行辺を持たないグラフに構成し直すことが出来るので、議論を簡明にするため逆平行辺を禁止することにする。
複数の入口と出口
複数の入口があっても超入口を作ってそこから各入口に容量無限の辺を張れば、入口 1 つのネットワークとして扱える。出口についても同様。
残余ネットワーク
辺 (u, v) に追加でどのくらいフローを流すことが出来るかを残余容量 で表す。
にフローが f(v, u) 流れているとき、フローを削減できることを表現するため、 と表せる。
これをまとめると、
増加
f(u,v) 流れているフローを変化させることを考える。f を G におけるフロー、f' を残余容量からなる残余ネットワーク のフローとすると、変化後のフローは以下のように表される。
補題 26.1
である。
証明
まず、容量制限を満たすことを示す。
http://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf
全ての について以下の式が成り立つことを示す。
u から出る辺のもう一方の端点の集合をと表す。
また、u へ向かう辺のもう一方の端点の集合をと表す。
G には逆平行辺を含まれないので、
増加可能経路
残余ネットワーク 上での s から t への経路。
増加可能経路 p の各辺に沿って増やすことの出来るフローの最大値を p の残余容量とし、以下のように定義する。
フローネットワークのカット
V を と を満たす S と T=V-S に分割する。これをカット (S, T) とする。
カット(S,T) と交差する純フローを
と定義する。
カットの容量はである。
最小カットは、カット(S, T)の中で、容量が最小のカットである。
系 26.5
G の任意のフロー f の値は G の任意のカット容量によって上から抑えられる。
証明
定理 26.6 最大フロー最小カットの定理
- fはGの最大フローである。
- 残余ネットワーク Gf は増加可能経路を含まない。
- Gのあるカット(S,T)に対して|f|=c(S,T) である。
証明
最大フローであるにも関わらず増加可能経路を持つと仮定すると、 が定まり、|f| より値が大きいGのフローが得られるので矛盾する。
Gf が増加可能経路を持たないとき、Gfにはsからtへの道が存在しない。
と定義する。
明らかにであり、にはsからtへの道が存在しないのでである。よって、この分割(S,T)はカットである。
かつ かつ であるようなu, v を考える。
ならば であり、となり矛盾する。よってである。
ならばで だからとなり矛盾する。よって
全てのカット(S, T) に対してである。よって はfが最大フローであるための十分条件である。
過剰量とプリフロー
今までは頂点にフローを溜め込むことができない条件のみを考えてきた。
頂点 u に流入するフローと頂点 u から流出するフローの合計が等しかった。
これを緩和して、流入量が流出量を超えることが出来るものとする。
このような条件でのフローをプリフローと呼ぶ。
この過剰量を e(u) とする。
について、
となるような頂点 をオーバーフロー頂点と呼ぶ。
高さ関数
であり、残余辺について、 が成り立つような高さ関数 h を考える。
プッシュ操作
以下の条件を満たす残余辺 (u, v) について、u から v にフローをプッシュする。
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
プッシュ後に となるようなプッシュを飽和プッシュと呼ぶ。
再ラベル操作
かつ の全ての 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 から出る辺は残余グラフに含まれなくなる。
よって全ての残余辺 について が成り立つ。
(全てのについてだから)
Generic-Push-Relabel(G)
Initialize-Preflow(G, s)
while 適用可能な push か relabel がある
適用可能な push か relabel を選び、実行する
補題 26.14
u がオーバーフロー頂点であれば、push か relabel が実行可能である。
証明
u から push が実行可能でない場合、全ての残余辺 について、 である。
このとき、 であり、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) を行った後は が保証される。
u に入る辺 (w, u) を考える。
Relabel(u) の前に が成立していたならば、操作後は が成立する。
よって Relabel(u) は高さ制約を維持する。
Push(u, v) を実行することを考える。
Push(u, v) によって が減少するとき、 が増加する。
これは に (v, u) が加わると考えられる。
このとき だからである。
新しい残余辺 (v, u) について が成り立つ。
Push(u, v) によって が減少するとき、 から (u, v) が取り除かれると考える。
このときは、制約が取り除かれるので、再び h は高さ関数である。
補題26.17
f をプリフローとする。このとき残余グラフ には s から t への道はない。
証明
矛盾を導くために における s から t への道 が存在すると仮定する。
である。
一般性を失うことなく と仮定する。
に対してである。
に対してである。
よって である。
ここでだからとなり、高さ関数制約に矛盾する。
補題26.18
Generic-Push-Relabel を実行して停止したとき、プリフロー f は最大フローである。
Generic-Push-Relabel の解析
補題 26.19
f をプリフローとする。この時、残余ネットワークの任意のオーバーフロー頂点 u から s への単純道が存在する。
証明
オーバーフロー頂点 x について、とする。
s が U に含まれることを示す。
矛盾を導くためにを仮定する。
とする。
より、
かつ、s以外のすべての頂点が非負の過剰を持ち、だから、である。
したがって
フローは非負だから
よってとなる が存在する。
よって残余ネットワークには残余辺が存在する。
よって道 が存在する。これは となり矛盾。
補題 26.20
Generic-Push-Relabel 実行中はすべての頂点 u で が成り立つ。
証明
h(s)=|V|, h(t)=0 なので、 となる頂点 u について考える。
u から s への単純道 にを考える。ここではである。pは単純道なのでである。
だから
系 26.21
relabel の回数は頂点当たり高々回である。
証明
各頂点の高さ関数 h(u) は最大で 回上がる。はい。
補題 26.22
飽和プッシュ回数は回未満である。
証明
u から v への飽和プッシュが発生するとき、である。
同様に v から u への飽和プッシュが発生するとき、である。
つまり、u から v への飽和プッシュが起こった後、v から u への飽和プッシュが起こるまでに h(v) は少なくとも 2 増加する。
h(v) の最大値は 2|V|-1 なので、u と v の間に起こる飽和プッシュの回数は 2|V| 回未満であり、辺の本数を考えると全体で 2|V||E| 未満である。
補題 26.23
非飽和プッシュ回数は回である。
証明
ポテンシャル関数を定義する。
頂点 u の relabel によって は高々 2|V|-1 だけ増加する。
頂点 u からの飽和プッシュによって は高々 2|V|-1 だけ増加する。
頂点 u から v への非飽和プッシュを考える。
この操作により e(u)=0 となるので、h(u) は和の対象から外れ、 は正確に h(u) だけ減少する。
v がもともとオーバーフロー頂点だったとき、 の増加量は 0 である。
v が新たにオーバーフロー頂点となる場合、 は h(v) だけ増加する。
h(u)=h(v)+1 だから、 は少なくとも 1 減少する。
relabel 回数の上界が (2|V|-1)(|V|-2) 回、飽和プッシュ回数の上界が 2|V||E| 回、だから、relabel の上界を として、の増加量の上界は
である。
は非飽和プッシュによって減少するので、非飽和プッシュ回数の上界はである。
許容辺
c_f(u, v) > 0 かつ h(u) == h(v) + 1 を満たすとき、辺(u, v)を許容辺という。
補題26.27
辺(u,v)へのプッシュ操作push(u,v)は新たな許容辺を作らない。
証明
(u,v)へプッシュ可能なとき、h(u)=h(v)+1である。(u,v)へのプッシュ操作によって唯一新たに残余辺(v,u)が生成しうるが、h(v)=h(u)-1であるためこれは許容辺ではない。よってプッシュ操作では新たな許容辺は作られない。
補題26.28
頂点uがオーバーフロー頂点で、uから外に向かう許容辺がなければrelabel(u)が適用できる。また、この操作の後、少なくとも1本はuから外へ向かう許容辺が存在し、uに入る許容辺は存在しない。
証明
uがオーバーフロー頂点なら、補題26.14よりプッシュかリラベル操作ができる。uから外へ向かう許容辺がないときプッシュ操作ができないので、リラベル操作ができる。リラベル操作終了後はとなり、辺(u,v)が許容辺となるような頂点vが存在し、uからvへ向かう許容辺が出来る。
リラベル操作終了後に、vからuに入る許容辺(v,u)が存在していると仮定すると、h(v)=h(u)+1であることから、リラベル操作終了前にはh(v)>h(u)+1であったことになる。しかし、高さが2以上違う頂点の間には残余辺が存在しないので、矛盾する。
オーバーフロー頂点での開栓
Discharge(u): while e(u) > 0: it = G[u].next() if it is None: Relabel(u) it = G[u].iterator() elif c_f(u, v) > 0 and h(u) == h(v) + 1: Push(u, v) else: it = G[u].next()
補題26.29
discharge(u)がrelabel(u)を呼び出すとき、uに対してリラベル操作が可能である。
証明
relabel(u)が呼び出されるとき、uから外に向かう許容辺が存在しないことを示す。
relabel(u)が呼び出されるとき、uから外へ向かう辺のうち許容辺であるものは全てプッシュ操作が適用された後である。補題26.27より、これらのプッシュ操作およびグラフ内で起こった別のプッシュ操作によって新たに許容辺が作られることはない。別の discharge(v)によってrelabel(v)が起こった場合、補題26.28よりvに入る許容辺が新たに生成されることはないため、uから外へ出る許容辺が新たに生成されることはない。
よって、relabel(u)が呼び出されるとき、uから外に向かう許容辺が存在しない。
アルゴリズム
Relabel-To-Front(s, t): Initialize-Preflow() L = [] for u in G: if u != s and u != t: L.append(u) it = L.iterator() u = it.next() while u != None: old = h(u) Discharge(u) if h(u) > old: u を L の先頭に移動 it = L.iterator() u = it.next()
任意の順番で頂点を見ていって、dischargeして高さが変わっているならその頂点をリストの先頭に持っていってリスタート、という感じである。
定理26.30
計算量はだよ。
証明
リラベル操作とリラベル操作の間をフェーズと呼ぶことにする。
リラベル操作は回行われるので、回のフェーズがある。dischargeがrelabel操作を呼び出さないとき、dischargeはリストを順番に見ていくので、高々|V|回行われる。一方、dischargeがrelabelを呼び出すと、その次に実行されるdischargeは別のフェーズのものとなる。よって、各フェーズで呼び出されるdischargeは高々|V|回であり、dischargeの総呼び出し回数は回である。
飽和プッシュの回数は全部でである。非飽和プッシュが行われるとdischargeは直ちに終了する。よって非飽和プッシュの総実行回数はである。
よって、計算量はだよ。
Highest-Label Rule
オーバーフロー頂点のうち、高さの最も高い頂点で開栓し続ければ良い。
https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws09_10/Opt2/handouts/lecture4.pdf
https://www.cs.princeton.edu/courses/archive/spring13/cos528/PreflowPushBiggestLabelSelectionAnalysis.pdf
補題4.2
非飽和プッシュ回数は
証明
ポテンシャル関数
を定義する。
リラベル操作や飽和プッシュ操作によっては最大Vだけ増加する。リラベル操作は全部で回、飽和プッシュ操作は全部で回行われるので、全体での増加量はである。
オーバーフロー頂点のうち、高さが最大のものをuとする。h(u)を変化させるリラベルの間に起こった非飽和プッシュたちをフェーズと呼ぶことする。リラベル操作を行ったり、uの過剰フローを次の高さの頂点に全てプッシュし終えたりするとフェーズは終了する。各頂点ごとに必ず1回は非飽和プッシュが存在し、最大でも回のフェーズがある(リラベル操作の2倍の回数)。
k回以上の非飽和プッシュが行われるフェーズをbigとし、それ以外のフェーズをsmallとする。smallフェーズでは最大でk回の非飽和プッシュが行われるので、全体で回行われる。bigフェーズでは高さが最大の頂点がk個以上存在するので、1回の非飽和プッシュで少なくともポテンシャルはk減少する。全体での増加量はであるから、bigフェーズの非飽和プッシュは全体で回である。よってbigとsmallの非飽和プッシュの回数は合計でである。ここでとすると、となる。
実装
import java.util.ArrayList; import java.util.Comparator; import java.util.PriorityQueue; public class RelabelToFront { class Edge { int from, to, rev; long flow, cap; Edge(int from, int to, long cap, int rev) { this.from = from; this.to = to; this.cap = cap; this.rev = rev; this.flow = 0; } } private int N; private ArrayList<ArrayList<Edge>> graph = new ArrayList<>(); private long[] excess; private int[] height; private int[] seen; private PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> -o[0])); RelabelToFront(int N) { this.N = N; for (int i = 0; i < N; i++) graph.add(new ArrayList<>()); excess = new long[N]; height = new int[N]; seen = new int[N]; } public void addEdge(int from, int to, long cap) { graph.get(from).add(new Edge(from, to, cap, graph.get(to).size())); graph.get(to).add(new Edge(to, from, 0, graph.get(from).size() - 1)); } private void push(Edge e) { int u = e.from; int v = e.to; long send = Math.min(excess[u], e.cap - e.flow); e.flow += send; graph.get(v).get(e.rev).flow -= send; excess[u] -= send; excess[v] += send; if (excess[v] > 0) queue.add(new int[]{height[v], v}); if (excess[u] > 0) queue.add(new int[]{height[u], u}); } private void relabel(int u) { int minHeight = N * 2; for (Edge e : graph.get(u)) if (e.cap - e.flow > 0) minHeight = Math.min(minHeight, height[e.to]); height[u] = minHeight + 1; queue.add(new int[]{height[u], u}); } private void discharge(int u) { while (excess[u] > 0) { if (seen[u] < graph.get(u).size()) { Edge e = graph.get(u).get(seen[u]); if (e.cap - e.flow > 0 && height[u] == height[e.to] + 1) push(e); else seen[u] += 1; } else { relabel(u); seen[u] = 0; } } } public long maxFlow(int source, int sink) { height[source] = N; for (Edge e : graph.get(source)) { excess[source] += e.cap; push(e); } while (!queue.isEmpty()) { int[] q = queue.poll(); int u = q[1]; if (u == source || u == sink) continue; discharge(u); } long maxFlow = 0; for (Edge e : graph.get(source)) maxFlow += e.flow; return maxFlow; } }
終わりに
くぅ~疲れましたw これにて完結です!
実は、会社の輪読会で最大フローの章を担当したのが始まりでした
本当はRelabel-To-Frontに辿り着く前に力尽きてしまったのですが←
ご厚意を無駄にするわけには行かないので流行りのアドベントカレンダーで挑んでみた所存ですw
以下、Mi_Sawaさんのみんなへのメッセジをどぞ
「動的木を使うともっと速くなります」
追記
ぼくからのみんなへのメッセジ, どちらかというと, 「3つくらいヒューリスティックを入れるともっと速くなります」ですかね. (動的木使うくらいならアルゴリズム変える)
— みさわ (@Mi_Sawa) 2016年12月22日
退学を支える技術
この記事は退学 Advent Calendar 2016 - Adventarの22日目の記事です。
アドベントカレンダーに投稿されている記事を見ると、退学した人間の自分語りか退学する予定の自分語りの記事しかないので、ここでは少し趣向を変えて、退学の技術的なノウハウを共有したいと思います。
退学とは
退学とはそもそもなんでしょうか。放校や除籍など広義の退学を含む場合もありますが、ここでは退学願を提出することを退学とします。
退学願の入手法
退学願はどのように入手すればよいのでしょうか。もしかしたら事務室に行けば手に入るかもしれませんが、退学したいわけですし、できれば学校に行かずに入手したいところです。
https://www.k.u-tokyo.ac.jp/j/syllabus/tai.pdf
学校によっては、このようにインターネットで退学願をダウンロードすることができます。これで人間と会話せずに退学願を書くことができそうです。
スタンプラリー
退学願を見てまず目に入ってくるのは、専攻長や指導教員と書かれた長方形です。書類の右上にある長方形には押印すべしというルールが説明無しにまかり通っていますが、これも例外ではなく、この長方形内に指定された人物に印鑑を押してもらう必要があります。
写真の例では、指導教員ならびに専攻長から印鑑を押して貰う必要があります。つまり、少なくとも2回はスタンプラリーをする必要があるわけです。しかしながら、退学したいのに悠長にスタンプラリーに興じている場合ではないということは学校側も百も承知で、実はスタンプを集める必要はありません。ある程度の規模の学校であれば退学者を出すことにも慣れているため、このスタンプラリーも自動化されています。スタンプが押されていない状態の退学願をそのまま事務室に提出しても、それが専攻長や指導教員のもとに巡っていき、スタンプが押された状態になって教務課へ自動的に提出されるのです。
退学の理由
学籍番号や個人情報を埋めると、その次に理由を書くスペースが与えられます。この理由に何を書いても受理されるとは思いますが、経済的困窮などと書いておくと、あとで述べるような救済措置が施される場合があります。
退学願の提出のタイミング
学校にもよりますが、退学願は学期開始の1ヶ月前までに提出する必要があります。例えば、冬学期は10月1日に開始するので、その前に退学する場合は、8月31日までに提出しなければなりません。また、東京大学の場合、退学届を提出すると職員の方が勝手に授業料免除申請を取り下げてくださいます。
冷静に考えると、退学予定者の授業料を免除する義理はないので、気持ちは分からなくはないのですが、例えば「夏学期は授業料免除して、10月1日に開始する冬学期の前に退学するため、8月31日付けで退学する」というプランで退学願を提出すると、夏学期の授業料免除申請を、経済的な条件などが免除基準をクリアしていようが関係なく、申請をいつの間にか取り下げてきます。これがなかなかの罠で、先に職員に手の内を見せてしまったために、免除される予定の27万円を払う羽目になります。これを避けるために、授業料免除の通知が来たことを確認してから、退学希望日ギリギリの日程で提出する必要があります。
タイムマシン
万が一、払う予定のない授業料を払う事になってしまった場合、タイムマシンを使うことができます。これは奥の手で、「どうしても授業料が払えないので過去に遡って実は既に退学していたことにしてくれ〜」という救済措置です。これについてはここでは話しませんが、消費者金融に行く前に、そういうものも存在することを思い出していただければと思います。
最後に
退学する際に気をつけるべきことは、払う予定のないお金がかからないかどうか、ということです。特に、退学願を出す時は脳内物質が大変なことになっているでしょうから、意識的に冷静になって、制度を調べながら対処する必要があります。
皆さんの確実な退学を応援いたします。
2016-2017 ACM-ICPC Southwestern European Regional F Performance Review
問題
根つき木があって、各頂点にはランクとコストが定められています。各頂点について、その頂点の子孫であり、かつ、その頂点のランク未満のランクをもつ頂点のコストの合計を計算してください。
解法
オイラーツアーで子孫となる範囲を計算しておきます。こうすることで、各頂点について、子孫を数列上の範囲として管理できます。このような処理をしておくと、以下のようなクエリを処理する問題になります。
- 場所 pos に数字 cost を入れる。
- 範囲 (start, end) に含まれる数字の合計を計算する。
これは Fenwick tree を使うことで処理できます。
解法
import java.io.PrintWriter; import java.util.*; public class F { ArrayList<Integer>[] tree; int[] start; int[] end; private void solve(Scanner in, PrintWriter out) { int N = in.nextInt(); tree = new ArrayList[N]; for (int i = 0; i < N; i++) tree[i] = new ArrayList<>(); start = new int[N]; end = new int[N]; int[] costs = new int[N]; int[] ranks = new int[N]; int rootId = -1; for (int i = 0; i < N; i++) { int parent = in.nextInt() - 1; int rank = in.nextInt(); int cost = in.nextInt(); costs[i] = cost; ranks[i] = rank; if (parent >= 0) { tree[i].add(parent); tree[parent].add(i); } else { rootId = i; } } dfs(rootId, -1); int[][] nodes = new int[N][2]; for (int i = 0; i < N; i++) { nodes[i][0] = ranks[i]; nodes[i][1] = i; } Arrays.sort(nodes, Comparator.comparingInt(o -> o[0])); FenwickTree bit = new FenwickTree(2 * N); long[] ans = new long[N]; int addHead = 0; int sumHead = 0; while (addHead < N) { int curRank = nodes[addHead][0]; while (addHead < N && nodes[addHead][0] == curRank) { int i = nodes[addHead][1]; ans[i] = bit.sum(start[i], end[i]) / 2; addHead++; } while (sumHead < N && nodes[sumHead][0] == curRank) { int i = nodes[sumHead][1]; bit.add(start[i], costs[i]); bit.add(end[i], costs[i]); sumHead++; } } for (long a : ans) out.println(a); } int now = 0; void dfs(int v, int p) { start[v] = now; now++; for (int u : tree[v]) { if (u == p) continue; dfs(u, v); } end[v] = now; now++; } public class FenwickTree { int N; long[] data; FenwickTree(int N) { this.N = N + 1; data = new long[N + 1]; } void add(int k, long val) { for (int x = k; x < N; x |= x + 1) { data[x] += val; } } // [0, k) long sum(int k) { if (k >= N) k = N - 1; long ret = 0; for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += data[x]; } return ret; } // [l, r) long sum(int l, int r) { return sum(r) - sum(l); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); new F().solve(in, out); in.close(); out.close(); } }
AtCoder Regular Contest 065 F - シャッフル / Shuffling
解法
dp[x][y] := x 文字目まで決めて1をy個使ってできる決め方の数
とします。
l 文字目まで見るとき、どこまでがシャッフルされる範囲に含まれるかというのを前もって計算しておけば良いです。
コード
import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Main { private void solve(Scanner in, PrintWriter out) { final int MOD = (int) (1e9 + 7); int N = in.nextInt(); int M = in.nextInt(); char[] S = in.next().toCharArray(); int[] right = new int[N]; Arrays.fill(right, -1); for (int i = 0; i < M; i++) { int l = in.nextInt() - 1; int r = in.nextInt() - 1; if (right[l] < r) right[l] = r; } int max = 0; for (int i = 0; i < N; i++) { max = Math.max(max, i); max = Math.max(max, right[i]); right[i] = max; } int[] sum = new int[N]; for (int i = 0; i < N; i++) sum[i] = S[i] - '0'; for (int i = 0; i < N - 1; i++) sum[i + 1] += sum[i]; long[][] dp = new long[N + 1][N + 1]; dp[0][0] = 1; for (int i = 0; i < N; i++) { for (int usedOne = 0; usedOne < N; usedOne++) { int r = right[i]; int restOne = sum[r] - usedOne; if (restOne < 0) continue; if (restOne > 0) dp[i + 1][usedOne + 1] = (dp[i + 1][usedOne + 1] + dp[i][usedOne]) % MOD; if (r - i + 1 != restOne) dp[i + 1][usedOne] = (dp[i + 1][usedOne] + dp[i][usedOne]) % MOD; } } out.println(dp[N][sum[N - 1]]); } public static void main(String[] args) { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); new Main().solve(in, out); in.close(); out.close(); } }