AtCoder Regular Contest 102 D - All Your Paths are Different Lengths

問題

atcoder.jp

解法

頂点 v から v+1 へ、長さ 0 の辺と、長さ  2^v の辺を張る。これによって、 0, 1, 2, 3, ... , 2^{(n-1)}-1 の長さのパスが存在することになる。

次に、頂点を  n-2, n-3, ..., 0 の順番で見ていく。頂点 0 から頂点 v へは  0, 1, 2, ... , 2^v-1 の長さのパスが存在するので、頂点 v から頂点 n-1 へ長さ t の辺を張ると、新たに  t, t+1, t+2, ... , t+2^v-1 の長さのパスが追加されることになる。そこで  t=l-2^v として辺を張ることで、  l-2^v, l-2^v+1, ... , l-1 のパスを追加することが出来る。これを繰り返していき、  2^{(n-1)}, ... , l-1 のパスを全て加えることができれば良い。

コード

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let mut l: usize = sc.read();

    let mut r = 0;
    while (1 << (r + 1)) <= l {
        r += 1;
    }

    let n = r + 1;
    let mut graph = vec![vec![]; n];
    for i in 0..r {
        graph[i].push((i + 1, 1 << i));
        graph[i].push((i + 1, 0));
    }

    let sum = (1 << r) - 1;
    for i in (0..(n - 1)).rev() {
        let to_i = (1 << i) - 1;
        if l >= to_i + 1 {
            let new_edge = l - to_i - 1;
            if new_edge > sum {
                // add paths [new_edge, new_edge+1, ..., l-1]
                graph[i].push((n - 1, new_edge));
                l = new_edge;
            }
        }
    }

    println!("{} {}", n, graph.iter().map(|e| e.len()).sum::<usize>());

    for (from, to, w) in graph
        .into_iter()
        .enumerate()
        .flat_map(|(i, e)| e.into_iter().map(move |(to, w)| (i, to, w)))
    {
        println!("{} {} {}", from + 1, to + 1, w);
    }
}

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()
    }
}

「第3回 RCO日本橋ハーフマラソン 予選」の復習

atcoder.jp

このコンテストに出たのですが、散々な結果だった。ただ、終わった後に流れてきた解法を見ると結構シンプルなものが多かったので、復習した。

A - ツーリストXの旅行計画

A - ツーリストXの旅行計画


分散が出てきてややこしい気持ちになるが、平均値を決め打ちすると、各辺のコストが固定の値になり、純粋な巡回セールスマン問題 (TSP) になる。

画像検索した感じだと 2-opt が初心者でも実装しやすそうに見えるので、実装してみた。

方針

  • 平均値を乱数で決め打ちする。
  • 最初は貪欲にとりあえず解を作る。スタート地点が決まっているので、スタート地点から、その都度、最もコストの低い辺を選びながら、移動していく。
  • 解に含まれている辺から 2 本選び、 2-opt 的に組み換える。これを全ての辺の組について試し、最もコストが減る組み合わせについて組み換える。これの組み換えは300回くらいやる。
  • これらを時間の限り繰り返し、最終的に一番良かった解を出力する。

最初の貪欲解

全くひねりなく、今いる頂点から一番低コストで行ける頂点に行く。

tuple<vector<size_t>, double> greedy() {
  double total_cost = 0.0;
  vector<size_t> res;
  vector<bool> vis(N, false);

  size_t cur = 0;
  vis[cur] = true;
  res.push_back(cur);

  REP(i, (N - 1)) {
    double cur_min = INF;
    size_t cur_next = N;
    REP(next, N) {
      if (vis[next]) {
        continue;
      }
      if (dist[cur][next] < cur_min) {
        cur_next = next;
        cur_min = dist[cur][next];
      }
    }

    total_cost += dist[cur][cur_next];
    res.push_back(cur_next);
    vis[cur_next] = true;
    cur = cur_next;
  }

  res.push_back(0);
  total_cost += dist[cur][0];

  return make_tuple(res, total_cost);
}

2-opt

Wikipedia を見ながら雰囲気で実装した。これも全くひねらず、全ての辺の組について組み換えてみて、一番コストを減らせる組について実際に組み換える。

double improve_2opt(vector<size_t>& path) {
  double cur_improvement = 0.0;
  size_t index_from = 0;
  size_t index_to = 0;

  REP(i, N) {
    auto from1 = path[i];
    auto to1 = path[i + 1];
    auto cost1 = dist[from1][to1];
    for (size_t j = i + 1; j < N; j++) {
      auto from2 = path[j];
      auto to2 = path[j + 1];
      auto cost2 = dist[from2][to2];

      auto prev_cost = cost1 + cost2;
      auto next_cost = dist[from1][from2] + dist[to1][to2];
      if (prev_cost > next_cost && prev_cost - next_cost > cur_improvement) {
        cur_improvement = prev_cost - next_cost;
        index_from = i + 1;
        index_to = j + 1;
      }
    }
  }
  if (index_from == index_to) {
    return 0.0;
  }

  reverse(path.begin() + index_from, path.begin() + index_to);
  return cur_improvement;
}

全体

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <tuple>
#include <vector>

using namespace std;

#define REP(i, n) for (size_t(i) = 0; (i) < (n); (i)++)

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}

uint64_t xor_shift64(uint64_t* state) {
  uint64_t x = *state;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  *state = x;
  return x;
}

/* ここまでテンプレート */

const double INF = 1e18;

size_t N;
double X[200], Y[200];
double dist[200][200];

double calc_distance(double x1, double y1, double x2, double y2) {
  double dx = x1 - x2;
  double dy = y1 - y2;
  return sqrt(dx * dx + dy * dy);
}

double improve_2opt(vector<size_t>& path) {
  double cur_improvement = 0.0;
  size_t index_from = 0;
  size_t index_to = 0;

  REP(i, N) {
    auto from1 = path[i];
    auto to1 = path[i + 1];
    auto cost1 = dist[from1][to1];
    for (size_t j = i + 1; j < N; j++) {
      auto from2 = path[j];
      auto to2 = path[j + 1];
      auto cost2 = dist[from2][to2];

      auto prev_cost = cost1 + cost2;
      auto next_cost = dist[from1][from2] + dist[to1][to2];
      if (prev_cost > next_cost && prev_cost - next_cost > cur_improvement) {
        cur_improvement = prev_cost - next_cost;
        index_from = i + 1;
        index_to = j + 1;
      }
    }
  }
  if (index_from == index_to) {
    return 0.0;
  }

  reverse(path.begin() + index_from, path.begin() + index_to);
  return cur_improvement;
}

tuple<vector<size_t>, double> greedy() {
  double total_cost = 0.0;
  vector<size_t> res;
  vector<bool> vis(N, false);

  size_t cur = 0;
  vis[cur] = true;
  res.push_back(cur);

  REP(i, (N - 1)) {
    double cur_min = INF;
    size_t cur_next = N;
    REP(next, N) {
      if (vis[next]) {
        continue;
      }
      if (dist[cur][next] < cur_min) {
        cur_next = next;
        cur_min = dist[cur][next];
      }
    }

    total_cost += dist[cur][cur_next];
    res.push_back(cur_next);
    vis[cur_next] = true;
    cur = cur_next;
  }

  res.push_back(0);
  total_cost += dist[cur][0];

  return make_tuple(res, total_cost);
}

tuple<vector<size_t>, double> solve(double average) {
  REP(i, N) REP(j, N) {
    auto d = calc_distance(X[i], Y[i], X[j], Y[j]);
    dist[i][j] = (d - average) * (d - average);
    dist[j][i] = dist[i][j];
  }

  vector<size_t> path;
  double total_cost;
  tie(path, total_cost) = greedy();

  REP(i, 300) {
    double improvement = improve_2opt(path);
    if (improvement < 1e-9) {
      break;
    }
    assert(total_cost >= improvement);
    total_cost -= improvement;
  }
  return make_tuple(path, total_cost);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  auto start = chrono::system_clock::now();

  cin >> N;
  REP(i, N) { cin >> X[i] >> Y[i]; }

  uint64_t random_state = 71;

  vector<vector<size_t>> paths;
  vector<tuple<double, size_t>> costs;
  while (true) {
    double r = xor_shift64(&random_state);
    r /= numeric_limits<uint64_t>::max();

    double average = 200.0 + r * 200.0;
    vector<size_t> path;
    double cost;
    tie(path, cost) = solve(average);
    costs.emplace_back(cost, paths.size());
    paths.emplace_back(path);

    auto ms = chrono::duration_cast<chrono::milliseconds>(
                  chrono::system_clock::now() - start)
                  .count();
    if (ms > 1900) {
      break;
    }
  }
  sort(costs.begin(), costs.end());

  size_t min_cost_index = get<1>(costs[0]);

  const auto& path = paths[min_cost_index];
  REP(i, N) { cout << path[i] << endl; }
}

結果

Submission #4246661 - 第3回 RCO日本橋ハーフマラソン 予選

これで 3766621 点になる。コンテスト本番だと8位くらい。

B - ファーマーXの収穫計画

B - ファーマーXの収穫計画

各マスの数字は一様乱数で決まっているので 8, 7, 6 を思考停止で全部 9 にしてしまっても 1700 手くらいで済みそうという考察が出来るらしい(すごい)。9の島は9個以上の要素が連なっていないと回収できないので、小さい島は他の島と頑張って接続したい。

方針

  • 8, 7, 6 を全て 9 にしてしまう。
  • 小さい島からダイクストラでつなげていって大きい島になるようにする。
  • 一気に回収する。

コード

ビジュアライザを見た限り微妙にバグっているが、疲れたので解散。

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;

#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}

uint64_t xor_shift64(uint64_t* state) {
  uint64_t x = *state;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  *state = x;
  return x;
}

// --- template ---

class UnionFind {
 private:
  struct nodeinfo {
    int par;
    int rank;
    int size;
    nodeinfo(int p) : par(p), rank(0), size(1) {}
  };
  std::vector<nodeinfo> node;

 public:
  UnionFind(int n) : node() {
    node.reserve(n);
    for (int i = 0; i < n; ++i) {
      node.push_back(nodeinfo(i));
    }
  }
  int root(int x) {
    if (node[x].par == x) {
      return x;
    }
    return node[x].par = root(node[x].par);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (node[x].rank < node[y].rank) {
      node[x].par = y;
      node[y].size += node[x].size;
      node[x].size = 0;
    } else {
      node[y].par = x;
      node[x].size += node[y].size;
      node[y].size = 0;
      if (node[x].rank == node[y].rank) {
        ++node[x].rank;
      }
    }
  }

  bool is_same_set(int x, int y) { return root(x) == root(y); }

  int size(int x) {
    x = root(x);
    return node[x].size;
  }
};

using State = tuple<double, int, int>;
const int DX[] = {0, 0, 1, -1};
const int DY[] = {1, -1, 0, 0};
const int INF = 1e9;

int N, M;
int A[50][50];

auto backward(vector<vector<double>>& dist, int i, int j) {
  vector<tuple<int, int>> ans;
  while (dist[i][j] > 0) {
    auto cur_min = dist[i][j];
    assert(cur_min < INF);
    tuple<int, int> next = make_tuple(i, j);

    REP(d, 4) {
      int ni = i + DX[d];
      int nj = j + DY[d];
      if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;

      if (dist[ni][nj] < cur_min) {
        next = make_tuple(ni, nj);
        cur_min = dist[ni][nj];
      }
    }

    int ni, nj;
    tie(ni, nj) = next;

    assert(ni != i || nj != j);
    dist[i][j] = INF;
    ans.emplace_back(ni, nj);
    i = ni;
    j = nj;
  }

  return ans;
}

vector<tuple<int, int>> dijkstra(int si, int sj, UnionFind& uf) {
  const int start_size = uf.size(si * N + sj);

  priority_queue<State, vector<State>, greater<State>> q;
  vector<vector<double>> dist(N, vector<double>(N, INF));
  dist[si][sj] = 0;
  q.emplace(0, si, sj);
  while (q.size() != 0) {
    int cost, i, j;
    tie(cost, i, j) = q.top();
    q.pop();

    if (A[i][j] == 9 && uf.size(i * N + j) + start_size >= 9) {
      return backward(dist, i, j);
    }

    REP(d, 4) {
      int ni = i + DX[d];
      int nj = j + DY[d];
      if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
      double w = 9.00001 - A[ni][nj];
      if (dist[ni][nj] > dist[i][j] + w) {
        dist[ni][nj] = dist[i][j] + w;
        q.emplace(dist[ni][nj], ni, nj);
      }
    }
  }

  return {};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vector<tuple<int, int, int>> ans;

  cin >> N >> M;
  REP(i, N) REP(j, N) {
    cin >> A[i][j];
    auto cost = 9 - A[i][j];
    if (cost <= 3 && cost + ans.size() <= M) {
      A[i][j] += cost;
      REP(z, cost) ans.emplace_back(1, i, j);
    }
  }

  UnionFind uf(N * N);
  REP(i, N) REP(j, N) REP(d, 4) {
    int ni = i + DX[d];
    int nj = j + DY[d];
    if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
    if (A[i][j] != A[ni][nj]) continue;
    int from = i * N + j;
    int to = ni * N + nj;
    uf.unite(from, to);
  }

  vector<bool> started(N * N, false);
  vector<vector<tuple<int, int>>> paths;
  vector<tuple<double, int, int>> costs;
  REP(i, N) REP(j, N) {
    if (A[i][j] != 9) continue;
    int x = i * N + j;
    x = uf.root(x);

    if (started[x]) continue;
    started[x] = true;

    int size = uf.size(i * N + j);
    if (size >= 9) continue;

    auto path = dijkstra(i, j, uf);
    int cost = 0;
    for (const auto& t : path) {
      int pi, pj;
      tie(pi, pj) = t;
      cost += 9 - A[pi][pj];
    }

    double cost_per_size = cost;
    cost_per_size /= size;
    costs.emplace_back(cost_per_size, cost, paths.size());
    paths.emplace_back(path);
  }

  sort(costs.begin(), costs.end());
  for (const auto& t : costs) {
    double cps;
    int cost;
    int index;
    tie(cps, cost, index) = t;
    const auto& path = paths[index];
    cost = 0;
    for (const auto& s : path) {
      int i, j;
      tie(i, j) = s;
      int turn = 9 - A[i][j];
      cost += turn;
    }

    if (cost + ans.size() >= M - 200) continue;
    for (const auto& s : path) {
      int i, j;
      tie(i, j) = s;
      int turn = 9 - A[i][j];
      REP(z, turn) ans.emplace_back(1, i, j);
      A[i][j] = 9;
    }
  }

  REP(i, N) REP(j, N) REP(d, 4) {
    int ni = i + DX[d];
    int nj = j + DY[d];
    if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
    if (A[i][j] != A[ni][nj]) continue;
    int from = i * N + j;
    int to = ni * N + nj;
    uf.unite(from, to);
  }

  vector<tuple<int, int, int>> candidates;
  vector<bool> done(N * N, false);
  REP(i, N) REP(j, N) {
    int x = i * N + j;
    x = uf.root(x);
    if (done[x]) continue;
    done[x] = true;
    if (uf.size(x) < A[i][j]) continue;
    int value = uf.size(x) * A[i][j];
    candidates.emplace_back(value, i, j);
  }

  sort(candidates.rbegin(), candidates.rend());
  for (const auto& t : candidates) {
    int v, i, j;
    tie(v, i, j) = t;
    ans.emplace_back(2, i, j);
    if (ans.size() == M) break;
  }

  for (const auto& t : ans) {
    int o, i, j;
    tie(o, i, j) = t;
    cout << o << " " << i << " " << j << "\n";
  }
}

結果

Submission #4247854 - 第3回 RCO日本橋ハーフマラソン 予選

503599点になる。本番100位くらい。僕は本番これの半分くらいしかとれなかったので、とりあえずよし。

6まで思考停止で9にしてしまうのはやりすぎ感はあるし、もう少し改善できそう。

Rust の Vec の sort_by_key は気をつけて使おう

当たり前っちゃ当たり前だが、

vec.sort_by_key(|&value| heavy_function(value));

みたいなことをすると、 heavy_function が比較のたびに呼ばれるので、ソートが定数倍遅くなる。これは sort_by_cached_key でなんとかなるっぽい。

sort_by_key は

This sort is stable (i.e. does not reorder equal elements) and O(m n log(m n)) worst-case, where the key function is O(m).

sort_by_cached_key は

During sorting, the key function is called only once per element.

This sort is stable (i.e. does not reorder equal elements) and O(m n + n log n) worst-case, where the key function is O(m).

AtCoder Problems を色々いじった

この記事は AtCoder関連サービス Advent Calendar 2018 - Adventar の一部です。毎年なぜか12月になるとウェブアプリを触りたくなる。

kimiyuki さんが DB に index を張ってくれた

なぜか今まで index を張っていなかったのが無事張られた。これによって、あるユーザーについての提出一覧を取得するのが高速化された。

github.com

ユーザー情報 API を作った

今まではユーザー情報を表示するために、「AC 数ランキング」「Rated Point ランキング」「使用言語のランキング」を取得していた。これらはそれぞれ、「ユーザーの AC 数が上から何番目か」「ユーザーの Point が上から何番目か」「ユーザーがある言語で解いた問題数が、その言語の中で何番目か」を表示するのに使われていた。これらを表示するためにわざわざランキングを取得しているのは、もともとあったランキング API を流用してユーザーページを作ったという歴史的経緯によるものである。実際には意外にユーザーページを見る人が多く、不必要なランキング取得によって表示が遅いなどの問題があった。今回は、ユーザーについて必要な情報だけ返す API を新しく作り、表示を高速化された。

https://github.com/kenkoooo/AtCoderProblems/pull/73github.com

ユーザー共通のファイルは静的ファイルに書き出すようにした

ユーザーごとの提出一覧は DB に問い合わせる必要があるが、それ以外の API は静的な JSON ファイルに書き出すようにした。もともと、これらの API は叩かれても 304 を返すようにしていたが、そのへんは nginx でやってくださいという気持ちになった。あとは API サーバーが落ちてても表面的には動いていてほしいというのもある。

https://github.com/kenkoooo/AtCoderProblems/pull/82github.com

AGC 029 C - Lexicographic constraints

解法

できるだけ、辞書準最小のリストを作ることを目指す。例えばA=[2, 2]の時は["aa","bb"]でもよいが、["aa", "ab"] が辞書準最小のリストになる。

この時、一つ前の要素よりも大きい時は、一つ前の文字列の後ろに "a" を連続で追加すればよく、そうでない時は、その要素の末尾を1つインクリメントすれば良い。どういうことかと言うと、例えば A=[3, 3, 3, 5, 3, 3] のとき、2種類だけの文字列で作るとすると文字列のリストは["aaa", "aab", "aba", "abaaa", "abb", "baa"] のようになる。これは二進数で表した整数の適当な桁を1ずつ増加させていく単純な操作であることが分かる。

よってx種類の文字で構築可能かどうかは、x進数で操作した時に桁あふれのような状態にならないかどうかで判定できる。あとはこれを二分探索すれば良い。

コード

use std::collections::BTreeMap;

fn solve(a: &Vec<usize>, color: usize) -> bool {
    let n = a.len();
    let mut big = Big {
        map: BTreeMap::new(),
        color: color,
    };
    let mut start = 0;
    for i in 1..n {
        if a[i] <= a[i - 1] {
            big.increment(a[i]);
            start = i + 1;
            break;
        }
    }

    for i in start..n {
        if a[i] <= a[i - 1] {
            big.resize(a[i]);
            if !big.increment(a[i]) {
                return false;
            }
        }
    }
    true
}

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { reader: s.lock() };
    let n: usize = sc.read();
    let a: Vec<usize> = sc.read_vec(n);

    if (1..n).all(|i| a[i] > a[i - 1]) {
        println!("1");
        return;
    }

    let mut ng = 0;
    let mut ok = n;
    while ok - ng > 1 {
        let mid = (ok + ng) / 2;
        if solve(&a, mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    println!("{}", ok + 1);
}

struct Big {
    map: BTreeMap<usize, usize>,
    color: usize,
}

impl Big {
    fn increment(&mut self, index: usize) -> bool {
        if let Some(&v) = self.map.get(&index) {
            if v == self.color {
                self.map.remove(&index);
                if index == 1 {
                    false
                } else {
                    self.increment(index - 1)
                }
            } else {
                *self.map.get_mut(&index).unwrap() += 1;
                true
            }
        } else {
            self.map.insert(index, 1);
            true
        }
    }

    fn resize(&mut self, s: usize) {
        while let Some(&key) = self.map.keys().next_back() {
            if key > s {
                self.map.remove(&key);
            } else {
                break;
            }
        }
    }
}

pub struct Scanner<R> {
    reader: 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
            .reader
            .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 read_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()
    }
}

AGC 029 D - Grid game

解法

まず先手が能動的にパスを選択することはありえない。なので、後手は先手の進行方向に障害物を置きさえすれば良い。

両プレーヤーが能動的にパスを選択せずにxターンが終了した時の位置を (x, y) とする。このとき、後手は適当にパスを挟むことでxターンが終了したときの位置を (x,1)〜(x,y) から選ぶことが出来る。つまり、xターン終了時に (x+1, 1) 〜 (x+1, y) のどこかに障害物があるならば x+1 ターン目で先手はパスせざるを得なくなる。

コード

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { reader: s.lock() };
    let h: usize = sc.read();
    let w: usize = sc.read();
    let n: usize = sc.read();

    let mut map = BTreeMap::new();
    for _ in 0..n {
        let x: usize = sc.read();
        let y: usize = sc.read();
        map.entry(x).or_insert(BTreeSet::new()).insert(y);
    }

    let mut y = 1;
    for x in 1..(h + 1) {
        if let Some(set) = map.get(&(x + 1)) {
            if set.range(..(y + 1)).next().is_some() {
                println!("{}", x);
                return;
            }
            if !set.contains(&(y + 1)) {
                y += 1;
            }
        } else {
            y += 1;
        }
    }
    println!("{}", h);
}

pub struct Scanner<R> {
    reader: 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
            .reader
            .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 read_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()
    }
}

AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies

解法

求める値は以下の式で表される。

{ \displaystyle
ans = \sum_{c_1+c_2+c_3+...+c_N=C} \sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} ... \sum_{x_N=A_N}^{B_N} ( x_1^{c_1} + x_2^{c_2} + ... + x_N^{c_N} )
}

これは解説動画の変形を駆使して、以下のように変形できる。

{ \displaystyle
ans = \sum_{c_1+c_2+c_3+...+c_N=C} ( \sum_{x_1=A_1}^{B_1} x_1^{c_1} )  ( \sum_{x_2=A_2}^{B_2} x_2^{c_2} ) ... ( \sum_{x_N=A_N}^{B_N} x_N^{c_N} ) 
}

よって以下のような動的計画法で解ける。

{ \displaystyle
dp_{0, 0} = 1 \\
dp_{i+1, from+add} = dp_{i,from} \times \sum_{x_i=A_i}^{B_i}x_i^{add} \\
ans = dp_{N, C}
}

コード

use self::mod_int::ModInt;

const MOD: usize = 1e9 as usize + 7;

fn main() {
    let stdin = std::io::stdin();
    let mut sc = Scanner {
        reader: stdin.lock(),
    };

    let n: usize = sc.read();
    let c: usize = sc.read();
    let a: Vec<usize> = sc.read_vec(n);
    let b: Vec<usize> = sc.read_vec(n);

    let b_max: usize = *b.iter().max().unwrap();

    // pow[i][j] := i**j
    let mut pow = vec![vec![ModInt::new(0); c + 1]; b_max + 1];
    for i in 1..(b_max + 1) {
        pow[i][0] = ModInt::new(1);
        for j in 0..c {
            pow[i][j + 1] = pow[i][j] * i;
        }
    }

    // sum[i][c] := sum(pow[a[i]..b[i]+1][c])
    let mut sum = vec![vec![ModInt::new(0); c + 1]; n];
    for i in 0..n {
        let from = a[i];
        let to = b[i];
        for c in 0..(c + 1) {
            for t in from..(to + 1) {
                sum[i][c] += pow[t][c];
            }
        }
    }

    let mut dp = vec![ModInt::new(0); c + 1];
    dp[0] = ModInt::new(1);
    for i in 0..n {
        let mut next = vec![ModInt::new(0); c + 1];
        for from in 0..(c + 1) {
            for add in 0..(c + 1) {
                if from + add > c {
                    continue;
                }
                next[from + add] += dp[from] * sum[i][add];
            }
        }
        dp = next;
    }
    println!("{}", dp[c].value);
}

pub mod mod_int {
    use std::ops::{Add, AddAssign, Mul, MulAssign, Rem, Sub, SubAssign};

    #[derive(Copy)]
    pub struct ModInt<T> {
        pub value: T,
        modulo: T,
    }

    impl<T> Clone for ModInt<T>
    where
        T: Copy,
    {
        fn clone(&self) -> Self {
            ModInt {
                value: self.value,
                modulo: self.modulo,
            }
        }

        fn clone_from(&mut self, source: &ModInt<T>) {
            self.value = source.value;
            self.modulo = source.modulo;
        }
    }

    impl<T> Add<ModInt<T>> for ModInt<T>
    where
        T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd,
    {
        type Output = ModInt<T>;
        fn add(self, rhs: ModInt<T>) -> ModInt<T> {
            self + rhs.value
        }
    }

    impl<T> Add<T> for ModInt<T>
    where
        T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd,
    {
        type Output = ModInt<T>;
        fn add(self, rhs: T) -> ModInt<T> {
            let m = self.modulo;
            let mut t = rhs + self.value;
            if t >= m {
                t = t - m;
            }
            ModInt {
                value: t,
                modulo: self.modulo,
            }
        }
    }

    impl<T> Sub<T> for ModInt<T>
    where
        T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>,
    {
        type Output = ModInt<T>;
        fn sub(self, rhs: T) -> ModInt<T> {
            let rhs = if rhs >= self.modulo {
                rhs % self.modulo
            } else {
                rhs
            };
            let value = if self.value < rhs {
                self.value + self.modulo
            } else {
                self.value
            };
            ModInt {
                value: value - rhs,
                modulo: self.modulo,
            }
        }
    }

    impl<T> Sub<ModInt<T>> for ModInt<T>
    where
        T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>,
    {
        type Output = ModInt<T>;
        fn sub(self, rhs: ModInt<T>) -> ModInt<T> {
            self - rhs.value
        }
    }

    impl<T> AddAssign<T> for ModInt<T>
    where
        T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd,
    {
        fn add_assign(&mut self, other: T) {
            *self = *self + other;
        }
    }
    impl<T> AddAssign<ModInt<T>> for ModInt<T>
    where
        T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd,
    {
        fn add_assign(&mut self, other: ModInt<T>) {
            *self = *self + other;
        }
    }

    impl<T> SubAssign<T> for ModInt<T>
    where
        T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>,
    {
        fn sub_assign(&mut self, other: T) {
            *self = *self - other;
        }
    }

    impl<T> SubAssign<ModInt<T>> for ModInt<T>
    where
        T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>,
    {
        fn sub_assign(&mut self, other: ModInt<T>) {
            *self = *self - other;
        }
    }

    impl<T> Mul<ModInt<T>> for ModInt<T>
    where
        T: Mul<Output = T> + Rem<Output = T> + Copy,
    {
        type Output = ModInt<T>;

        fn mul(self, rhs: ModInt<T>) -> ModInt<T> {
            self * rhs.value
        }
    }
    impl<T> Mul<T> for ModInt<T>
    where
        T: Mul<Output = T> + Rem<Output = T> + Copy,
    {
        type Output = ModInt<T>;

        fn mul(self, rhs: T) -> ModInt<T> {
            let t = (self.value * rhs) % self.modulo;
            ModInt {
                value: t,
                modulo: self.modulo,
            }
        }
    }

    impl<T> MulAssign<T> for ModInt<T>
    where
        T: Mul<Output = T> + Rem<Output = T> + Copy,
    {
        fn mul_assign(&mut self, rhs: T) {
            *self = *self * rhs;
        }
    }

    impl<T> MulAssign<ModInt<T>> for ModInt<T>
    where
        T: Mul<Output = T> + Rem<Output = T> + Copy,
    {
        fn mul_assign(&mut self, rhs: ModInt<T>) {
            *self = *self * rhs;
        }
    }

    impl ModInt<usize> {
        pub fn new(value: usize) -> Self {
            ModInt {
                value: value,
                modulo: self::super::MOD,
            }
        }
    }
}

pub struct Scanner<R> {
    reader: 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
            .reader
            .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 read_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()
    }
}