CODE FESTIVAL 2017 Final E - Combination Lock

問題

E - Combination Lock

解法

方針としては、

1. 区間を整理しやすいように文字列の長さを偶数にする。
2. 区間の整理をめっちゃ頑張る
3. 端から区間を見ていけば良いだけの状態になったら imos 法で順番に処理していき、ダメだったら NO

文字列の長さを偶数にする

文字列の長さが奇数だった場合、中央の文字に対する操作が何回行われても結果に影響はないので、中央の文字とそれに対する操作を削除して考えても変わりません。よって、入力を整理して、文字列の長さは必ず偶数であるとして考えます。

中央を覆う区間に対する操作

例えば、長さ 8 の文字列の [1, 5] 文字目に対する操作があった時、回分にするためには 4 文字目と 5 文字目を同じ文字にする必要がありますが、この操作によって 4 文字目と 5 文字目の差は変わらないため、この操作による 4 文字目と 5 文字目への影響は無視できます。よって、長さ 8 の文字列の [1, 5] 文字目に対する操作は [1, 3] 文字目に対する操作と考えることができます。

このように中央を越える区間に対する操作は、中央を挟んだ無視できる区間への影響を無視することで、より小さい区間への操作に置き換えることができます。これによって全ての操作を、中央から見て右側か左側のどちらかに収まるものとして考えることができます。

片側に寄せる

ある区間に対する操作を 26 回行うのと 0 回行うのは同じです。よってある区間に対する操作を 25 回行うのと -1 回行うのは同じことがわかります。中央から見て右側にある区間に対する操作は、中央から見て対称な左側の区間に対する操作に置き換えられます。例えば、長さ 8 の文字列について、 [6, 8] 文字目に対する操作を 1 回行うことは、 [1, 3] 文字目に対する操作を -1 回行うのと同じです。

このことから、全ての区間を左側に集め、左側に対して操作を行うことで右側の文字列を作って行く問題と考えることができます。

区間の整理

片方の端が同じ値である2つの区間に対する各操作は、区間が被らない操作として考えることが出来ます。例えば、区間 [a, b] に対する操作 1 と、区間 [a, b+k] に対する操作 2 があって操作 1 を m 回行って操作 2 を n 回行うのは、区間 [a, b] に対する操作を 2m 回行って、区間 [b+1, b+k] に対する操作を n 回行うのと同じです。

よって上の図のように 4 つの区間がある時、下の図のようにそれぞれが被らない区間の操作に置き換えることができます。

累積和

imos 法

コード

use std::io;
use std::cmp;
use std::collections::BTreeMap;
use std::collections::VecDeque;
use std::collections::BTreeSet;

fn main() {
    let s = read_line().trim().to_owned();
    let n = s.len();
    let methods = read_values::<usize>()[0];
    let mut segments = Vec::new();
    for _ in 0..methods {
        let input = read_values::<usize>();
        let mut l: usize = input[0] - 1;
        let mut r: usize = input[1] - 1;
        let half = n >> 1;

        if (n & 1) == 1 {
            // 文字列の長さが奇数の時、中央の文字を削除するために区間を整理する
            if l == half && r == half {
                // 中央の 1 文字のみに対する操作は意味がないので無視する
                continue;
            }

            // 中央の文字を削除する分だけ 1 文字分ずらす
            if half < l {
                l -= 1;
            }
            if half <= r {
                r -= 1;
            }
        }
        segments.push((l, r));
    }

    // 長さが奇数の時、中央の文字を削除する
    let s = {
        let t = s.bytes().map(|c| {
            c - "a".bytes().next().unwrap()
        }).collect::<Vec<_>>();
        let mut polished = Vec::new();
        for i in 0..n {
            if (n & 1) != 1 || (n >> 1) != i {
                polished.push(t[i]);
            }
        }
        polished
    };

    // 新しい文字列の長さ
    let n = s.len();

    // 区間の左端をキーにして、左端の値の set を持つ
    let mut right_map: BTreeMap<usize, BTreeSet<usize>> = BTreeMap::new();
    for x in segments.iter() {
        let (l, r) = *x;

        let half = n >> 1;
        let (l, r) = if r < half {
            // 中央から見て左側の区間はそのまま使う
            (l, r)
        } else if l >= half {
            // 中央から見て右側の区間は左側に移す
            (n - 1 - r, n - 1 - l)
        } else {
            // 中央を越える区間を整理する
            let right_side = r - (half - 1);
            let left_side = half - l;

            if right_side > left_side {
                // 中央から見て右のほうが大きい区間
                let tmp_l = half + left_side;
                (n - 1 - r, n - 1 - tmp_l)
            } else if right_side == left_side {
                // 中央から見て対称な区間に対する操作は結果に影響がないので無視する
                continue;
            } else {
                // 中央から見て左のほうが大きい区間
                (l, half - 1 - right_side)
            }
        };

        if !right_map.contains_key(&l) {
            right_map.insert(l, BTreeSet::new());
        }
        right_map.get_mut(&l).unwrap().insert(r);
    }

    // 区間の右端をキーとした map も作る
    let mut left_map = BTreeMap::new();
    for (left, rights) in right_map.iter() {
        for r in rights.iter() {
            if !left_map.contains_key(&(r + 1)) {
                left_map.insert(r + 1, BTreeSet::new());
            }
            left_map.get_mut(&(r + 1)).unwrap().insert(*left);
        }
    }

    // 区間を整理する
    let mut merged_map = BTreeMap::new();
    for left in 0..n {
        // left を左端に持つ区間がなければスルー
        if !right_map.contains_key(&left) {
            continue;
        }

        let mut lefts = BTreeSet::new();

        let mut queue = VecDeque::new();
        queue.push_back(left);
        let mut right = left;
        while !queue.is_empty() {
            let v = queue.pop_front().unwrap();
            lefts.insert(v);

            if let Some(set) = right_map.remove(&v) {
                for r in set.iter() {
                    queue.push_back(*r + 1);
                    right = cmp::max(right, *r + 1);
                }
            }

            if let Some(set) = left_map.remove(&v) {
                for l in set.iter() {
                    queue.push_back(*l);
                }
            }
        }
        lefts.insert(right);

        let list = lefts.iter().map(|x| x.clone()).collect::<Vec<_>>();
        for i in 0..(list.len() - 1) {
            let cur = list[i];
            let next = list[i + 1];
            merged_map.insert(cur, next);
        }
    }

    let mut sum = vec![0; n / 2 + 1];
    let mut cur = 0;
    for i in 0..(n / 2) {
        cur += sum[i];
        let from = (s[i] as i64 + cur) % 26;
        let to = (s[n - 1 - i] as i64) % 26;
        let add = (to + 26 - from) % 26;
        if add == 0 {
            continue;
        }
        if !merged_map.contains_key(&i) {
            println!("NO");
            return;
        }
        let x = *merged_map.get(&i).unwrap();
        cur += add;
        sum[x] -= add;
    }
    println!("YES");
}

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}

AtCoder Problems を支える技術

adventar.org

はじめに

AtCoder Problems というサービスを作っています。最近作り直しています。

http://beta.kenkoooo.com/atcoder/

これは AtCoder の提出を全部クロールして、一覧で見れるようにしたものです。最近は機能が増えすぎていますが・・・

ソースコードも公開しています。このプログラムの中でどんなことをしているのかを書いていきたいと思います。競技プログラミングはそんなに関係ないです。

github.com

スクレイパー

Scala で書いています。ScalaScraper でクロールもスクレイピングもやってくれるので、それに任せています。

やっていることは以下のとおりです。

• コンテスト一覧をクロールして DB に入れる。
• DB のコンテストを順番に見ていき、そのコンテストの問題をクロールして DB に入れる。
• コンテストを順番に見ていき、そのコンテストの提出をクロールして DB に入れる。全てクロールすると多すぎるので、既に DB に入っている提出が出るまで最新の方から見てクロールする。
• クロール漏れするかもしれないので 1 日に 4 回だけ全ての提出をクロールする。

集計

ユーザーが問題を解いた数や、各問題の正解者数、実行速度最速の提出やコード長が最短の提出などを集計しています。これらの値は API でリクエストが来ますが、来るたびに計算していると遅いので予め計算しておきます。やっていることは SQL クエリを投げるだけです。ユーザーの提出をできるだけ早めに反映するため 5 分ごとくらいで実行しています。

API サーバー

フロントエンドからは JSON で出力を返す API を叩いています。API サーバーも Scala で書かれていて、サーバーは Akka HTTP で、SQL 部分は ScalikeJDBC を使って書いています。

可能ならレスポンスを gzip で返したり、ETag を見て変更がなければ 304 を返してキャッシュを使ってもらったりなどの工夫がありますが、このへんは Akka HTTP がよしなにやってくれています。

フロントエンド

フロントエンドは TypeScript と React で書いています。JS 業界は gulp だの bower だの browserify だの webpack だの mocha だの chai だの無限にインストールしなければならないイメージでしたが、TypeScript のチュートリアルどおりにやったところ、トランスパイルは webpack 、テストは jest だけで十分でした。

TypeScript は VSCode でプラグイン無しで快適に書けるのでとても良いです。素の JavaScript を書くことは一生ないでしょう。

得点の予測

AtCoder の rated のコンテストでは各問題に得点が設定されていますが、そうでない問題は rated の問題と違う基準で得点が設定されているので、推定してみることにしました。

AtCoder で 300 問以上解いているユーザーをヘビーユーザーとして、ヘビーユーザーの各問題についての「解けた」「提出したが不正解だった」「提出していない」を特徴量にして、思考停止 XGBoost で predict しました。

AtCoder で問題を解くと、ヘビーユーザーとして特徴量作成に使われたり、各問題の特徴が正確になったりして、反映される予測値も正確になっていくはずなので、みなさん問題を解きましょう。

まとめ

Scala はいい。TypeScript もまあいい。

フィボナッチヒープ

adventar.org

フィボナッチヒープとは

この記事ではヒープは最小値を求めるものとします。

フィボナッチヒープとは、フィボナッチ数の性質をうまく使ってならし計算量で高い性能を持ったヒープです。

ヒープ	フィボナッチヒープ	二分ヒープ
最小値の削除	ならし O(log n)	O(log n)
値の追加	O(1)	O(log n)

値の追加が非常に多く、最小値の削除が非常に少ない場合は、二分ヒープより速くなることもあるかもしれません。他にもヒープ同士をマージできたり、ヒープ内の値の減少ができたりしますが、この記事では扱いません。すみません。

構造

図は wikipedia からの引用です。

フィボナッチヒープは、下図のようにいくつかのツリーを並べたような構造を持っています。ツリーの各ノードに、ヒープ内の値が入っています。各ツリーでは、上の根に近いほうが小さい値になるようになっています。このとき、ヒープ内の値の最小値は 1 で、実際に最小値のポインタも 1 のノードを指しています。

次に、最小値を削除 (pop) することを考えます。先ほど最小値とされていた 1 のノードが削除され、1 を根としたツリーが分解し、新たに 3, 4, 7 をそれぞれ根とした新しいツリーができます。新しいツリーたちはヒープのツリーのリストに入ります。

今度はツリーのリストを整理します。ツリーを順番に見ていき、以下の操作を施します。

見ているツリーの根の次数を i とする。

• 次数 i のツリーとして登録されているツリーが他になければ、今見ているツリーを次数 i のツリーとして登録する。
• 次数 i のツリーとして登録されているツリーが既にある場合、登録されているツリーの根の値と、今見ているツリーの根の値を比べ、大きい方の根を小さい方の根の下に接続する。この操作で次数 i の根を持ったツリーが 2 つ消え、次数 i+1 を持ったツリーが新たに生成される。

この操作を全て終えると、ヒープ内のツリーの根の次数が全て相異なるようになります。（後述しますが、これは重要なことです）
最後に残っているツリーの根をもう一度全て見て、最小の値を持つ根を最小値として指すようにします。

計算量

ツリーのリストを走査するときにノードを参照する回数は、新たに追加されたノードの数 + 最小値のノードの子ノードの数であるが、新たに追加されたノードの数はノードを追加する計算量に含めるとして、最小値のノードの子ノードの数、すなわち最小値のノードの次数が となることを示す。

補題 1

あるノード x について、 x の次数を と表す。 として、x の k 個の子ノードをそれぞれ として、この順番で x の子として接続されたとする。この時 かつ である。

証明

は自明。

に対して を x に接続する時、 は既に x の子ノードとして接続されている。つまり が成り立っている。
ここで が x に子として接続されるためには が成り立っていなければならない。よって が成り立つ。
値が減少するバージョンではまだやることがありますが、とりあえずこれで が成り立ったのでこのまま行きます。

補題 2

k 番目のフィボナッチ数を と表す。この時 とする。k (k > 2) 番目のフィボナッチ数 の漸化式は である。

この時、任意の について が成り立つ。

証明

帰納法で示す。

k=0 のとき成り立つ。

が成り立つことを仮定すると、

補題 3

を の正の解とする。

全ての整数 に対して、 k+2 番目のフィボナッチ数 は を満たす。

証明

帰納法で示す。

のとき
のとき

を仮定すると

補題 4

ノード x について とする。 を、ノード x を根とする部分木の頂点数とすると、 が成り立つ。

証明

次数 k のあるノード z の が取りうる最小値を とする。 である。また、 は k について単調増加である。z の k 個の子ノードを とすると、

(補題 1 より であり、 は単調増加なので である)

を仮定すると

よって

系 5

要素数 n のフィボナッチヒープに属する任意の頂点の最大次数 は である。

証明

要素数 n のフィボナッチヒープの任意のノードを x とし、 とする。
だから

よって任意の頂点の次数は で抑えられる。

実装

import java.util.ArrayList;
import java.util.List;

public class LongFibonacciHeap {

  class Node {

    long key = -1;
    int degree = 0;
    Node p = null;
    Node right = null;
    Node left = null;
    List<Node> children = new ArrayList<>();
    boolean mark = false;
  }

  private Node min = null;
  private int size = 0;

  public void insert(Node x) {
    if (min == null) {
      min = x;
      x.right = x;
      x.left = x;
    } else {
      addRoot(x);
      if (x.key < min.key) {
        min = x;
      }
    }
    size++;
  }

  /**
   * Add node x to linked root list
   *
   * @param x node to add
   */
  private void addRoot(Node x) {
    if (min == null) {
      min = x;
      min.right = x;
      min.left = x;
      return;
    }

    Node l = min.left;
    l.right = x;
    min.left = x;

    x.right = min;
    x.left = l;
  }

  /**
   * Remove node x from linked root list
   *
   * @param x node to remove
   */
  private void removeRoot(Node x) {
    Node r = x.right;
    Node l = x.left;
    r.left = l;
    l.right = r;
  }

  /**
   * merge h1 and h2 to generate new one
   *
   * @param h1 heap1 to merge
   * @param h2 heap2 to merge
   * @return merged heap
   */
  public static LongFibonacciHeap unite(LongFibonacciHeap h1, LongFibonacciHeap h2) {
    LongFibonacciHeap h = new LongFibonacciHeap();
    h.min = h1.min;
    if ((h1.min == null) || (h2.min != null && h2.min.key < h1.min.key)) {
      h.min = h2.min;
    }

    // link h1's root list & h2's root list
    if (h1.min != null && h2.min != null) {
      Node n1 = h1.min;
      Node n2 = h2.min;
      Node n1l = n1.left;
      Node n2r = n2.right;

      n1.left = n2;
      n2.right = n1;
      n2r.left = n1l;
      n1l.right = n2r;
    }

    h.size = h1.size + h2.size;
    return h;
  }

  public Node extractMinNode() {
    Node z = min;
    if (z == null) {
      return null;
    }

    for (Node child : z.children) {
      addRoot(child);
      child.p = null;
    }
    removeRoot(z);
    if (z == z.right) {
      min = null;
    } else {
      min = z.right;
      consolidate();
    }
    size--;
    return z;
  }

  public int size() {
    return size;
  }

  private void consolidate() {
    //list up rooted nodes
    ArrayList<Node> rootList = new ArrayList<>();
    rootList.add(min);
    while (rootList.get(rootList.size() - 1).right != rootList.get(0)) {
      Node lastRight = rootList.get(rootList.size() - 1).right;
      rootList.add(lastRight);
    }

    Node[] rootOfDegree = new Node[size + 1];
    for (Node parent : rootList) {
      int d = parent.degree;
      while (rootOfDegree[d] != null) {
        Node child = rootOfDegree[d];
        if (parent.key > child.key) {
          Node t = parent;
          parent = child;
          child = t;
        }
        link(child, parent);
        rootOfDegree[d] = null;
        d++;
      }
      rootOfDegree[d] = parent;
    }

    min = null;
    for (Node node : rootOfDegree) {
      if (node == null) {
        continue;
      }

      if (min == null) {
        node.right = node;
        node.left = node;
        min = node;
      } else {
        addRoot(node);
        if (node.key < min.key) {
          min = node;
        }
      }
    }
  }

  private void link(Node child, Node parent) {
    removeRoot(child);
    parent.degree++;
    parent.children.add(child);
    child.p = parent;
    child.mark = false;
  }

  public void insert(long key) {
    Node x = new Node();
    x.key = key;
    insert(x);
  }
}

フィボナッチヒープを使ってダイクストラやってみた

問題

atcoder.jp

コード

use std::cmp;
use std::collections::HashMap;

const INF: u64 = std::u64::MAX / 2;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let m: usize = sc.read();
    let s = sc.read::<usize>() - 1;
    let t = sc.read::<usize>() - 1;

    let mut graph = vec![vec![]; n];
    for _ in 0..m {
        let a = sc.read::<usize>() - 1;
        let b = sc.read::<usize>() - 1;
        let c = sc.read::<u64>();
        graph[a].push((b, c));
        graph[b].push((a, c));
    }

    let dist1 = dijkstra(s, &graph);
    let dist2 = dijkstra(t, &graph);
    for i in 0..n {
        if dist1[i] == dist2[i] && dist1[i] != INF {
            println!("{}", i + 1);
            return;
        }
    }
    println!("-1");
}

fn dijkstra(s: usize, graph: &Vec<Vec<(usize, u64)>>) -> Vec<u64> {
    let n = graph.len();
    let mut dist = vec![INF; n];
    dist[s] = 0;
    let mut heap = FibonacciHeap::new(cmp::min);
    heap.push((0, s));
    while let Some((_, v)) = heap.pop() {
        for &(next, cost) in graph[v].iter() {
            if dist[next] > dist[v] + cost {
                dist[next] = dist[v] + cost;
                heap.push((dist[next], next));
            }
        }
    }
    dist
}

fn store_to_map<T, F>(map: &mut HashMap<usize, Node<T>>, mut node: Node<T>, ordering: F)
where
    T: Copy + PartialEq,
    F: Fn(T, T) -> T,
{
    let d = node.children.len();
    match map.remove(&d) {
        Some(mut other) => {
            let node = if (ordering)(node.key, other.key) == node.key {
                node.children.push(other);
                node
            } else {
                other.children.push(node);
                other
            };
            store_to_map(map, node, ordering);
        }
        None => {
            map.insert(d, node);
        }
    }
}

pub struct FibonacciHeap<T, F> {
    pub nodes: Vec<Node<T>>,
    min_index: usize,
    ordering: F,
}

impl<T, F> FibonacciHeap<T, F>
where
    T: Copy + PartialEq,
    F: Fn(T, T) -> T + Copy,
{
    pub fn new(ordering: F) -> FibonacciHeap<T, F> {
        FibonacciHeap {
            nodes: Vec::new(),
            min_index: 0,
            ordering: ordering,
        }
    }
    pub fn push(&mut self, x: T) {
        let node = Node::new(x);
        self.nodes.push(node);
        let cur_min = self.nodes[self.min_index].key;
        if (self.ordering)(cur_min, x) == x {
            self.min_index = self.nodes.len() - 1;
        }
    }
    pub fn pop(&mut self) -> Option<T> {
        let mut map: HashMap<usize, Node<T>> = HashMap::new();
        let mut popped = None;

        let mut nodes = Vec::new();
        std::mem::swap(&mut self.nodes, &mut nodes);
        for (i, node) in nodes.into_iter().enumerate() {
            if i == self.min_index {
                popped = Some(node.key);
                for node in node.children.into_iter() {
                    store_to_map(&mut map, node, self.ordering);
                }
            } else {
                store_to_map(&mut map, node, self.ordering);
            }
        }

        self.nodes = map.into_iter().map(|(_, node)| node).collect();
        if !self.nodes.is_empty() {
            let mut min = self.nodes[0].key;
            for i in 0..self.nodes.len() {
                if (self.ordering)(min, self.nodes[i].key) == self.nodes[i].key {
                    min = self.nodes[i].key;
                }
            }

            self.min_index = self
                .nodes
                .iter()
                .enumerate()
                .find(|&(_, node)| node.key == min)
                .unwrap()
                .0;
        } else {
            self.min_index = 0;
        }
        popped
    }
}

#[derive(Debug)]
pub struct Node<T> {
    pub key: T,
    pub children: Vec<Node<T>>,
}

impl<T> Node<T> {
    fn new(x: T) -> Node<T> {
        Node {
            key: x,
            children: Vec::new(),
        }
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

リクルートコミュニケーションズを退職しました

adventar.org

豆知識

この記事のタイトルでググると、まともな記事が出てきます。

退職しました

20 ヶ月ほど勤務したリクルートコミュニケーションズ (RCO) を退職しました。RCO ではウェブ広告リアルタイム配信チームで、主に高速化を頑張りました。かなり面白かったです。また、 2 年目に並行して始めた、流通を線形計画問題に落とし込んで解くという仕事も割と面白かったです。

自由な雰囲気で、給料も良く、良い同僚に恵まれもしましたが、若いうちに色んな環境を経験しておきたかったのと、上司いわく「うちは出入り自由なんで」とのことだったので、気楽な気持ちで退職しました。

これが罠で、12月末で退職すれば良かったものを、何故かうっかり 11 月末で退職してしまったがために、12 月のボーナスを貰い損ねてしまいました。さすがに適当に退職し過ぎた・・・

まとめ

積極的な理由がないなら、賞与の後に退職すると良い。

AOJ 2829 Room Assignment

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2829

解法

JAG の wiki に分かりやすい解説があります。

2017/Practice/模擬国内予選/講評 - ACM-ICPC Japanese Alumni Group

場合分けとしては以下の 3 つです

• 長さ 3 以上の閉路が存在する場合は 0
• 閉路を潰した時に、全てのツリーの葉の数が 2 以下でなければ 0
• 長さ 3 以上の弱連結成分が存在しない時
• それ以外

コード

import java.util.Scanner

import scala.collection.mutable.ArrayBuffer

object Main {
  private val Mod = (1e9 + 7).toInt

  // 階乗を前計算しておく
  private val Fact = {
    var cur = 1L
    for (i <- 0 to 200000) yield {
      if (i == 0) {
        1
      } else {
        cur = (cur * i) % Mod
        cur
      }
    }
  }

  // 2 の累乗を前計算しておく
  private val Pow = {
    val pow = new Array[Int](200000)
    pow(0) = 1
    for (i <- 1 until pow.length) pow(i) = pow(i - 1) * 2 % Mod
    pow
  }

  def main(args: Array[String]): Unit = {
    val in = new Scanner(System.in)
    while (true) {
      val n = in.nextInt()
      if (n == 0) {
        return
      }
      val a = for (_ <- 0 until n) yield {
        in.nextInt() - 1
      }
      println(solve(a.toArray))
    }
  }

  // 長さ 3 以上の閉路が存在しないことを確認する
  def cycleCheck(graph: IndexedSeq[Seq[Int]]): Boolean = {
    val cmp = StronglyConnectedComponents.decompose(graph)
    var map = Map[Int, Int]()
    cmp.foreach { c => map += (c -> (map.getOrElse(c, 0) + 1)) }
    map.values.forall(count => count <= 2)
  }

  // 全ての弱連結成分がパスが閉路を潰すとパスになることを確認する
  def pathCheck(graph: IndexedSeq[Seq[Int]]): Boolean = {
    val uf = new UnionFind(graph.size)
    for {
      i <- graph.indices
      j <- graph(i)
    } uf.unite(i, j)

    var map = Map[Int, Int]()
    for {
      i <- graph.indices
      if graph(i).isEmpty
    } {
      val count = map.getOrElse(uf.find(i), 0)
      map += (uf.find(i) -> (count + 1))
    }
    map.values.forall(count => count <= 2)
  }

  // 要素数 2 の弱連結成分の数と、要素数 3 以上の弱連結成分の数を算出する
  def getSize(array: Array[Int]): (Int, Int) = {
    val N = array.length
    val uf = new UnionFind(N)
    for (i <- array.indices) uf.unite(i, array(i))
    val sizes = for {
      i <- 0 until N
      if i == 0 || !uf.isSame(i, 0)
    } yield {
      if (i == 0) {
        uf.partialSizeOf(i)
      } else {
        val s = uf.partialSizeOf(i)
        uf.unite(i, 0)
        s
      }
    }

    var three = 0
    var two = 0
    sizes.foreach(size => if (size == 2) {
      two += 1
    } else {
      three += 1
    })

    (two, three)
  }

  def solve(parent: Array[Int]): Int = {
    val n = parent.length
    val combination = new Combination(n + 1, Mod)

    val graph = parent.indices.map(i => new ArrayBuffer[Int]())
    parent.indices.foreach(i => graph(parent(i)).append(i))

    if (cycleCheck(graph) && pathCheck(graph)) {
      val (two, three) = getSize(parent)
      if (three == 0) {
        // 長さ 3 以上の弱連結成分が存在しないとき
        var cur: Long = ((two + 2) / 2) % Mod
        cur = cur * Pow(two) % Mod
        cur = cur * Fact(two) % Mod
        cur.toInt
      } else {
        var ans = 0L
        for (i <- 0 to math.min(two + three - 2, two)) {
          var cur = combination.get(two + three - i - 2, two - i).toLong
          cur = cur * Fact(two) % Mod
          cur = cur * Fact(three) % Mod
          cur = cur * Pow(two + three) % Mod
          cur = cur * (two + three - i - 1) % Mod
          cur = cur * ((i + 2) / 2) % Mod
          ans = (ans + cur) % Mod
        }
        for (i <- 0 to math.min(two + three - 1, two)) {
          var cur = combination.get(two + three - i - 1, two - i).toLong
          cur = cur * Fact(two) % Mod
          cur = cur * Fact(three) % Mod
          cur = cur * Pow(two + three) % Mod
          cur = cur * ((i + 2) / 2) % Mod
          ans = (ans + cur * 2) % Mod
        }
        ans.toInt
      }
    } else {
      0
    }
  }

  class UnionFind(n: Int) {
    private val parent = (0 until n).toArray
    private val sizes = Array.fill[Int](n)(1)
    private var _size = n

    def find(x: Int): Int = {
      if (x == parent(x)) {
        x
      } else {
        parent(x) = find(parent(x))
        parent(x)
      }
    }

    def unite(a: Int, b: Int): Boolean = {
      val fa = find(a)
      val fb = find(b)
      if (fa == fb) {
        false
      } else {
        val (x, y) = if (sizes(fa) >= sizes(fb)) {
          (fa, fb)
        } else {
          (fb, fa)
        }

        parent(y) = x
        sizes(x) += sizes(y)
        sizes(y) = 0

        _size -= 1
        true
      }
    }

    def isSame(x: Int, y: Int): Boolean = find(x) == find(y)

    def partialSizeOf(x: Int): Int = sizes(find(x))

    def size(): Int = _size
  }

  class Combination(max: Int, mod: Int) {
    private val inv = new Array[Long](max + 1)
    private val fact = new Array[Long](max + 1)
    private val invFact = new Array[Long](max + 1)
    inv(1) = 1
    for (i <- 2 to max) inv(i) = inv(mod % i) * (mod - mod / i) % mod
    fact(0) = 1
    invFact(0) = 1
    for (i <- 1 to max) fact(i) = (fact(i - 1) * i) % mod
    for (i <- 1 to max) invFact(i) = (invFact(i - 1) * inv(i)) % mod

    /**
      * get nCm
      */
    def get(n: Int, m: Int): Int = {
      if (n < m) {
        0
      } else fact(n) * invFact(m) % mod * invFact(n - m) % mod
    }.toInt
  }

  object StronglyConnectedComponents {
    def decompose(graph: IndexedSeq[Seq[Int]]): Array[Int] = {
      val vs = new ArrayBuffer[Int]()
      val V = graph.size
      val cmp = new Array[Int](V)

      val rg = graph.indices.map(_ => new ArrayBuffer[Int]())
      for {
        from <- graph.indices
        to <- graph(from)
      } rg(to).append(from)

      var used = Array.fill[Boolean](V)(false)
      var stack = List[Int]()
      val added = Array.fill[Boolean](V)(false)
      for {
        i <- used.indices
        if !used(i)
      } {
        stack = i :: stack
        while (stack.nonEmpty) {
          val v = stack.head
          used(v) = true
          var pushed = false
          for {
            u <- graph(v).reverse
            if !used(u)
          } {
            stack = u :: stack
            pushed = true
          }
          if (!pushed) {
            stack = stack.tail
            if (!added(v)) {
              vs.append(v)
              added(v) = true
            }
          }
        }
      }

      used = Array.fill[Boolean](V)(false)
      var k = 0
      for {
        i <- vs.reverse
        if !used(i)
      } {
        stack = i :: stack
        used(i) = true
        cmp(i) = k
        while (stack.nonEmpty) {
          val v = stack.head
          var pushed = false
          for {
            u <- rg(v)
            if !used(u)
          } {
            used(u) = true
            cmp(u) = k
            stack = u :: stack
            pushed = true
          }
          if (!pushed) {
            stack = stack.tail
          }
        }
        k += 1
      }
      cmp
    }
  }

}

AOJ 3019 Picnic

問題

Picnic | Aizu Online Judge

解法

ワーシャルフロイド→巡回セールスマン→半分全列挙→個数制約付きナップサック

コード

import java.util

import scala.io.StdIn
import scala.util.Try

object Main extends App {
  val INF: Long = 1e15.toLong
  val (n, x, y) = {
    val in = StdIn.readLine().split(" ").map(_.toInt)
    (in(0), in(1), in(2))
  }
  val sweets = for (_ <- 0 until n) yield {
    val k = StdIn.readLine().toInt
    for (_ <- 0 until k) yield {
      val in = StdIn.readLine().split(" ").map(_.toInt)
      Sweet(in(0), in(1), in(2))
    }
  }

  val dist = for (_ <- 0 until n) yield StdIn.readLine().split(" ").map(_.toLong)
  for (k <- 0 until n) for (i <- 0 until n) for (j <- 0 until n) dist(i)(j) = math.min(dist(i)(j), dist(i)(k) + dist(k)(j))

  val cost = Array.fill[Long](1 << n, n)(INF)
  cost(0)(0) = 0
  for (mask <- 0 until 1 << n)
    for (cur <- 0 until n)
      for (next <- 0 until n)
        if ((mask & (1 << next)) == 0) {
          val add = dist(cur)(next)
          cost(mask | (1 << next))(next) = math.min(cost(mask | (1 << next))(next), cost(mask)(cur) + add)
        }


  def knapsack(dp: Array[Long], available: Seq[Sweet]): Unit = {
    for {
      sweet <- available
      money <- 0 until sweet.price
    } {
      val deque = new util.ArrayDeque[(Int, Long)]()
      var num = 0
      while (num * sweet.price + money <= y) {
        val next = num * sweet.price + money


        val v = dp(next) - num * sweet.value
        while (!deque.isEmpty && deque.peekLast()._2 <= v) deque.pollLast()
        deque.addLast((num, v))

        dp(next) = deque.peekFirst()._2 + num * sweet.value
        if (deque.peekFirst()._1 == num - sweet.remain) deque.pollFirst()

        num += 1
      }
    }
    for (i <- 1 until dp.length) dp(i) = math.max(dp(i), dp(i - 1))
  }


  val prefix = n / 2
  val suffix = n - prefix

  val prefixDp = Array.fill[Long](1 << prefix, y + 1)(0)
  for (prefixMask <- 0 until 1 << prefix) {
    val mask = prefixMask << suffix
    val dp = prefixDp(prefixMask)
    val available = for {
      i <- 0 until n
      if (mask & (1 << i)) != 0
      sweet <- sweets(i)
    } yield sweet
    knapsack(dp, available)
  }

  val suffixDp = Array.fill[Long](1 << suffix, y + 1)(0)
  for (mask <- 0 until 1 << suffix) {
    val dp = suffixDp(mask)
    val available = for {
      i <- 0 until n
      if (mask & (1 << i)) != 0
      sweet <- sweets(i)
    } yield sweet
    knapsack(dp, available)
  }
  var ans = 0L
  for (mask <- 0 until 1 << n) {
    val suffixMask = mask & ((1 << suffix) - 1)
    val prefixMask = mask >> suffix
    val travelingCost = (for (last <- 0 until n) yield {
      cost(mask)(last) + dist(last)(0)
    }).min
    val money = math.min(x - travelingCost, y).toInt
    for (prefixMoney <- 0 to money) {
      val suffixMoney = money - prefixMoney
      val value = prefixDp(prefixMask)(prefixMoney) + suffixDp(suffixMask)(suffixMoney)
      ans = math.max(ans, value)
    }
  }
  println(ans)
}

case class Sweet(price: Int, value: Int, remain: Int)

AIM Tech Round 4 (Div. 1) D. Dynamic Shortest Path

問題

http://codeforces.com/contest/843/problem/D

解法

最初にダイクストラで距離を求めておき、各クエリごとにダイクストラで追加で増えた分の距離を計算して加算していく。各クエリごとに距離は 1 しか増えないので、キューを距離の数だけ用意すれば、クエリごとのダイクストラの計算量は になる。

よって、最初のダイクストラが クエリごとのダイクストラが全部で となるので、全体で で とかなので、 10 秒あれば間に合う（いいえ）。

コード

use std::io;
use std::str;
use std::usize;
use std::collections::BinaryHeap;
use std::cmp::Ordering;
use std::collections::BTreeMap;
use std::collections::VecDeque;
use std::cmp;

static INF: i64 = 1 << 60;
static MAX_REQ: usize = 2000000;

fn main() {
    let start = 0;
    let (n, m, q) = {
        let v = read_values::<usize>();
        (v[0], v[1], v[2])
    };

    let mut graph: Vec<Vec<Edge>> = vec![Vec::new(); n];
    let mut edges = Vec::new();
    for _ in 0..m {
        let (from, to, cost) = {
            let v = read_values::<usize>();
            (v[0] - 1, v[1] - 1, v[2] as i64)
        };
        edges.push((from, graph[from].len()));
        graph[from].push(Edge { to: to, cost: cost });
    }

    let mut shortest_dist = dijkstra(start, &graph);
    let mut deque = vec![VecDeque::new(); MAX_REQ];
    let mut add = vec![INF; n];

    let mut modify_queries = Vec::new();

    for _ in 0..q {
        let queries = read_values::<usize>();
        if queries[0] == 1 {
            let to = queries[1] - 1;
            let num = modify_queries.len();

            for edge_idx in &modify_queries {
                let (from, idx): (usize, usize) = edges[*edge_idx];
                unsafe { graph[from].get_unchecked_mut(idx).cost += 1; }
            }
            modify_queries.clear();

            add[start] = 0;
            deque[0].push_back(start);

            for dist in 0..(num + 1) {
                while !deque[dist].is_empty() {
                    let cur = deque[dist].pop_front().unwrap();
                    if add[cur] != dist as i64 {
                        continue;
                    }
                    for e in &graph[cur] {
                        let d = shortest_dist[cur] + add[cur] - shortest_dist[e.to] + e.cost;
                        if d as usize <= num && add[e.to] > d {
                            add[e.to] = d;
                            deque[d as usize].push_back(e.to);
                        }
                    }
                }
            }

            for i in 0..n {
                shortest_dist[i] = cmp::min(shortest_dist[i] + add[i], INF);
                add[i] = INF;
            }

            if shortest_dist[to] >= INF {
                println!("-1");
            } else {
                println!("{}", shortest_dist[to]);
            }
        } else {
            let num = queries[1];
            for i in 0..num { modify_queries.push(queries[i + 2] - 1); }
        }
    }
}

fn dijkstra(start: usize, graph: &Vec<Vec<Edge>>) -> Vec<i64> {
    let n = graph.len();
    let mut heap = BinaryHeap::<Edge>::new();
    heap.push(Edge { to: start, cost: 0 });
    let mut dist = vec![INF; n];
    dist[start] = 0;
    while !heap.is_empty() {
        let p: Edge = heap.pop().unwrap();
        for e in &graph[p.to] {
            if dist[e.to] > e.cost + dist[p.to] {
                dist[e.to] = e.cost + dist[p.to];
                heap.push(Edge { to: e.to, cost: dist[e.to] });
            }
        }
    }
    dist
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct Edge {
    to: usize,
    cost: i64,
}

impl Ord for Edge {
    fn cmp(&self, other: &Edge) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}

impl PartialOrd for Edge {
    fn partial_cmp(&self, other: &Edge) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T>
    where T: std::str::FromStr,
          T::Err: std::fmt::Debug
{
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}