Mujin Programming Challenge 2017 C - Robot and String (解説を見た)

自分で考察したときは手掛かりが何もなかった。
C - Robot and String

問題

英小文字からなる文字列Sが与えられる。以下の形のクエリにQ回答えよ。

  • Sの部分文字列S[L[i]...R[i] + 1] (半開区間、L[i]文字目からR[i]文字目までを抜き出した文字列)について、以下の規則で簡約していった結果が空文字列になるか判定せよ:
    • 文字列の中に隣接する同じ文字がある場合に、それらの中で一番左のものについて、その同じ2文字を辞書順で次の文字1文字に変換する。ただしzzの変換先は空文字列とする。

制約

  • 1 <= |S| <= 5 * 10^5
  • 1 <= Q <= 10^5

解法

まず、各iについて、S[i...x]が空文字列に簡約されるような最小のx > iを求めたい気分になる。文字列の簡約は左から優先して行われるので、空文字列から始めて、i文字目から文字を追加して簡約して…、という処理をj文字目まで行った結果は、S[i..j]を簡約した結果と同じになる。
i文字目から文字の追加・簡約を繰り返すとき、文字列が最初に空文字列に簡約されるのはいつだろうか? そのような場合はもともと"z"だった文字列に'z'を追加した場合、およびその場合に限られる。よって、各iについてS[i..x]が"z"に簡約されるような最小のx > iを求めたい気分になる。この考察を繰り返すと、各iについてS[i..x]が各文字1文字に簡約されるような最小のx > iを求めたい気分になる。

実は以上の情報がDPをする上で十分である。DP[i] := (S[i...x]が空文字列に簡約されるような最小のx > i), DPS[c][i] := (S[i..x]がc 1文字に簡約されるような最小のx > i)とすると、以下の更新を行えばいいことがわかる(更新はすべてminで、式の中に一つでもinvalidな値がある場合は実行されない):

  • DPS[c][i] <- DPS[c][DP[i]]
  • DPS[c + 1][i] <- DPS[c][DPS[c][i]] (c < 'z', ダブリングに似ている)
  • DP[i] <- DPS['z'][DPS['z'][i]]

これらの更新はどこから始めればよいか? まず、i = n - 1のときは更新なしで正しい答えが手に入る。i = n - 2のときは、DP[n - 1]と各文字cについてDPS[c][n - 1]がわかっていれば正しい答えが手に入る。この考察を帰納的に行うことで、iの降順に更新を行えば良いことがわかる。

以上でDP[i]がわかった。あとはこれをダブリングすれば、各クエリに対してO(log |S|)時間で答えを求めることができる。このダブリングの手法は例えばLCAの計算などで有名なので、ここでは省略する。

登場する典型

  • ダブリング
  • 再帰的に考察を進め、自己完結したら止める

実装上の注意点

  • 添字の扱い(上限n - 1かnか)に気をつける

提出: #4397603 (Rust)

// This solution was written after the author read the editorial.
fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        s: chars,
        lr: [(usize1, usize)],
    }
    let n = s.len();
    let s: Vec<_> = s.into_iter().map(|x| (x as u8 - b'a') as usize).collect();
    let mut dp = vec![n + 1; n + 1];
    let mut dps = vec![vec![n + 1; 26]; n + 1];
    for i in (0..n).rev() {
        let mut que = BinaryHeap::new();
        que.push((n - i - 1, s[i]));
        while let Some((pidx, ch)) = que.pop() {
            let idx = n - pidx;
            if ch <= 25 {
                if dps[i][ch] <= idx { continue; }
                dps[i][ch] = idx;
                if dps[idx][ch] <= n {
                    que.push((n - dps[idx][ch], ch + 1));
                }
            } else {
                assert_eq!(ch, 26);
                if dp[i] <= idx { continue; }
                dp[i] = idx;
                for j in 0..26 {
                    if dps[idx][j] <= n {
                        que.push((n - dps[idx][j], j));
                    }
                }
            }
        }
    }
    const B: usize = 20;
    let mut dbl = vec![vec![n + 1; n]; B];
    for i in 0..n {
        dbl[0][i] = dp[i];
    }
    for j in 1..B {
        for i in 0..n {
            let stage = dbl[j - 1][i];
            if stage < n {
                dbl[j][i] = dbl[j - 1][stage];
            }
        }
    }
    for (mut l, r) in lr {
        for i in (0..B).rev() {
            if dbl[i][l] <= r {
                l = dbl[i][l];
            }
            if l == n { break; }
        }
        puts!("{}\n", if l == r { "Yes" } else { "No" });
    }
}

まとめ

「1文字に簡約できる範囲を持つDP」という解説の方法が天才すぎて、それっぽい考察の道筋をこじつけるのに苦労した。

CODE FESTIVAL 2017 Elimination Tournament Round 2 A - Colorful MST

あさぷろで解いたときは解けなかった。面白い問題。
A - Colorful MST

問題

N頂点M辺のグラフがある。各頂点には色1から色Kまでのどれかの色が塗られているか、あるいはまだ色が塗られていない。
以下の操作を行ったときにできるグラフの最小全域木の重みの最小値を求めよ。どのようにしても最小全域木を作れない場合は-1を出力せよ。

  1. まだ色が塗られていない頂点に色1から色Kまでのどれかの色を塗る。別の頂点には別の色を塗ってよい。
  2. 同じ色の頂点を1点に潰して、K頂点のグラフを作る。このとき、対応する色の頂点が存在しないような色については、その頂点は0本の辺が接続することになる。

制約

  • 1 <= K <= N <= 10^5
  • 1 <= M <= 10^5
  • 1 <= (辺の重み) <= 10^9
  • 与えられるグラフは、単純とも連結とも限らない

解法

適当に(K - 1)辺(実行可能解)を取った時、その辺集合が全域木となるような色の塗り方は存在するだろうか? 存在するためには以下の条件が必要十分:

  • すでに塗られている頂点を色ごとに1点に潰した時、潰した後の点集合が森になっている。

(必要性): どのような塗り方をしても、塗られていない状態よりは潰れるので、森になりにくい。よって自明
(十分性): 塗り方を作ればよい。まだ塗られていない頂点に接続する辺1つにつき、まだ使われていない色を1つずつ使っていけばよい。
以上より、すでに塗られている頂点を同一視しながらKruskal法を実行するだけで解ける。

登場する典型

  • 実行可能解の条件を考える

実装上の注意点

  • オーバーフローの危険があるのでlong longを使う
  • ちょうど(K - 1)個の辺を選ぶ
    • 1敗 (は?)

提出: Submission #4343453 - CODE FESTIVAL 2017 Elimination Tournament Round 2 (Parallel) (C++)

const int N = 112222;
int a[N], b[N], w[N];

typedef pair<ll, PI> PLPI;

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  VI c(n);
  REP(i, 0, n) {
    cin >> c[i];
  }
  vector<PLPI> pool;
  REP(i, 0, m) {
    cin >> a[i] >> b[i] >> w[i];
    a[i]--, b[i]--;
    pool.push_back(PLPI(w[i], PI(a[i], b[i])));
  }
  sort(pool.begin(), pool.end());
  UnionFind uf(k + n);
  int conn = k;
  ll tot = 0;
  REP(i, 0, pool.size()) {
    if (conn <= 1) break;
    ll ww = pool[i].first;
    int x = pool[i].second.first;
    int y = pool[i].second.second;
    x = c[x] == 0 ? k + x : c[x] - 1;
    y = c[y] == 0 ? k + y : c[y] - 1;
    assert (x >= 0);
    assert (y >= 0);
    if (not uf.is_same_set(x, y)) {
      tot += ww;
      uf.unite(x, y);
      conn--;
    }
  }
  cout << (conn > 1 ? -1 : tot) << "\n";
}

まとめ

実行可能解の条件を考えるのも割とよく見る典型という気がする。

CODE FESTIVAL 2017 Exhibition A - Awkward

当時Code Festivalに参加していた時は、何をすればいいのか見当もつかず、出題陣のライブ解説も理解不能だったが、今解き直したらかなり簡単に思えた。A - Awkward

問題

N頂点の木が与えられる。木の頂点の並べ方はN!通りあるが、その中で以下を満たすものの個数を10^9 + 7で割った余りを求めよ。

  • どの2個の隣接する頂点も、隣同士にならない。

解法

包除原理を使う。以下の値をx = 0, ..., N - 1について数え上げることができればよい。

  • N - 1個の辺のうちx個を選ぶ。それらの辺については制約が破られている(隣同士になっている)ような並べ方の総数の合計。
    • 例えば入力例3 (N=5, b = [1, 1, 3, 3])では120, 192, 96, 16, 0となる。問題の答えは120 - 192 + 96 - 16 + 0 = 8。

これを求めるにはどうすれば良いだろうか? まず、辺の集合Sをfixしたときに、その集合Sについては制約が破られているような並べ方の総数を求めよう。辺集合に枝分かれがある(同じ頂点にSの3本以上の辺が接続している)ときは0通りである。それ以外の時を考える。Sを辺集合とした木の部分グラフは、1点と長さ1以上のパスの寄せ集めになっている。パスは列の中で一続きの部分列になること、およびどちらを列の先頭に持ってくるかが2通りあることを考えると、場合の数は(ものの個数)! * 2^(長さ1以上のパスの個数)であることがわかる。
次に、集合Sではなく集合の大きさx = |S|をfixしたときの和を計算したい。「(ものの個数)!」についてはあとでまとめて掛けることにして、「2^(長さ1以上のパスの個数)」の合計をもとめることにすると、これは以下のようなDPで計算することができる。

  • DP[v][x][k]: 頂点vを根とする部分木において、連結成分の個数がx個あり、vからは辺がk本伸びているときの、2^(長さ1以上のパスの個数)の合計

これは二乗の木 DP - (iwi) { 反省します - TopCoder部のテクニックを使えば、O(N^2)で計算することができる。

登場する典型

  • 包除原理
  • 2乗の木DP

実装上の注意点

  • 遷移が複雑なのでバグらせないようにする
  • 余計なループを回すとO(N^3)になるので回さないようにする
    • RustだとDP配列をそのまま返してしまうのが賢明な気がする

提出: Submission #4342066 - CODE FESTIVAL 2017 Exhibition (Parallel) (Rust)

// ModInt省略
// Depends on ModInt.rs
fn fact_init(w: usize) -> (Vec<ModInt>, Vec<ModInt>) {
    let mut fac = vec![ModInt::new(1); w];
    let mut invfac = vec![0.into(); w];
    for i in 1 .. w {
        fac[i] = fac[i - 1] * i as i64;
    }
    invfac[w - 1] = fac[w - 1].inv();
    for i in (0 .. w - 1).rev() {
        invfac[i] = invfac[i + 1] * (i as i64 + 1);
    }
    (fac, invfac)
}

fn dfs(ch: &[Vec<usize>], v: usize) -> Vec<[ModInt; 3]> {
    let mut dp = vec![[ModInt::new(0); 3]; 2];
    dp[1][0] = ModInt::new(1);
    for &w in &ch[v] {
        let sub = dfs(ch, w);
        let sub_sz = sub.len() - 1;
        let cur_sz = dp.len() - 1;
        let mut next_dp = vec![[ModInt::new(0); 3]; cur_sz + sub_sz + 1];
        for i in 1..sub_sz + 1 {
            for j in 1..cur_sz + 1 {
                // add one edge
                for k in 0..2 {
                    next_dp[i + j - 1][1] += sub[i][k] * dp[j][0];
                    next_dp[i + j - 1][2] += sub[i][k] * dp[j][1];
                }
                // don't add an edge
                for k in 0..3 {
                    for l in 0..3 {
                        next_dp[i + j][l] += sub[i][k] * dp[j][l]
                            * if k >= 1 { 2 } else { 1 };
                    }
                }
            }
        }
        dp = next_dp;
    }
    dp
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        b: [usize1; n - 1],
    }
    let mut ch = vec![vec![]; n];
    for i in 1..n {
        ch[b[i - 1]].push(i);
    }
    const W: usize = 3000;
    let mut invtbl = vec![ModInt::new(0); W];
    for i in 1..W {
        invtbl[i] = ModInt::new(i as i64).inv();
    }
    let (fac, _invfac) = fact_init(W);
    let dp = dfs(&ch, 0);
    let mut tot = ModInt::new(0);
    let mut factor = ModInt::new(1);
    for i in (0..n + 1).rev() {
        let mut t = ModInt::new(0);
        for k in 0..3 {
            t += dp[i][k] * fac[i]
                * if k >= 1 { 2 } else { 1 };
        }
        tot += t * factor;
        factor = -factor;
    }
    puts!("{}\n", tot);
}

まとめ

当時に比べこの手の問題が多く出題されているなど、界隈が進歩しているので、今出題するとしたら800点くらいになりそうな気がする。

CODE FESTIVAL 2018 Final I - Homework

F問題は解説を見ないとわからなかったがI問題は自力で解けた。
I - Homework

問題

荷物がN個ある。i番目の荷物はコスト2^A[i]、価値B[i]である。合計価値をK以上にするために必要なコストの合計を求めよ。

制約

  • 入力は全て整数
  • 1 <= N <= 10^5
  • 0 <= A[i] <= 30
  • 1 <= B[i] <= 10^9
  • 1 <= K <= \sum B[i]

解法

二分探索をすることにして、問題を「合計コストx以下で合計価値をK以上にできるか?」という形に変形する。

ここで、xの偶奇とコスト1の荷物をどうするかに着目しよう。xが奇数であれば、少なくとも1個はコスト1の荷物を取るべきである。またxが偶数であっても奇数であっても、最初に取る荷物以外の荷物は2個ずつ取っていくべきである。これを使うと、xの各ビットを下から見て、立っていたら一番価値の高い荷物を取り、そのあとそれ以外の荷物を2個まとめてコストが2倍の荷物として扱うとよいことがわかる。
これの計算量は、ほとんどの荷物の個数が毎ターン半分になること、最大1個の荷物がそれ以外に次のターンに持ち越されることを考えると、O(N + (ターン数)) = O(N + max A[i])である。

登場する典型

  • 二分探索
  • 1, 2, 2^2, ...という等比数列の典型パターン
    • 今回は下位ビットに着目するといけた

実装上の注意点

  • 二分探索の範囲
    • 上限はN * 2^30以上にすべき
    • 上限に応じてxの大きさも変わるので、ターン数も30ではなくもっと大きくしないといけない

提出: Submission #4325140 - CODE FESTIVAL 2018 Final (Parallel) (Rust)

const B: usize = 31;
const C: usize = 50;
 
// x: max time
fn can_pack(tbl: &[Vec<i64>], k: i64, x: i64) -> bool {
    let mut rem = k;
    let mut cur_bag = tbl[0].clone();
    for i in 0..C {
        cur_bag.sort();
        if (x >> i & 1) == 1 && cur_bag.len() >= 1 {
            rem -= cur_bag.pop().unwrap();
        }
        let mut nxt = vec![];
        while let Some(mut fst) = cur_bag.pop() {
            if let Some(snd) = cur_bag.pop() {
                fst += snd;
            }
            nxt.push(fst);
        }
        if i + 1 < B {
            nxt.extend_from_slice(&&tbl[i + 1]);
        }
        cur_bag = nxt;
    }
    rem <= 0
}
 
fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($format:expr) => (write!(out,$format).unwrap());
        ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
    }
    input! {
        n: usize,
        k: i64,
        ab: [(usize, i64); n],
    }
    let mut tbl = vec![vec![]; B];
    for (a, b) in ab {
        tbl[a].push(b);
    }
    let mut pass = 1 << C;
    let mut fail = 0;
    while pass - fail > 1 {
        let mid = (pass + fail) / 2;
        if can_pack(&tbl, k, mid) {
            pass = mid;
        } else {
            fail = mid;
        }
    }
    puts!("{}\n", pass);
}

まとめ

2の冪乗系コストの問題は、たまに見ると面白い。

全国統一プログラミング王決定戦本戦 F - Flights (他人の解法を見た)

20位以内に入りたければ、A問題からE問題は自明問題として高速に処理し、この問題かG問題のどちらかを解く必要があった。
F - Flights

問題

XY平面上にN個の点がある。i番目の点の座標は(X[i], Y[i])であり、どの2点の座標も異なる。この点たちの間に、以下の規則で無向辺を設ける:

  • X[i] <= X[j], Y[i] <= Y[j]のとき、頂点iと頂点jの間にコストC[j]の無向辺を設ける。

頂点Sから頂点Tへ移動するときの最短距離を求めよ。

制約

  • 2 <= N <= 10^5
  • 0 <= 座標 <= 10^9
  • 1 <= C[i] <= 10^9

解法

最短経路がどのような形をしているか考察してみよう。X[i] <= X[j], Y[i] <= Y[j]のとき、頂点jは頂点iの右上にあるということにする。明らかに、頂点jが頂点iの右上にあり頂点kが頂点jの右上にあるときはi -> j -> kという道を通る意味はない。このことから、最短経路はジグザグになっている、つまりS -> a_1 -> a_2 -> ... -> Tを最短経路としたときにa_1はSとa_2の右上にあり、a_3はa_2とa_4の右上にあり、…ということが成り立つ。(最初に他の頂点の右上になるのがa_1ではなくSの場合もある。)
a_1, a_2, ...として選ぶ意味がある頂点はどのような頂点だろうか? a_kがa_{k-1}の右上にあると仮定すると、一般性を失わず元の点集合にa_{k-1}の左下にある点はないと仮定してよい。なぜなら、そのような点があれば、それを代わりにa_{k-1}とすればよいからである。これを使うと、最適戦略においては以下の2種類の辺しか使われないことがわかる:

  • 各点vについて、vの左下にある頂点wであって、それより左下の点が存在しないような点wへの辺(v, w)
  • SまたはTの右上か左下にある点vへの辺(S, v)あるいは(T, v)

後者の辺はO(N)本しかないのでよい。前者について、もともと頂点集合を座標の辞書順にソートしておけば、辺を伸ばすべき頂点の列はならしO(1)で管理できる。しかし、頂点集合の大きさはO(N)程度であるため、このままではO(N^2)本の辺ができてしまう。これは以下のようにして解決できる。
一般性を失わず(Sの座標) < (Tの座標)とする。最適戦略はジグザグに右に進んでいく戦略である。このとき、辺を伸ばすべき頂点の列をKとして、各点vに対してKのどの点へ辺を伸ばせるかを考える。Kは左上から右下へと進んでいく点列で、座標でソートしている以上Kにはv以下のX座標を持つ点しか登場しないので、vから辺を伸ばせる頂点はY座標がvのY座標以下の点たち、つまりKの途中から最後まで、あるいは空列である。この列の先頭と最後をそれぞれst, enと呼ぶことにし、有向辺st -> v, v -> en を張り、enからstへ向かってKの頂点の間に逆向きに大きさ0の有向辺を張ることにする。(座標空間内では右下から左上に辺が伸びる。) こうすると、上で考慮した辺を張るのと同等であることがわかる。大きさ0の有向辺は別のvに対しても共有できるので、合計で張られる辺の総数はO(N)である。
こうしてできたグラフの上でダイクストラ法をすれば答えが計算できる。計算量はO(N log N)である。

登場する典型

  • 最適戦略の形を考える

実装上の注意点

  • 問題のグラフは無向グラフだが、長さ0の有向辺を追加するのでSとTの順番には気をつける必要がある。

提出: Submission #4316925 - 全国統一プログラミング王決定戦本戦 (Rust)

// Dijkstra省略

fn calc(xyc: &[(i64, i64, i64)],
        pool: &[(i64, i64, i64, usize)], s: usize, t: usize)
        -> i64 {
    let n = pool.len();
    let mut edges = vec![];
    let mut dedges = vec![];
    let mut st: Vec<(i64, usize)> = vec![];
    for &(_x, y, cost, curi) in pool {
        let mut added = true;
        if let Some(&(top, _idx)) = st.last() {
            if top <= y {
                added = false;
            }
        }
        if added {
            st.push((y, curi));
            if st.len() >= 2 {
                let other = st[st.len() - 2].1;
                dedges.push((curi, other, 0)); // reverse edge
            }
        } else {
            let mut fail = -1;
            let mut pass = st.len() as i64 - 1;
            while pass - fail > 1 {
                let mid = ((pass + fail) / 2) as usize;
                let (ym, _idxm) = st[mid];
                if ym <= y {
                    pass = mid as i64;
                } else {
                    fail = mid as i64;
                }
            }
            let pass = pass as usize;
            dedges.push((st[pass].1, curi, cost));
            dedges.push((curi, st[st.len() - 1].1, cost));
        }
    }
    for &v in &[s, t] {
        for i in 0..n {
            if i == v { continue; }
            if xyc[i].0 <= xyc[v].0 && xyc[i].1 <= xyc[v].1 {
                edges.push((i, v, xyc[v].2));
            }
            if xyc[i].0 >= xyc[v].0 && xyc[i].1 >= xyc[v].1 {
                edges.push((i, v, xyc[i].2));
            }
        }
    }
    let mut dijk = Dijkstra::new(n);
    for (u, v, x) in edges {
        dijk.add_edge(u, v, x);
        dijk.add_edge(v, u, x);
    }
    for (u, v, x) in dedges {
        dijk.add_edge(u, v, x);
    }
    let ans = dijk.solve(s, t, 1 << 57);
    ans
}
 
fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        s: usize1,
        t: usize1,
        xyc: [(i64, i64, i64); n]
    }
    let mut s = s;
    let mut t = t;
    // s comes before t in the lexicographical order
    if xyc[t] < xyc[s] {
        std::mem::swap(&mut s, &mut t);
    }
    let mut pool = vec![];
    for i in 0..n {
        let (x, y, c) = xyc[i];
        pool.push((x, y, c, i));
    }
    pool.sort();
    let ans = calc(&xyc, &pool, s, t);
    puts!("{}\n", ans);
}

まとめ

本番重み0の辺を張ればよさそうなことまでは気付けたが、逆向きの有向辺にすることを思いつかず爆死した。kanasii
この解法はcatupperさんのツイートを参考にして書いた。

全国統一プログラミング王決定戦本戦 D - Deforestation

本番は平面走査で通したけど、セグメント木で殴る解法にもちゃんと気付くべきだった。
D - Deforestation

問題

N本の竹がある。各竹の時刻0における高さは0で、毎秒1ずつ伸びる。
以下の行動をi = 1, ..., NのN回行うとき、総得点を求めよ。

  • 時刻T[i]に、L[i]番目からR[i]番目までの竹を根元から切る。それらの竹の長さの合計を得点とする。切られた竹も、その後伸び続ける。

解法

数列の上の以下のようなクエリを捌ければよい。

  • 区間和クエリ (L番目からR番目までの和を求める)
  • 区間ゼロ初期化クエリ (L番目からR番目までを0にする)
  • 区間加算クエリ (1番目からN番目までに1を加える)

これは以下のような遅延セグメント木で処理できる。

  • 要素: i64
  • 更新: (i64, i64)、(a, b)は要素xをax + bに変更するクエリを表す。

単位元および演算は以下の通り。

  • 要素の単位元: 0
  • 更新の単位元: (1, 0) (x |-> 1x + 0が恒等写像であるため)
  • 要素の演算: (+)
  • 更新の作用: ノードの高さ(根からの距離)をhとすると、xに(a,b)を作用させた結果はax + b * 2^h (理由: そのノードは2^h個の要素の和が格納されているため)
  • 更新の演算: (a, b) * (c, d) = (ac, bc + d) (理由: yにx |-> ax + bとx |-> cx + dをこの順で適用すると、acy + bc + dになるため)

以上を遅延セグメント木に落とし込むとできる。これらの演算を書いた遅延セグメント木を書くのは大変なので、演算部分を除いて抽象化したものをライブラリにして、演算はtraitの実装という形で与えるのがよいだろう。

登場する典型

  • 遅延セグメント木

実装上の注意点

  • 更新の演算でバグらせないように気をつける。今回の場合、「ゼロクリア」と「区間加算」を同時に処理する構造を考えようとするとバグらせるに決まっているので、両方を含む代数構造を考えるとよい。

提出: Submission #4309587 - 全国統一プログラミング王決定戦本戦 (Rust)

/**
 * Lazy Segment Tree. This data structure is useful for fast folding and updating on intervals of an array
 * whose elements are elements of monoid T. Note that constructing this tree requires the identity
 * element of T and the operation of T. This is monomorphised, because of efficiency. T := i64, biop = max, upop = (+)
 * Reference: http://d.hatena.ne.jp/kyuridenamida/20121114/1352835261
 * Verified by https://codeforces.com/contest/1114/submission/49759034
 */
pub trait ActionRing {
    type T: Clone + Copy; // data
    type U: Clone + Copy + PartialEq + Eq; // action
    fn biop(Self::T, Self::T) -> Self::T;
    fn update(Self::T, Self::U, height: usize) -> Self::T;
    fn upop(Self::U, Self::U) -> Self::U;
    fn e() -> Self::T;
    fn upe() -> Self::U; // identity for upop
}
pub struct LazySegTree<R: ActionRing> {
    n: usize,
    dep: usize,
    dat: Vec<R::T>,
    lazy: Vec<R::U>,
}

impl<R: ActionRing> LazySegTree<R> {
    pub fn new(n_: usize) -> Self {
        let mut n = 1;
        let mut dep = 0;
        while n < n_ { n *= 2; dep += 1; } // n is a power of 2
        LazySegTree {
            n: n,
            dep: dep,
            dat: vec![R::e(); 2 * n - 1],
            lazy: vec![R::upe(); 2 * n - 1]
        }
    }
    #[inline]
    fn lazy_evaluate_node(&mut self, k: usize, height: usize) {
        if self.lazy[k] == R::upe() { return; }
        self.dat[k] = R::update(self.dat[k], self.lazy[k], height);
        if k < self.n - 1 {
            self.lazy[2 * k + 1] = R::upop(self.lazy[2 * k + 1], self.lazy[k]);
            self.lazy[2 * k + 2] = R::upop(self.lazy[2 * k + 2], self.lazy[k]);
        }
        self.lazy[k] = R::upe(); // identity for upop
    }
    #[inline]
    fn update_node(&mut self, k: usize) {
        self.dat[k] = R::biop(self.dat[2 * k + 1], self.dat[2 * k + 2]);
    }
    fn update_sub(&mut self, a: usize, b: usize, v: R::U, k: usize, height: usize, l: usize, r: usize) {
        self.lazy_evaluate_node(k, height);

        // [a,b) and  [l,r) intersects?
        if r <= a || b <= l {return;}
        if a <= l && r <= b {
            self.lazy[k] = R::upop(self.lazy[k], v);
            self.lazy_evaluate_node(k, height);
            return;
        }

        self.update_sub(a, b, v, 2 * k + 1, height - 1, l, (l + r) / 2);
        self.update_sub(a, b, v, 2 * k + 2, height - 1, (l + r) / 2, r);
        self.update_node(k);
    }
    /* ary[i] = upop(ary[i], v) for i in [a, b) (half-inclusive) */
    #[inline]
    pub fn update(&mut self, a: usize, b: usize, v: R::U) {
        let n = self.n;
        let dep = self.dep;
        self.update_sub(a, b, v, 0, dep, 0, n);
    }
    /* l,r are for simplicity */
    fn query_sub(&mut self, a: usize, b: usize, k: usize, height: usize, l: usize, r: usize) -> R::T {
        self.lazy_evaluate_node(k, height);

        // [a,b) and  [l,r) intersect?
        if r <= a || b <= l {return R::e();}
        if a <= l && r <= b {return self.dat[k];}
        let vl = self.query_sub(a, b, 2 * k + 1, height - 1, l, (l + r) / 2);
        let vr = self.query_sub(a, b, 2 * k + 2, height - 1, (l + r) / 2, r);
        self.update_node(k);
        R::biop(vl, vr)
    }
    /* [a, b) (note: half-inclusive) */
    #[inline]
    pub fn query(&mut self, a: usize, b: usize) -> R::T {
        let n = self.n;
        let dep = self.dep;
        self.query_sub(a, b, 0, dep, 0, n)
    }
}

struct Monoid {}
impl ActionRing for Monoid {
    type T = i64;
    type U = (i64, i64);
    fn e() -> i64 { 0 }
    fn upe() -> Self::U { (1, 0) }
    fn biop(a: i64, b: i64) -> i64 {
        a + b
    }
    fn update(a: Self::T, (b, c): Self::U, height: usize) -> i64 {
        a * b + (c << height)
    }
    fn upop((a, b): Self::U, (c, d): Self::U) -> Self::U {
        (a * c, b * c + d)
    }
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($format:expr) => (write!(out,$format).unwrap());
        ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap())
    }
    input! {
        n: usize,
        tlr: [(i64, usize1, usize)],
    }
    let mut st = LazySegTree::<Monoid>::new(n);
    let mut last_t = 0;
    let mut tot = 0;
    for (t, l, r) in tlr {
        let diff = t - last_t;
        st.update(0, n, (1, diff));
        tot += st.query(l, r);
        st.update(l, r, (0, 0));
        last_t = t;
    }
    puts!("{}\n", tot);
}

まとめ

遅延セグメントツリーは実装が大変なので、うまい実装を書けるかどうかはライブラリ作成者の腕が問われる気がする。

NJPC2017 F - ダブルス (解説を見た)

何もわからなかったので解説を見た。
F - ダブルス

問題

無限に伸びる数直線上に2人の人間が立っている。2人の初期位置は0である。この2人は協力して以下の条件を満たしたい:

  • 時刻0以降に散発的に光点が現れるので、2人のうちのどちらかがその光点を叩く。光点は合計N回現れ、i番目の光点は時刻T[i]のときに場所X[i]に現れる。2人は速度V以下で動くことができる。

この条件を満たせるようなVの最小値を求めよ。

制約

  • 1 <= N <= 10^5
  • 1 <= T[i] <= 10^9
  • -10^6 <= X[i] <= 10^6
  • T[i]は狭義単調増加

解法

Vについての二分探索で判定問題に変換する。(「速度V以下で条件を満たせるか?」という問題に変換できる。)
dp[i][j] = (2人がi, jにいることがあり得るかどうか)というDPでこの問題を解くことはできるが、O(N^2)時間かかる。
そこで、状態のうち一つを圧縮して、dp[i] = (i番目までの光点が現れ、一人がiにいる場合、その時もう一人が存在し得る範囲)とするとうまく行くことが証明できる。遷移は以下の通り(dp[i] = [l, r]とし、D = V(T[i + 1] - T[i])を、時刻T[i]からT[i+1]の間に2人が移動可能な距離とする):

  • iにいる人がi+1に行く場合、dp[i] <- [l - D, r + D]
  • iにいない方の人がi+1に行く場合、dp[i] <- [X[i] - D, X[i] + D]

どちらか一方しか実現しない場合はそちらの区間を、両方実現する場合は両方の区間のunionをdp[i + 1]とすればよい。(unionが実際に区間になることの証明は解説を参考にしてください)
遷移はO(1)なので、この問題はO(N * log(V))で解ける。

登場する典型

  • 二分探索で最大化問題を判定問題に変換する
  • bool値のDPの状態の一つを値に持って行く

実装上の注意点

  • 2分探索のループ回数に気をつける
    • 時間に余裕があるので100回くらいやればよい
  • 最初時刻0のとき位置0にいる
    • 番兵などを使うと実装しやすい


提出: Submission #4272588 - NJPC2017 (C++)

// This solution is made after the author read the editorial.
bool ok(int n, const vector<double> &t, const vector<double> &x, double v) {
  vector<pair<double, double> > dp(n + 1);
  const double INF = 1e18;
  dp[0] = make_pair(0.0, 0.0);
  REP(i, 0, n) {
    double dist = v * (t[i + 1] - t[i]);
    dp[i + 1] = make_pair(INF, -INF);
    if (abs(x[i + 1] - x[i]) <= dist) {
      dp[i + 1].first = min(dp[i + 1].first, dp[i].first - dist);
      dp[i + 1].second = max(dp[i + 1].second, dp[i].second + dist);
    }
    if (dp[i].first - dist <= x[i + 1] && x[i + 1] <= dp[i].second + dist) {
      dp[i + 1].first = min(dp[i + 1].first, x[i] - dist);
      dp[i + 1].second = max(dp[i + 1].second, x[i] + dist);
    }
    if (dp[i + 1].first > dp[i + 1].second) return false;
  }
  return true;
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<double> t(n + 1), x(n + 1);
  REP(i, 0, n) cin >> t[i + 1] >> x[i + 1];
  double pass = 1e7, fail = 0;
  REP(i, 0, 100) {
    double mid = (pass + fail) / 2;
    if (ok(n, t, x, mid)) {
      pass = mid;
    } else {
      fail = mid;
    }
  }
  cout << setprecision(15) << pass << endl;
}

まとめ

最初実家DP + CHTかなと思ったが、CHTは大嘘で、ちゃんと問題の性質を調べる必要がある問題だった…。