CF Good Bye 2017 G: New Year and Original Order

http://codeforces.com/contest/908/problem/G

解法

上の桁から決めていく桁 DP により解くことができる。ソート済み整数はレピュニット数*1 の和で表せるという性質が役に立つ。たとえば 1122244 という整数の場合

1122244
1111111
  11111
     11
     11

という表現が可能である。$\underbrace{1\dots1}_n=(10^{n+1}-1)/9$ と表せるため、以下の表現も可能である。

$$1122244\times 9 + 9 = 10^8 + 10^6 + 10^3 + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0$$

1122244 の次に 2 を使うとしよう。このとき次のような変化を見せる。

\begin{align}
1122244\times 9 + 9 &= \underline{10^8 + 10^6} + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 \\
11222244\times 9 + 9 &= \underline{10^9 + 10^7} + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0
\end{align}

つまり 1 と 2 に対応するレピュニット数が 10 倍されて、それ以外はそのままになっている。ここまでわかると、1,2,3,...,9 に対応するレピュニット数の総和は独立に数え上げられることが分かる。よって、次のようなDPが可能となる。

\begin{align}
1122244\times 9 + 9 &= \underbrace{10^8}_{dp[i][less][1]} + \underbrace{10^6}_{dp[i][less][2]} + \underbrace{10^3}_{dp[i][less][3]} + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 \\
11222244\times 9 + 9 &= \underbrace{10^9}_{dp[i+1][less][1]} + \underbrace{10^7}_{dp[i+1][less][2]} + \underbrace{10^3}_{dp[i+1][less][3]} + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0
\end{align}

\begin{align}
dp[i+1][j'][k] \gets \begin{cases}
10\times dp[i][j][k] & \text{$d \le k$} \\
dp[i][j][k] & \text{otherwise}
\end{cases}
\end{align}

ここで $d$ は遷移時に選んだ数字である。

Submission #33803662 - Codeforces

感想

アプローチの掛け方が少ないから少し考えれば解けるような問題だった。
レピュニット数は AtCoder でも最近見たしね。Eの方が圧倒的に難しい。

*1:レピュニット - Wikipedia

ARC086 E問題 Smuggling Marbles

E: Smuggling Marbles - AtCoder Regular Contest 086 | AtCoder

解法

縮約解について説明する。よく考えるとマージテク解と本質的に同じ。

深さが等しい頂点をまとめて計算できるのは自明だと思いたい。普通にやると$O(depth\times n)$ だが、各深さごとに木を縮約してあげると $O(n \log n+ n\log (10^9+7))$ で解ける。

縮約するとなぜ計算量が落ちるのかというと、内部節点がかならず分岐を持つ木であれば、内部節点の個数は葉の個数より少ないためである。

内部節点の個数の評価は二分木で有名だろう。一応説明する。

証明（内部節点の個数の評価）

葉と隣接する内部節点をひとつ選び、それを改めて葉に置き直す操作を考える（図を参照）。頂点がひとつになるまでこの操作を繰り返すと、その回数は内部節点の個数と一致する。この操作によって葉は少なくとも一つ減るため、（内部節点の個数）＜（葉の個数）であることが言える。（証明終わり）

ソースコード

縮約解：https://arc086.contest.atcoder.jp/submissions/1864868
マージテク解：https://arc086.contest.atcoder.jp/submissions/1864696

感想

縮約すると計算量が落ちるのには気がついたのだけど、縮約の仕方がまずかったみたいでコンテスト中には通せなかった。縮約は post-order に並べて隣接要素の LCA を取っていくと良いのだが、変な方法でやろうとして失敗した。

CSA #60 E問題

Rust で書き直したのだが Rust で提出できなかった。そういえばクロージャの再帰ってできるんだろうか。グラフを引数に渡すのくどい。

パスを交差させる必要はなくて、互いに素なものだけ考慮すれば良い。これは適当な木DPで解ける――具体的には、状態を(dp0: 親と繋がない)(dp1:親と繋ぐ)として値を (パス数, パス長) とすれば良い。

macro_rules! input {
  ($($x:ident : $t:ty), *) => {
    $(let $x: $t;)*
    {
      let mut s = String::new();
      std::io::stdin().read_line(&mut s).unwrap();
      let mut it = s.trim().split_whitespace();
      $($x = it.next().unwrap().parse().unwrap();)*
      assert!(it.next().is_none());
    }
  };
}

fn dfs(u: usize, p: usize, g: &Vec<Vec<(usize, i32)>>) -> ((i32, i32), (i32, i32)) {
  use std::cmp;

  let mut dp0 = (0, 0);
  let mut dp1 = (1, 0);

  for &(v, c) in &g[u] {
    if v == p { continue }
    let (ep0, ep1) = dfs(v, u, g);

    let x0 = (dp0.0 + ep0.0    , dp0.1 + ep0.1);
    let y0 = (dp1.0 + ep0.0    , dp1.1 + ep0.1);
    let x1 = (dp1.0 + ep1.0 - 1, dp1.1 + ep1.1 + 1);
    let y1 = (dp0.0 + ep1.0    , dp0.1 + ep1.1 + 1);

    if c == 0 {
      dp0 = x0;
      dp1 = y0;
    } else if c == 1 {
      dp0 = x1;
      dp1 = y1;
    } else {
      dp0 = cmp::min(x0, x1);
      dp1 = cmp::min(y0, y1);
    }
  }
  (dp0, dp1)
}

fn main() {
  input!(n: usize);

  let mut g: Vec<Vec<(usize, i32)>> = vec![Vec::new(); n];

  for _ in 1..n {
    input!(a: usize, b: usize, c: i32, d: i32);
    let a = a - 1;
    let b = b - 1;
    let d = if d != 2 { c ^ d } else { d };
    g[a].push((b, d));
    g[b].push((a, d));
  }

  let ((x, y), _) = dfs(0, n, &g);
  println!("{} {}", x, y);
}

ARC 085 F

http://arc085.contest.atcoder.jp/tasks/arc085_d

愚直な DP 解を示す。DP の値には一致した文字数を格納してあり、状態は(位置、最後に使った区間番号)としている。0 番目に番兵として区間 [-1,-1] を入れている。

int dp[100][101];

void to(int &x, int y) {
  x = max(x, y);
}

int main() {
  int n;
  cin >> n;

  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }

  int q;
  cin >> q;

  vector<int> l(q + 1), r(q + 1);
  l[0] = -1;
  r[0] = -1;
  for (int i = 1; i <= q; i++) {
    cin >> l[i] >> r[i];
    l[i]--;
    r[i]--;
  }
  q++;

  fill_n(*dp, 100 * 101, -1e9);
  dp[0][0] = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < q; j++) {
      for (int k = 0; k < q; k++) {
        if (l[k] == i && r[j] <= r[k]) {
          to(dp[i + 1][k], dp[i][j] + b[i]);
        }
      }
      if (i <= r[j]) {
        to(dp[i + 1][j], dp[i][j] + b[i]);
      } else {
        to(dp[i + 1][j], dp[i][j] + !b[i]);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < q; i++) {
    ans = max(ans, dp[n][i]);
  }
  cout << n - ans << endl;
}

区間を右端でソートすることで、DP の性質が良くなる。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
const int N = 1 << 18;
const int inf = 1.01e9;
int dat[N * 2];
int lz[N * 2];
 
void apply(int k, int v) {
  dat[k] += v;
  lz[k] += v;
}
 
void push(int k) {
  apply(k * 2 + 0, lz[k]);
  apply(k * 2 + 1, lz[k]);
  lz[k] = 0;
}
 
void setval(int y, int v, int k = 1, int ll = 0, int rr = N) {
  if (rr - ll == 1) {
    dat[k] = v;
    lz[k] = 0;
    return;
  }
  push(k);
  int mm = ll + rr >> 1;
  if (y < mm) {
    setval(y, v, k * 2 + 0, ll, mm);
  } else {
    setval(y, v, k * 2 + 1, mm, rr);
  }
  dat[k] = max(dat[k * 2], dat[k * 2 + 1]);
}
 
void update(int l, int r, int v, int k = 1, int ll = 0, int rr = N) {
  if (rr <= l || r <= ll) return;
  if (l <= ll && rr <= r) {
    apply(k, v);
    return;
  }
  push(k);
  update(l, r, v, k * 2 + 0, ll, ll + rr >> 1);
  update(l, r, v, k * 2 + 1, ll + rr >> 1, rr);
  dat[k] = max(dat[k * 2], dat[k * 2 + 1]);
}
 
int query(int l, int r, int k = 1, int ll = 0, int rr = N) {
  if (rr <= l || r <= ll) return -inf;
  if (l <= ll && rr <= r) return dat[k];
  push(k);
  return max(query(l, r, k * 2, ll, ll + rr >> 1), query(l, r, k * 2 + 1, ll + rr >> 1, rr));
}
 
int main() {
  int n;
  cin >> n;
 
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
 
  int q;
  cin >> q;
 
  vector<pair<int, int>> rl(q + 1);
  rl[0].first = 0;
  rl[0].second = 0;
  for (int i = 1; i <= q; i++) {
    cin >> rl[i].second >> rl[i].first;
  }
  sort(rl.begin(), rl.end());
  q++;
 
  vector<int> l(q), r(q);
  vector<vector<int>> foo(n);
  for (int i = 0; i < q; i++) {
    l[i] = rl[i].second - 1;
    r[i] = rl[i].first - 1;
    if (l[i] >= 0) 
      foo[l[i]].push_back(i);
  }
 
  update(1, q, -inf);
 
  int u = 0;
 
  for (int i = 0; i < n; i++) {
    vector<int> hoge;
    for (int j = 0; j < foo[i].size(); j++) {
      // r[t] > r[k]
      int t = upper_bound(r.begin(), r.end(), r[foo[i][j]]) - r.begin();
      hoge.push_back(query(0, t));
    }
 
    for (int j = 0; j < foo[i].size(); j++) {
      setval(foo[i][j], hoge[j]);
    }
    while (u < q && r[u] < i) {
      u++;
    }
    update(0, u, !b[i]);
    update(u, q, b[i]);
  }
 
  int ans = query(0, q);
  cout << n - ans << endl;
}

ARC 084 F XorShift

http://arc084.contest.atcoder.jp/tasks/arc084_d

多項式への言い換えが気持ちがいい問題だった。多項式は気持ちがいい。

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;

const long long mod = 998244353;

string gcd(string a, string b) {
  while (true) {
    if (a.size() < b.size()) swap(a, b);
    for (int i = 0; i < b.size(); i++) {
      a[i] ^= b[i];
    }
    int pos = a.find(1);
    if (pos == string::npos) return b;
    a.erase(0, pos);
  }
}

string input() {
  string s;
  cin >> s;
  for (char &c : s) c -= '0';
  return s;
}

long long modpow(long long x, long long y) {
  long long ret = 1;
  while (y > 0) {
    if (y & 1) ret = ret * x % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ret;
}

int main() {
  int n;
  cin >> n;
  string x = input();
  string g = input();
  for (int i = 1; i < n; i++) {
    g = gcd(g, input());
  }

  long long ans = 0;
  string curr(x.size(), 0);
  for (int i = 0; i + g.size() <= x.size(); i++) {
    if (curr[i] == 0 && x[i] == 0) {
      // can't use
    } else if (curr[i] == 1 && x[i] == 0) {
      for (int j = 0; j < g.size(); j++) {
        curr[i + j] ^= g[j];
      }
    } else if (curr[i] == 0 && x[i] == 1) {
      for (int j = 0; j < g.size(); j++) {
        curr[i + j] ^= g[j];
      }
      ans += modpow(2, x.size() - i - g.size());
      ans %= mod;
    } else if (curr[i] == 1 && x[i] == 1) {
      ans += modpow(2, x.size() - i - g.size());
      ans %= mod;
    }
  }
  if (curr <= x) {
    ans++;
    ans %= mod;
  }
  
  cout << ans << endl;
}