CS Academy Round #14 Subarrays Xor Sum

問題

https://csacademy.com/contest/round-14/task/subarrays-xor-sum/

解法

eha くんに解説をしてもらってようやく理解した。

各ビットごとに独立なので、ビットごとに分ける。

0と1のみの数列の長さ k 以下の数列の xor の合計値をとりたい。 i 番目の数を末尾とする長さ k 以下の数列のうち、 xor が z となるものをカウントする。

コード

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

public class Main {

  private static final int MOD = (int) (1e9 + 7);

  /**
   * 長さ k 以下のものについて計算する
   */
  private long count(int[] bit, int k) {
    if (k == 0) {
      return 0;
    }

    int N = bit.length;
    long res = 0;

    // count[i] := 長さ k 以下の数列で、 xor が i となるものの数
    int[] count = new int[2];
    int[] imos = new int[N + 1];
    for (int i = 0; i < N; i++) {
      imos[i + 1] = imos[i] ^ bit[i];
    }

    for (int i = 0; i < N; i++) {
      // 末尾が 1 ならば、 xor が 0 の数列は 1 に、 1 の数列は 0 になる
      if (bit[i] == 1) {
        int t = count[0];
        count[0] = count[1];
        count[1] = t;
      }

      // 長さ 1 の数列を追加する
      if (bit[i] == 1) {
        count[1]++;
      } else {
        count[0]++;
      }

      // 長さ k+1 になってしまった列を取り除く
      if (i - k >= 0) {
        int w = imos[i + 1] ^ imos[i - k];
        if (w == 1) {
          count[1]--;
        } else {
          count[0]--;
        }
      }

      // i 番目を末尾とする、長さ k 以下の数列の個数のうち xor が 1 のものを足しておく
      res += count[1];
    }

    return res;
  }

  private void solve(FastScanner in, PrintWriter out) {

    int N = in.nextInt();
    int a = in.nextInt();
    int b = in.nextInt();
    int[] array = in.nextIntArray(N);

    long ans = 0;
    for (int bit = 0; bit < 31; bit++) {
      int[] tmp = new int[N];
      for (int i = 0; i < N; i++) {
        tmp[i] = (array[i] >> bit) & 1;
      }

      long count = (count(tmp, b) - count(tmp, a - 1));
      if (count < 0) {
        count += MOD;
      }
      count %= MOD;
      ans += count * (1 << bit);
      ans %= MOD;
    }

    out.println(ans);
  }

  public static void main(String[] args) {
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(new FastScanner(), 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;
    }
  }
}

Bitbucket サーバーにプッシュされたコードを Jenkins でビルドする

無意味にハマった。

Jenkins 側の設定

とりあえず Pipeline を使っているものとする。「ビルドのパラメータ化」にチェックを入れておくと、外部からのパラメータを受け取れるようになる。

例えばパラメータ "branch" を定義していると、Pipeline Script の Groovy は変数 branch の中に値が入った状態で起動する。

Bitbucket Server 側の設定

うちの会社では Bitbucket Server を使っている。

HTTP-Request Hook for Bitbucket Server | Atlassian Marketplace

とりあえずこのプラグインを入れる。

HTTP-Request Hook for Bitbucket Server の設定

Method

POST にする。後述するように Post Data が空であるにも関わらずだ。

URL

JENKINS_URL/job/JOB_NAME/buildWithParameters?PARAMETER_NAME=PARAMETER_VALUE

の形式で書く。

例えば、プッシュされたブランチの名前が知りたければ、以下のように書く。

JENKINS_URL/job/JOB_NAME/buildWithParameters?branch=${refChange.refId}

Username / Password

Jenkins のユーザーネームと API トークンをそれぞれ書く。

Post Data

空のままで良い。

Closeable は Close しなければ閉じられない

非常に当たり前だが、以下のコードでは "closed" が出力されることはない。

package sandbox;

import java.io.Closeable;
import java.io.IOException;

public class Sandbox {

  public static void main(String[] args) throws Exception {
    String a = get();
    System.out.println(a);
  }

  private static String get() {
    return loadFromHoge(new HogeStream());
  }

  private static String loadFromHoge(HogeStream hogeStream) {
    return "load";
  }

  static class HogeStream implements Closeable {

    @Override
    public void close() throws IOException {
      System.out.println("closed");
    }
  }
}

明らかに get の中で一生を終えているので上手いこと閉じてほしいという気持ちではある。

AtCoder Grand Contest 013 C - Ants on a Circle

問題

http://agc013.contest.atcoder.jp/tasks/agc013_c

解法

解説の通りにやった。Rustでは map を使って for を消せることを学んだ。

コード

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::cmp;
use std::collections::vec_deque::VecDeque;
use std::i64::MAX;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.parse::<usize>();
    let l = sc.parse::<i64>();
    let t = sc.parse::<i64>();

    let mut x: Vec<i64> = vec![0; n];
    let mut w: Vec<usize> = vec![0; n];

    for i in 0..n {
        x[i] = sc.parse::<i64>();
        w[i] = sc.parse::<usize>();
    }

    let cross_count = (0..n)
        .map(|i| {
            let w0 = w[0];
            let wi = w[i];
            if w0 == wi {
                return 0;
            }

            let interval;
            if w0 == 1 {
                interval = x[i] - x[0];
            } else {
                interval = x[0] + l - x[i];
            }

            if interval > t * 2 {
                return 0;
            }

            let time = t * 2 - interval;
            let count;
            if time % l == 0 && w[0] == 1 {
                count = time / l;
            } else {
                count = time / l + 1;
            }
            return count;
        })
        .collect::<Vec<i64>>();

    let count_sum: i64 = cross_count.iter().sum::<i64>() % (n as i64);
    let position;
    let num;
    if w[0] == 1 {
        position = (x[0] + t) % l;
        num = count_sum;

    } else {
        position = (x[0] - (t % l) + l) % l;
        num = (n as i64) - count_sum;
    }

    let mut positions: Vec<i64> = (0..n)
        .map(|i| {
            let p;
            if w[i] == 1 {
                p = (x[i] + t) % l;
            } else {
                p = (x[i] - (t % l) + l) % l;
            }
            return p;
        })
        .collect::<Vec<i64>>();
    positions.sort();

    let mut a = 0;
    for i in 0..n {
        if positions[i] == position {
            a = i;
            break;
        }
    }

    let ans = (0..n)
        .map(|idx| {
                 let i = (idx + n - ((num as usize) % n)) % n;
                 let p = (a + i as usize) % n;
                 return positions[p];
             })
        .collect::<Vec<i64>>();

    for a in &ans {
        println!("{}", a);
    }
}

struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

CS Academy Round #29: Root Change

問題

https://csacademy.com/contest/round-29/task/root-change/

ツリーの各頂点 i について、 i を根とした時に切断してもツリーの高さが変化しない辺の数を出力してください。

解法

editorial のコード通りです。いわゆる全方位木dpと呼ばれる手法です。
切断しても高さが変わらない辺の数は、切断すると高さが変わる辺の数を求めれば良いので、後者を求めることにします。

まず、頂点0を根とした時の、切断すると高さが変わる辺の数を求めます。0 を根とした時の頂点 v の親を p とすると、この操作によって「v を根とした時の、切断すると高さの変わる辺の数（p 方向以外）」が求まります。これを down[v] とします。

あとはこの図からエスパーしていただければ幸いです。

コード

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

public class Main {

  class Height {

    int height, unremovableEdgeNum;

    Height(int height, int unremovableEdgeNum) {
      this.height = height;
      this.unremovableEdgeNum = unremovableEdgeNum;
    }

    void merge(Height h) {
      if (h.height > height) {
        height = h.height;
        unremovableEdgeNum = h.unremovableEdgeNum;
      } else if (h.height == height) {
        unremovableEdgeNum = 0;
      }
    }

    Height goUp() {
      return new Height(height + 1, unremovableEdgeNum + 1);
    }
  }

  private ArrayList<Integer>[] tree;
  private int[] ans;
  private Height[] down, up;
  // down[u] := 0 を根としたツリー上で葉の方向に見た時の、高さと、切ったら高さが変わる辺の数
  // up[u] := 0 を根としたツリー上で根の方向に見た時の、高さと、切ったら高さが変わる辺の数

  private void solve(FastScanner in, PrintWriter out) {
    int N = in.nextInt();
    tree = new ArrayList[N];
    for (int i = 0; i < N; i++) {
      tree[i] = new ArrayList<>();
    }

    for (int i = 0; i < N - 1; i++) {
      int a = in.nextInt() - 1;
      int b = in.nextInt() - 1;
      tree[a].add(b);
      tree[b].add(a);
    }

    ans = new int[N];
    down = new Height[N];
    for (int i = 0; i < N; i++) {
      down[i] = new Height(0, 0);
    }
    up = new Height[N];
    for (int i = 0; i < N; i++) {
      up[i] = new Height(0, 0);
    }

    downDfs(0, -1);
    dfs(0, -1);
    for (int a : ans) {
      out.println(N - 1 - a);
    }
  }

  private void downDfs(int v, int p) {
    down[v] = new Height(0, 0);
    for (int u : tree[v]) {
      if (u == p) {
        continue;
      }
      downDfs(u, v);
      down[v].merge(down[u].goUp());
    }
  }

  private void dfs(int v, int p) {
    Height suffix = new Height(0, 0);
    for (int i = tree[v].size() - 1; i >= 0; i--) {
      int u = tree[v].get(i);
      if (u == p) {
        continue;
      }
      up[u] = new Height(suffix.height, suffix.unremovableEdgeNum);

      //頂点vから頂点uの方向に見た時の情報をマージしておく
      suffix.merge(down[u].goUp());
    }

    //この時点で up[u] には、頂点vを介して suffix に含まれる頂点の方向に見た時の、切手はいけない辺の数が入っている

    Height prefix = new Height(0, 0);
    for (int u : tree[v]) {
      if (u == p) {
        continue;
      }

      // v->p
      Height h = new Height(up[v].height, up[v].unremovableEdgeNum);
      // v->prefix
      h.merge(prefix);
      // v->suffix
      h.merge(up[u]);

      //u->v->...
      up[u] = h.goUp();

      dfs(u, v);

      //頂点v から頂点uの方向に見た時の情報をマージしておく
      // v->u
      prefix.merge(down[u].goUp());
    }

    //v->p
    prefix.merge(up[v]);
    ans[v] = prefix.unremovableEdgeNum;
  }

  public static void main(String[] args) {
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(new FastScanner(), 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();
    }

    public int loadChar(char[] buf) {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      int pos = 0;
      int b = readByte();
      while (isPrintableChar(b)) {
        buf[pos] = (char) b;
        b = readByte();
        pos++;
      }
      return pos;
    }

    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;
    }
  }
}

ABC062/ARC074

Rust でやってみました。標準入出力は他の人のを拝借してきたけど、 println マクロは出力ごとに flush しているようなので注意が必要そう。もっときれいに書けるようになりたい。

A - Grouping

http://abc062.contest.atcoder.jp/tasks/abc062_a

fn next() -> String {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).ok();
    return buffer;
}

fn main() {
    let s = next();
    let a: Vec<&str> = s.trim().split(' ').collect();
    let x: i32 = a[0].parse().unwrap();
    let y: i32 = a[1].parse().unwrap();

    let g1 = vec![1, 3, 5, 7, 8, 10, 12];
    let g2 = vec![4, 6, 9, 11];
    let g3 = vec![2];
    if g1.contains(&x) && g1.contains(&y) {
        println!("Yes");
    } else if g2.contains(&x) && g2.contains(&y) {
        println!("Yes");
    } else if g3.contains(&x) && g3.contains(&y) {
        println!("Yes");
    } else {
        println!("No");
    }
}

B - Picture Frame

http://abc062.contest.atcoder.jp/tasks/abc062_b

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;

fn main() {
    let mut sc = Scanner::new();
    let h = sc.parse::<usize>();
    let w = sc.parse::<usize>();
    let rows = (0..h).map(|_| sc.parse::<String>()).collect::<Vec<_>>();
    for _ in 0..w + 2 {
        print!("#");
    }
    println!("");
    for row in rows {
        println!("#{}#", row);
    }
    for _ in 0..w + 2 {
        print!("#");
    }
    println!("");
}


struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

C - Chocolate Bar

http://abc062.contest.atcoder.jp/tasks/arc074_a

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::cmp;

fn calc(h: i64, w: i64) -> i64 {
    let mut min: i64 = w;
    for h1 in 1..(h + 1) {
        let s1: i64 = h1 * w;
        let h2: i64 = h - h1;
        let w1: i64 = w / 2;
        let w2: i64 = w - w1;

        let s2: i64 = w1 * h2;
        let s3: i64 = w2 * h2;

        let mut max = cmp::max((s1 - s2).abs(), (s1 - s3).abs());
        max = cmp::max(max, (s2 - s3).abs());

        min = cmp::min(min, max);
    }
    min
}

fn main() {
    let mut sc = Scanner::new();
    let h = sc.parse::<i64>();
    let w = sc.parse::<i64>();
    if h % 3 == 0 || w % 3 == 0 {
        println!("0");
        return;
    }

    let ans = cmp::min(calc(h, w), calc(w, h));
    println!("{}", ans);
}


struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

D - 3N Numbers

http://arc074.contest.atcoder.jp/tasks/arc074_b

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::usize;
use std::cmp;


fn main() {
    let mut sc = Scanner::new();
    let n = sc.parse::<usize>();
    let mut a: Vec<i64> = vec![0; 3*n];
    for i in 0..(3 * n) {
        a[i] = sc.parse::<i64>();
    }

    let mut heap: BinaryHeap<i64> = BinaryHeap::new();
    let mut sum: i64 = 0;
    let mut prefix_max: Vec<i64> = vec![0;3*n];
    for i in 0..(2 * n) {
        if heap.len() == n {
            let min = -heap.pop().unwrap();
            sum -= min;
            let max = cmp::max(min, a[i]);
            sum += max;
            heap.push(-max);
        } else {
            heap.push(-a[i]);
            sum += a[i];
        }

        if heap.len() == n {
            prefix_max[i] = sum;
        }
    }

    heap.clear();
    sum = 0;
    let mut suffix_min = vec![0;3*n];
    for i in (n..(3 * n)).rev() {
        if heap.len() == n {
            let max = heap.pop().unwrap();
            sum -= max;
            let min = cmp::min(max, a[i]);
            sum += min;
            heap.push(min);
        } else {
            heap.push(a[i]);
            sum += a[i];
        }

        if heap.len() == n {
            suffix_min[i] = sum;
        }
    }

    let mut ans: i64 = -1000000000000000000;
    for i in n..(2 * n + 1) {
        let p = prefix_max[i - 1] as i64;
        let s = suffix_min[i] as i64;
        // println!("{} {}", p, s);
        ans = cmp::max(ans, p - s);
    }
    println!("{}", ans);
}


struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

E - RGB Sequence

http://arc074.contest.atcoder.jp/tasks/arc074_c

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::cmp;

struct Rule {
    left: usize,
    x: usize,
}

fn main() {
    let mut sc = Scanner::new();
    let n = sc.parse::<usize>();
    let m = sc.parse::<usize>();

    let mut rules: Vec<Vec<Rule>> = Vec::new();
    for _ in 0..(n + 1) {
        rules.push(Vec::new());
    }
    for _ in 0..m {
        let l = sc.parse::<usize>();
        let r = sc.parse::<usize>();
        let x = sc.parse::<usize>();
        rules[r].push(Rule { left: l, x: x });
    }

    let mut dp = vec![vec![vec![0;(n+1)];(n+1)];(n+1)];
    dp[0][0][0] = 1;
    let modulo = 1000000007;
    for r in 0..n {
        for g in 0..n {
            for b in 0..n {
                let k = cmp::max(cmp::max(r, g), b);
                if check(&rules, k + 1, g, b) {
                    dp[k + 1][g][b] += dp[r][g][b];
                    dp[k + 1][g][b] %= modulo;
                }
                if check(&rules, r, k + 1, b) {
                    dp[r][k + 1][b] += dp[r][g][b];
                    dp[r][k + 1][b] %= modulo;
                }
                if check(&rules, r, g, k + 1) {
                    dp[r][g][k + 1] += dp[r][g][b];
                    dp[r][g][k + 1] %= modulo;
                }
            }
        }
    }

    let mut ans = 0;
    for i in 0..n {
        for j in 0..n {
            ans += dp[i][j][n];
            ans %= modulo;
            ans += dp[i][n][j];
            ans %= modulo;
            ans += dp[n][i][j];
            ans %= modulo;
        }
    }
    println!("{}", ans);
}

fn check(rules: &Vec<Vec<Rule>>, r: usize, g: usize, b: usize) -> bool {
    let k = cmp::max(cmp::max(r, g), b);
    for rule in &rules[k] {
        let left = rule.left;
        let mut count = 0;
        if r >= left {
            count += 1;
        }
        if g >= left {
            count += 1;
        }
        if b >= left {
            count += 1;
        }
        if count != rule.x {
            return false;
        }
    }
    return true;
}

struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

F - Lotus Leaves

http://arc074.contest.atcoder.jp/tasks/arc074_d

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::cmp;
use std::collections::vec_deque::VecDeque;
use std::i64::MAX;

pub struct Edge {
    pub to: usize,
    pub rev: usize,
    pub cap: i64,
}

struct Dinitz {
    g: Vec<Vec<Edge>>,
    level: Vec<i32>,
    iter: Vec<usize>,
}

impl Dinitz {
    fn new(v: usize) -> Dinitz {
        let mut g: Vec<Vec<Edge>> = Vec::new();
        for _ in 0..v {
            g.push(Vec::new());
        }
        Dinitz {
            g: g,
            level: vec![0;v],
            iter: vec![0;v],
        }
    }

    fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
        let to_len = self.g[to].len();
        let from_len = self.g[from].len();
        self.g[from].push(Edge {
                              to: to,
                              rev: to_len,
                              cap: cap,
                          });
        self.g[to].push(Edge {
                            to: from,
                            rev: from_len,
                            cap: 0,
                        });
    }

    fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 {
        if v == t {
            return f;
        }
        while self.iter[v] < self.g[v].len() {

            let (e_cap, e_to, e_rev);
            {
                let ref e = self.g[v][self.iter[v]];
                e_cap = e.cap;
                e_to = e.to;
                e_rev = e.rev;
            }
            if e_cap > 0 && self.level[v] < self.level[e_to] {
                let d = self.dfs(e_to, t, cmp::min(f, e_cap));
                if d > 0 {
                    {
                        let ref mut e = self.g[v][self.iter[v]];
                        e.cap -= d;
                    }
                    {
                        let ref mut rev_edge = self.g[e_to][e_rev];
                        rev_edge.cap += d;
                    }
                    return d;
                }
            }
            self.iter[v] += 1;
        }

        return 0;
    }

    fn bfs(&mut self, s: usize) {
        let v = self.level.len();
        self.level = vec![-1;v];
        self.level[s] = 0;
        let mut deque = VecDeque::new();
        deque.push_back(s);
        while !deque.is_empty() {
            let v = deque.pop_front().unwrap();
            for e in &self.g[v] {
                if e.cap > 0 && self.level[e.to] < 0 {
                    self.level[e.to] = self.level[v] + 1;
                    deque.push_back(e.to);
                }
            }
        }
    }

    fn max_flow(&mut self, s: usize, t: usize) -> i64 {
        let v = self.level.len();
        let mut flow: i64 = 0;
        loop {
            self.bfs(s);
            if self.level[t] < 0 {
                return flow;
            }
            self.iter = vec![0;v];
            loop {
                let f = self.dfs(s, t, MAX);
                if f == 0 {
                    break;
                }
                flow += f;
            }
        }
    }
}

fn main() {
    let mut sc = Scanner::new();
    let h = sc.parse::<usize>();
    let w = sc.parse::<usize>();
    let n = h + w + 2;
    let source = h + w;
    let sink = source + 1;

    let mut dinitz = Dinitz::new(n);

    let mut si = 0;
    let mut sj = 0;
    let mut ti = 0;
    let mut tj = 0;
    let rows = (0..h).map(|_| sc.parse::<String>()).collect::<Vec<_>>();
    for i in 0..h {
        let row = rows[i].as_bytes();
        for j in 0..w {
            match row[j] {
                b'S' => {
                    si = i;
                    sj = j;
                    dinitz.add_edge(source, i, MAX);
                    dinitz.add_edge(source, h + j, MAX);
                }
                b'T' => {
                    ti = i;
                    tj = j;
                    dinitz.add_edge(i, sink, MAX);
                    dinitz.add_edge(h + j, sink, MAX);
                }
                b'o' => {
                    dinitz.add_edge(i, h + j, 1);
                    dinitz.add_edge(h + j, i, 1);
                }
                _ => {}
            }
        }
    }

    if si == ti || sj == tj {
        println!("-1");
        return;
    }

    let f = dinitz.max_flow(source, sink);
    println!("{}", f);
}

struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}

AtCoder Beginner Contest 010 D - 浮気予防

問題

D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoder

Rust で Dinitz を実装した

コード

use std::fmt::Debug;
use std::io;
use std::io::{Read, Stdin};
use std::str;
use std::str::FromStr;
use std::usize;
use std::cmp;
use std::collections::vec_deque::VecDeque;
use std::i64::MAX;

pub struct Edge {
    pub to: usize,
    pub rev: usize,
    pub cap: i64,
}

struct Dinitz {
    g: Vec<Vec<Edge>>,
    level: Vec<i32>,
    iter: Vec<usize>,
}

impl Dinitz {
    fn new(v: usize) -> Dinitz {
        let mut g: Vec<Vec<Edge>> = Vec::new();
        for _ in 0..v {
            g.push(Vec::new());
        }
        Dinitz {
            g: g,
            level: vec![0;v],
            iter: vec![0;v],
        }
    }

    fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
        let to_len = self.g[to].len();
        let from_len = self.g[from].len();
        self.g[from].push(Edge {
                              to: to,
                              rev: to_len,
                              cap: cap,
                          });
        self.g[to].push(Edge {
                            to: from,
                            rev: from_len,
                            cap: 0,
                        });
    }

    fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 {
        if v == t {
            return f;
        }
        while self.iter[v] < self.g[v].len() {

            let (e_cap, e_to, e_rev);
            {
                let ref e = self.g[v][self.iter[v]];
                e_cap = e.cap;
                e_to = e.to;
                e_rev = e.rev;
            }
            if e_cap > 0 && self.level[v] < self.level[e_to] {
                let d = self.dfs(e_to, t, cmp::min(f, e_cap));
                if d > 0 {
                    {
                        let ref mut e = self.g[v][self.iter[v]];
                        e.cap -= d;
                    }
                    {
                        let ref mut rev_edge = self.g[e_to][e_rev];
                        rev_edge.cap += d;
                    }
                    return d;
                }
            }
            self.iter[v] += 1;
        }

        return 0;
    }

    fn bfs(&mut self, s: usize) {
        let v = self.level.len();
        self.level = vec![-1;v];
        self.level[s] = 0;
        let mut deque = VecDeque::new();
        deque.push_back(s);
        while !deque.is_empty() {
            let v = deque.pop_front().unwrap();
            for e in &self.g[v] {
                if e.cap > 0 && self.level[e.to] < 0 {
                    self.level[e.to] = self.level[v] + 1;
                    deque.push_back(e.to);
                }
            }
        }
    }

    fn max_flow(&mut self, s: usize, t: usize) -> i64 {
        let v = self.level.len();
        let mut flow: i64 = 0;
        loop {
            self.bfs(s);
            if self.level[t] < 0 {
                return flow;
            }
            self.iter = vec![0;v];
            loop {
                let f = self.dfs(s, t, MAX);
                if f == 0 {
                    break;
                }
                flow += f;
            }
        }
    }
}

fn main() {
    let mut sc = Scanner::new();
    let n = sc.parse::<usize>();
    let g = sc.parse::<usize>();
    let e = sc.parse::<usize>();

    let v = n + 1;
    let mut dinitz = Dinitz::new(v);
    for _ in 0..g {
        let p = sc.parse::<usize>();
        dinitz.add_edge(p, n, 1);
    }
    for _ in 0..e {
        let a = sc.parse::<usize>();
        let b = sc.parse::<usize>();
        dinitz.add_edge(a, b, 1);
        dinitz.add_edge(b, a, 1);
    }

    let ans = dinitz.max_flow(0, n);
    println!("{}", ans);
}

struct Scanner {
    stdin: Stdin,
    buf: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            buf: Vec::with_capacity(256),
        }
    }

    fn parse<T: FromStr>(&mut self) -> T
        where <T as FromStr>::Err: Debug
    {
        self.buf.clear();
        let mut it = self.stdin.lock().bytes();
        let mut c = it.next().unwrap().unwrap();
        while c == ' ' as u8 || c == '\n' as u8 {
            c = it.next().unwrap().unwrap();
        }
        while !(c == ' ' as u8 || c == '\n' as u8) {
            self.buf.push(c);
            c = it.next().unwrap().unwrap();
        }
        str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap()
    }
}