2016-11-16

Codeforces Round #379 (Div. 2) F. Anton and School

問題

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

解法

Fはb_i+c_iを足すとなんとa_i*n+(sum a_j)になりそこからがんばる。あと検証もちゃんとする
— 有為 (@uwitenpen) 2016年11月15日

コード

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

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

public class F {
  private static class Task {
    void solve(FastScanner in, PrintWriter out) throws Exception {
      int N = in.nextInt();
      long[] B = in.nextLongArray(N);
      long[] C = in.nextLongArray(N);

      long[] BC = new long[N];
      long sum = 0;
      for (int i = 0; i < N; i++) {
        BC[i] = B[i] + C[i];
        sum += BC[i];
      }
      if (sum % (2 * N) != 0) {
        out.println(-1);
        return;
      }

      long S = sum / 2 / N;
      long[] A = new long[N];
      for (int i = 0; i < N; i++) {
        if ((BC[i] - S) % N != 0 || (BC[i] - S) < 0) {
          out.println(-1);
          return;
        }
        A[i] = (BC[i] - S) / N;
      }

      long[] bitSum = new long[60];
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < 60; j++) {
          bitSum[j] += (A[i] >> j) & 1L;
        }
      }

      for (int i = 0; i < N; i++) {
        long andCheck = 0, orCheck = 0;
        for (int j = 0; j < 60; j++) {
          if (((A[i] >> j) & 1L) == 1) {
            andCheck += (1L << j) * bitSum[j];
            orCheck += (1L << j) * N;
          } else {
            orCheck += (1L << j) * bitSum[j];
          }
        }
        if (B[i] != andCheck || C[i] != orCheck) {
          out.println(-1);
          return;
        }
      }

      for (long a : A) 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-11-16

Codeforces Round #379 (Div. 2) E. Anton and Tree

Codeforces 競技プログラミング

問題

http://codeforces.com/problemset/problem/734/E

N頂点のツリーがあり、各頂点は白か黒で塗られています。1回の操作で同じ色の連結成分の色を全て塗り替えることができます。ツリーを全て同じ色にするための最小の操作回数を求めてください。

解法

連結成分を1つの頂点に縮約したグラフを作ります。縮約したツリー上で考えると、例えばある黒い頂点を白く塗ったとき、次の操作でその頂点に隣接する頂点も含めて黒く塗ることができます。

このことを利用して縮約したツリーの中心付近の頂点を塗る操作を何回もすれば色が伝搬してく感じになります。この操作回数は最大で直径の半分くらいになりそうだと分かります。

コード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
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 {
      int N = in.nextInt();

      int[] color = new int[N];
      for (int i = 0; i < N; i++) {
        color[i] = in.nextInt();
      }

      UnionFind uf = new UnionFind(N);
      ArrayList<Integer>[] graph = new ArrayList[N];
      for (int i = 0; i < N; i++) graph[i] = new ArrayList<>();
      int[] A = new int[N - 1];
      int[] B = new int[N - 1];
      for (int i = 0; i < N - 1; i++) {
        A[i] = in.nextInt() - 1;
        B[i] = in.nextInt() - 1;
        if (color[A[i]] == color[B[i]]) uf.unite(A[i], B[i]);
      }
      for (int i = 0; i < N - 1; i++) {
        if (color[A[i]] == color[B[i]]) continue;
        graph[uf.find(A[i])].add(uf.find(B[i]));
        graph[uf.find(B[i])].add(uf.find(A[i]));
      }

      ArrayDeque<Integer> deque = new ArrayDeque<>();
      int[] dist = new int[N];
      Arrays.fill(dist, -1);
      int x = uf.find(0);
      dist[x] = 0;
      deque.add(x);
      while (!deque.isEmpty()) {
        int v = deque.poll();
        for (int u : graph[v]) {
          if (dist[u] != -1) continue;
          dist[u] = dist[v] + 1;
          deque.add(u);
        }
      }

      for (int i = 0; i < N; i++) {
        if (dist[i] > dist[x]) x = i;
      }

      Arrays.fill(dist, -1);
      deque.add(x);
      dist[x] = 0;
      while (!deque.isEmpty()) {
        int v = deque.poll();
        for (int u : graph[v]) {
          if (dist[u] != -1) continue;
          dist[u] = dist[v] + 1;
          deque.add(u);
        }
      }
      int y = x;
      for (int i = 0; i < N; i++) {
        if (dist[i] > dist[y]) y = i;
      }

      int diameter = dist[y];
      out.println((diameter + 1) / 2);
    }

    class UnionFind {
      // par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである
      private int[] par;
      // sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる
      private int[] sizes;

      // 木の数
      private int size;

      UnionFind(int n) {
        par = new int[n];
        sizes = new int[n];
        size = n;
        Arrays.fill(sizes, 1);
        // 最初は全てのデータiがグループiに存在するものとして初期化
        for (int i = 0; i < n; i++) par[i] = i;
      }

      /**
       * データxが属する木の根を得る
       *
       * @param x
       * @return
       */
      int find(int x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);  // 根を張り替えながら再帰的に根ノードを探す
      }

      /**
       * 2つのデータx, yが属する木をマージする。
       * マージが必要なら true を返す
       *
       * @param x
       * @param y
       * @return
       */
      boolean unite(int x, int y) {
        // データの根ノードを得る
        x = find(x);
        y = find(y);

        // 既に同じ木に属しているならマージしない
        if (x == y) return false;

        // xの木がyの木より大きくなるようにする
        if (sizes[x] < sizes[y]) {
          int tx = x;
          x = y;
          y = tx;
        }

        // xがyの親になるように連結する
        par[y] = x;
        sizes[x] += sizes[y];
        sizes[y] = 0;  // sizes[y]は無意味な値となるので0を入れておいてもよい

        size--;
        return true;
      }

      /**
       * 2つのデータx, yが属する木が同じならtrueを返す
       *
       * @param x
       * @param y
       * @return
       */
      boolean isSame(int x, int y) {
        return find(x) == find(y);
      }

      /**
       * データxが含まれる木の大きさを返す
       *
       * @param x
       * @return
       */
      int partialSizeOf(int x) {
        return sizes[find(x)];
      }

      /**
       * 木の数を返す
       *
       * @return
       */
      int size() {
        return size;
      }
    }
  }

  /**
   * ここから下はテンプレートです。
   */
  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-11-15

Codeforces Round #364 (Div. 2) E. Connecting Universities

Codeforces 競技プログラミング

問題

http://codeforces.com/contest/701/problem/E

N 頂点のツリー状に 2K 個の大学があります。これらの大学を K このペアに分割します。ペアとなっている大学間の距離の合計が最大となるようにペアを作るとき、その最大値を答えてください。

解法

辺 (v, p) を見ているとき、min(v側の大学の数, p側の大学の数)だけ、辺(v, p)上を通り道にするペアが存在します。これを各辺について計算します。

コード

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

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

public class Main {
  private static class Task {
    long K;
    boolean[] univ;
    ArrayList<Integer>[] graph;
    long ans = 0;

    // 辺 (v, p) を観た時に、v以下にある大学の数を返す
    long dfs(int v, int p) {
      long vSide = 0;
      if (univ[v]) vSide++;
      for (int u : graph[v]) {
        if (u == p) continue;
        vSide += dfs(u, v);
      }
      long pSide = 2 * K - vSide;

      // 辺 (v, p) を通る道の数を計上する
      if (p != -1) ans += Math.min(pSide, vSide);
      return vSide;
    }

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

      dfs(0, -1);
      out.println(ans);

    }
  }

  /**
   * ここから下はテンプレートです。
   */
  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-11-15

TopCoder SRM 702 Div1 Medium: RepeatedStrings

SRM 競技プログラミング

問題

"()" は良い文字列です。
S を良い文字列としたとき、"(SSS...S)" は良い文字列です。

文字列 S が与えられるので、文字列 S の部分列、かつ、良い文字列のうち、辞書順で k 番目の文字列を返してください。

解法

括弧列に対する様々な先入観から良い文字列の候補が多く感じますが、例えば "(()(()))" は良い文字列ではありません。S が良い文字列であったとき、あくまで S のコピーをいくつか並べたものを括弧で囲ったもののみが良い文字列です。

f:id:kenkoooo:20161115140311j:plain

長さが 150 以下の良い文字列がそもそも 15 万個くらいしかないので、全列挙で間に合います。

コード

import java.util.TreeSet;

public class RepeatedStrings {
  TreeSet<String> G = new TreeSet<>();
  char[] S;

  private boolean isSubSequence(String t) {
    int pos = 0;
    for (char c : S) {
      if (c == t.charAt(pos)) {
        pos++;
        if (pos == t.length()) break;
      }
    }
    return pos == t.length();
  }

  private boolean dfs(String t) {
    if (!isSubSequence(t)) return false;

    G.add(t);
    String good = t;
    while (true) {
      if (dfs("(" + good + ")")) {
        good += t;
      } else
        break;
    }
    return true;
  }

  public String findKth(String s, int k) {
    this.S = s.toCharArray();
    dfs("()");
    for (String t : G) {
      k--;
      if (k == 0) return t;
    }
    return "";
  }
}

2016-11-11

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

前回のページ

kenkoooo.hatenablog.com

内容は大体かぶってます。

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

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

頂点 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$ が成り立つ。

証明

h(s)=|V|, h(t)=0 なので、 $u \in V-\{s,t\}$ となる頂点 u について考える。

u から s への単純道 $p=< v_0, ..., v_k >$ にを考える。ここでは $v_0=u, v_k=s$ である。pは単純道なので $k< |V|-1$ である。

$h(v_i)\leq h(v_{i+1})+1$ だから

$h(v_0)=h(v_0) \leq h(v_k)+k \leq h(s)+(|V|-1)=2|V|-1$

系 26.21

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

証明

各頂点の高さ関数 h(u) は最大で $2|V|-1$ 回上がる。はい。

補題 26.22

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

証明

u から v への飽和プッシュが発生するとき、 $h(v)=h(u)-1$ である。
同様に v から u への飽和プッシュが発生するとき、 $h(v)=h(u)+1$ である。
つまり、u から v への飽和プッシュが起こった後、v から u への飽和プッシュが起こるまでに h(v) は少なくとも 2 増加する。
h(v) の最大値は 2|V|-1 なので、u と v の間に起こる飽和プッシュの回数は 2|V| 回未満であり、辺の本数を考えると全体で 2|V||E| 未満である。

補題 26.23

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

証明

ポテンシャル関数 $\Phi$ を定義する。

$\begin{eqnarray} \Phi = \sum_{v :e(v)>0} h(v) \end{eqnarray}$

頂点 u の relabel によって $\Phi$ は高々 2|V|-1 だけ増加する。
頂点 u からの飽和プッシュによって $\Phi$ は高々 2|V|-1 だけ増加する。

頂点 u から v への非飽和プッシュを考える。
この操作により e(u)=0 となるので、h(u) は和の対象から外れ、 $\Phi$ は正確に h(u) だけ減少する。
v がもともとオーバーフロー頂点だったとき、 $\Phi$ の増加量は 0 である。
v が新たにオーバーフロー頂点となる場合、 $\Phi$ は h(v) だけ増加する。
h(u)=h(v)+1 だから、 $\Phi$ は少なくとも 1 減少する。

relabel 回数の上界が (2|V|-1)(|V|-2) 回、飽和プッシュ回数の上界が 2|V||E| 回、だから、relabel の上界を $2|V|^2$ として、 $\Phi$ の増加量の上界は
$(2|V|)(2|V|^2)+(2|V|)(2|V||E|) = 4|V|^2(|V|+|E|)$ である。

$\Phi$ は非飽和プッシュによって減少するので、非飽和プッシュ回数の上界は $4|V|^2(|V|+|E|)$ である。

計算量

$O(V^2E)$

2016-11-04

Codeforces Round #378 (Div. 2) E. Sleep in Class

競技プログラミング Codeforces

問題

http://codeforces.com/contest/733/problem/E

N 階建ての建物の中にいます。各階には 'U' または 'D' の文字が書かれています。 i 階にいて U と書かれているときは i+1 階へ、D と書かれているときは i-1 階へ移動します。移動すると、直前にいた階の文字は切り替わります。i 回にいるとき、何回移動すると N+1 階もしくは 0 階へ移動できるか出力してください。

解法

実は、状況は問題文ほどややこしくありません。右側の一番近くのDで跳ね返り、左側の一番近くのUで跳ね返り、右側の二番目に近いDで跳ね返り…を外に出るまで繰り返します。累積和を上手に使うと O(N) で N 個分を一気に求めることができます。

コード

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

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

public class Main {
  private static class Task {

    void solve(FastScanner in, PrintWriter out) throws Exception {
      int N = in.nextInt();
      char[] S = in.next().toCharArray();
      int[] leftUp = new int[N];
      for (int i = 1; i < N; i++) {
        leftUp[i] = leftUp[i - 1];
        if (S[i - 1] == 'U') leftUp[i]++;
      }

      int[] rightDown = new int[N];
      for (int i = N - 2; i >= 0; i--) {
        rightDown[i] = rightDown[i + 1];
        if (S[i + 1] == 'D') rightDown[i]++;
      }
      long[] leftWing = new long[N];
      long[] rightWing = new long[N];
      {
        long rightSum = 0;
        int cur = 0;
        int right = 0;
        for (int i = 0; i < N; i++) {
          rightSum -= right * 2;
          if (S[i] == 'D' && right > 0) right--;
          int left = leftUp[i];
          if (S[i] == 'U') left++;
          if (cur <= i) cur = i + 1;
          while (cur < N && right < left) {
            if (S[cur] == 'D') {
              right++;
              rightSum += (cur - i) * 2;
            }
            cur++;
          }
          rightWing[i] = rightSum;
        }
      }
      {
        long leftSum = 0;
        int cur = N - 1;
        int left = 0;
        for (int i = N - 1; i >= 0; i--) {
          leftSum -= left * 2;
          if (S[i] == 'U' && left > 0) left--;
          int right = rightDown[i];
          if (S[i] == 'D') right++;
          if (i <= cur) cur = i - 1;
          while (cur >= 0 && left < right) {
            if (S[cur] == 'U') {
              left++;
              leftSum += (i - cur) * 2;
            }
            cur--;
          }
          leftWing[i] = leftSum;
        }
      }
      for (int i = 0; i < N; i++) {
        long ans = leftWing[i] + rightWing[i];
        if (S[i] == 'U') leftUp[i]++;
        else rightDown[i]++;
        if (leftUp[i] < rightDown[i] || (leftUp[i] == rightDown[i] && S[i] == 'U')) ans += (i + 1);
        if (leftUp[i] > rightDown[i] || (leftUp[i] == rightDown[i] && S[i] == 'D')) ans += (N - i);

        out.print(ans + " ");
      }
      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-10-30

AtCoder Grand Contest 006 C - Rabbit Exercise

AtCoder 競技プログラミング

問題

http://agc006.contest.atcoder.jp/tasks/agc006_c

解法

editorial 通りにやった。

コード

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 Main {
  private static class Task {

    int[] mul(int[] a, long K) {
      int[] cur = Arrays.copyOf(a, a.length);
      int[] x = new int[a.length];
      for (int i = 0; i < x.length; i++) x[i] = i;
      while (K > 0) {
        if ((K & 1) == 1) {
          int[] y = new int[x.length];
          for (int i = 0; i < x.length; i++) {
            y[i] = x[cur[i]];
          }
          x = y;
        }
        K >>= 1;
        int[] tmp = new int[cur.length];
        for (int i = 0; i < cur.length; i++) {
          tmp[i] = cur[cur[i]];
        }
        cur = tmp;
      }
      return x;
    }

    void solve(FastScanner in, PrintWriter out) throws Exception {

      int N = in.nextInt();
      long[] dp = new long[N];
      for (int i = 0; i < N; i++) {
        dp[i] = in.nextInt();
      }
      int M = in.nextInt();
      long K = in.nextLong();
      int[] a = new int[M];
      for (int i = 0; i < M; i++) a[i] = in.nextInt() - 1;

      int[] b = new int[N - 1];
      for (int i = 0; i < N - 1; i++) b[i] = i;
      for (int x : a) {
        int tmp = b[x];
        b[x] = b[x - 1];
        b[x - 1] = tmp;
      }
      b = mul(b, K);
      long[] diff = new long[b.length];
      for (int i = 0; i < b.length; i++) {
        int j = b[i];
        diff[i] = dp[j + 1] - dp[j];
      }
      long cur = dp[0];
      out.println(cur);
      for (int i = 0; i < N - 1; i++) {
        cur += diff[i];
        out.println(cur);
      }

    }
  }

  /**
   * ここから下はテンプレートです。
   */
  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;
    }
  }
}