練習メモ3-1

あ
GoodBye2015

c
ふつうに分割統治するとNlogNだから累積和持ってクエリ数×logNで分割統治した。
想定はDPで線形らしい。

fn exec() {
    let mut sc = Scanner::new();
    let row: usize = sc.ne();
    let col: usize = sc.ne();
    let mut fld = vec![Vec::new(); row];
    for i in 0..row {
        fld[i] = sc.ne::<String>().into_bytes();
    }
    let mut cnt1 = vec![vec![0; col]; row + 1];
    for j in 0..col {
        for i in 0..row - 1 {
            if fld[i][j] == b'.' && fld[i + 1][j] == b'.' {
                cnt1[i + 1][j] = 1;
            }
            cnt1[i + 1][j] += cnt1[i][j];
        }
    }
    let mut cnt2 = vec![vec![0; col]; row + 1];
    for j in 0..col - 1 {
        for i in 0..row {
            if fld[i][j] == b'.' && fld[i][j + 1] == b'.' {
                cnt2[i + 1][j] = 1;
            }
            cnt2[i + 1][j] += cnt2[i][j];
        }
    }
    fn calc(cnt1: &Vec<Vec<usize>>,
            cnt2: &Vec<Vec<usize>>,
            l: usize,
            r: usize,
            y: &(usize, usize))
            -> usize {
        if l >= r {
            return 0;
        }
        if l + 1 == r {
            let cnt = cnt1[y.1 - 2][l] - cnt1[y.0 - 1][l];
            return cnt;
        }
        let mid = (l + r) / 2;
        let a = calc(cnt1, cnt2, l, mid, y);
        let b = calc(cnt1, cnt2, mid, r, y);
        a + b + cnt2[y.1 - 1][mid - 1] - cnt2[y.0 - 1][mid - 1]
    }
    let q: usize = sc.ne();
    for _ in 0..q {
        let r1 = sc.ne::<usize>();
        let c1 = sc.ne::<usize>() - 1;
        let r2 = sc.ne::<usize>() + 1;
        let c2 = sc.ne::<usize>();
        let ret = calc(&cnt1, &cnt2, c1, c2, &(r1, r2));
        println!("{}", ret);
    }
}

d
dp[i][j] := s[i..j - 1]が最後になるやつの数
でDP。
文字列比較するからやばいなあTLEかなあと思ってだしたら1540msくらいで通った。
想定解は
nxt[i][j] := s[i + x] != s[j + x]が成り立つような最小のx
をDPで前計算して使うのだったらしい。
このテク使えそうだから覚えとこ。

fn exec() {
    let mut sc = Scanner::new();
    let n: usize = sc.ne();
    let s = sc.ne::<String>().into_bytes();
    let mut dp = vec![vec![0i64; n]; n];
    let mut nxt = vec![vec![0usize; n + 1]; n + 1];
    for i in (0..n).rev() {
        for j in 0..n {
            if s[i] == s[j] {
                nxt[i][j] = nxt[i + 1][j + 1] + 1;
            } else {
                nxt[i][j] = 0;
            }
        }
    }
    const MOD: i64 = 1000000007;
    for i in 0..n {
        if i == 0 {
            for j in 0..n {
                dp[i][j] = 1;
            }
            continue;
        }
        if s[i] == b'0' {
            continue;
        }
        let mut cand = 0;
        let mut id = i;
        for j in i..n {
            if id > 0 {
                id -= 1;
                let len = j - i + 1;
                if len > nxt[i][id] {
                    let plus = nxt[i][id];
                    if s[id + plus] < s[i + plus] {
                        dp[i][j] += dp[id][i - 1];
                    }
                }
                dp[i][j] += cand;
                cand += dp[id][i - 1];
            } else {
                dp[i][j] += cand;
            }
            dp[i][j] %= MOD;
        }
    }
    let mut ans = 0;
    for i in 0..n {
        ans += dp[i][n - 1];
        ans %= MOD;
    }
    println!("{}", ans);
}

E
ややこしい貪欲。
解いてない。

日本橋ハーフマラソン
ビームサーチがバグって敗北した。

みんなのプロコン
c
なんか２ケースだけWAするけど面倒だからもういいや。
d
全然サンプル合わんと思ったらライブラリバグってて爆笑

fn exec() {
    let mut sc = Scanner::new();
    let q: usize = sc.ne();
    let k: i64 = sc.ne();
    let mut query = vec![Vec::new(); q];
    let mut map = BTreeMap::new();
    for i in 0..q {
        let z: usize = sc.ne();
        let z = if z == 1 { 2 } else { 1 };
        for j in 0..z {
            let x: i64 = sc.ne();
            query[i].push(x);
            if j == 0 {
                map.insert(x, 0usize);
            }
        }
    }

    let mut cnt = 0;
    for x in &mut map {
        *x.1 = cnt;
        cnt += 1;
    }
    let mut seg: SegTree<P> = SegTree::new(q);
    let mut bval = 0;
    for x in &map {
        let val = x.0 * k;
        seg.update(*x.1, (val - bval, 0));
        bval = val;
    }
    let mut fwt = FenwickTree::new(q, 0i64);
    let mut fwt2 = FenwickTree::new(q, 0i64);
    for i in 0..q {
        if query[i].len() == 1 {
            let d = query[i][0];
            let id = map[&d];
            let ans1 = fwt.sum(id + 1);
            let ans2 = {
                let rest = seg.query(0, id + 1);
                let sum = fwt2.sum(id + 1);
                sum - rest.1
            };
            println!("{}", ans1 + ans2);
        } else {
            let d = query[i][0];
            let x = query[i][1];
            let id = map[&d];
            let now = seg.query(id, id + 1);
            let consume = min(now.0, x);
            let upd = now.0 - consume;
            seg.update(id, (upd, now.1));
            fwt.add(id, consume);
            // println!("{:?}, {}", now, x);
            if now.0 < x {
                let sa = x - now.0;
                seg.update(id, (0, now.1 + sa));
                // println!("{:?}", seg.query(id, id + 1));
                fwt2.add(id, sa);
            }
        }
    }
}

#[allow(dead_code)]
struct FenwickTree<T> {
    zero: T,
    n: usize,
    data: Vec<T>,
}
use std::ops::AddAssign;
#[allow(dead_code)]
impl<T: Copy + AddAssign> FenwickTree<T> {
    fn new(n_: usize, z_: T) -> FenwickTree<T> {
        FenwickTree {
            zero: z_,
            n: n_,
            data: vec![z_; n_],
        }
    }
    //sum of [0, j)
    fn sum(&self, j: usize) -> T {
        let mut res = self.zero;
        let mut x = j as i64 - 1;
        while x >= 0 {
            res += self.data[x as usize];
            x = (x & (x + 1)) - 1;
        }
        res
    }
    // add w to a[j]
    fn add(&mut self, j: usize, w: T) {
        let mut x = j;
        while x < self.n {
            self.data[x] += w;
            x |= x + 1;
        }
    }
}

#[allow(dead_code)]
struct SegTree<T> {
    n: usize,
    data: Vec<T>,
}

use std::fmt::Debug;
// 根ノードを1とする
#[allow(dead_code)]
impl<T: Monoid<T> + Debug> SegTree<T> {
    fn new(n_: usize) -> SegTree<T> {
        let mut res_n = 1;
        while res_n < n_ {
            res_n <<= 1;
        }
        SegTree::<T> {
            n: res_n,
            data: vec![T::ide(); 2 * res_n],
        }
    }
    fn fromseq(seq: &Vec<T>) -> SegTree<T> {
        let n_ = seq.len();
        let mut res_seg = SegTree::<T>::new(n_);
        for i in 0..n_ {
            res_seg.data[i + res_seg.n] = seq[i].clone();
        }
        for i in (1..res_seg.n).rev() {
            res_seg.data[i] = T::merge(&res_seg.data[2 * i], &res_seg.data[2 * i + 1])
        }
        res_seg
    }
    fn update(&mut self, k_: usize, x: T) {
        let mut k = k_ + self.n;
        self.data[k] = x;
        while k > 0 {
            k >>= 1;
            self.data[k] = T::merge(&self.data[k * 2], &self.data[k * 2 + 1]);
        }
    }
    fn query(&mut self, ql: usize, qr: usize) -> T {
        let n_ = self.n;
        self.__query(ql, qr, 1, 0, n_)
    }
    fn __query(&mut self, ql: usize, qr: usize, k: usize, nl: usize, nr: usize) -> T {
        if nr <= ql || qr <= nl {
            return T::ide();
        };
        if ql <= nl && nr <= qr {
            return self.data[k].clone();
        };
        let mid = (nl + nr) / 2;
        let vl = self.__query(ql, qr, k * 2, nl, mid);
        let vr = self.__query(ql, qr, k * 2 + 1, mid, nr);
        T::merge(&vl, &vr)
    }
}

座圧嫌い。あってもなくても何も変わらないと思うし知識ゲー度上げるだけな気がする。
解法だが、seg木に
(余ってる数, 引ききれなかった数)
を持たせていい感じにマージする。
一日の生産数がKだから、座圧して前の日付からその日付までに生産したやつをとりあえず使っていい数として最初にseg木に持たせる。
ちなみにライブラリがバグっていたというのは

k >>= 1;

のところが

k = (k - 1) >> 1;

になっていた。
なんでか知らんが一回このセグ木rootが１になるように書きかえたんだよね。で、修正してなかったと。
デバッグ出力させた時に気づくべきだったんだよなあ。明らかに変なバグり方してたし。

敗北が続き本当に辛いが、負ける代わりにverifyされたライブラリを手に入れたと思おう（あらかじめ確認しとけや、という話だが）。