結果

問題 No.3000 Optimal Run Length Encoding
ユーザー akakimidori
提出日時 2024-12-17 23:42:54
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 4,152 ms / 10,000 ms
コード長 9,376 bytes
コンパイル時間 24,677 ms
コンパイル使用メモリ 377,096 KB
実行使用メモリ 285,572 KB
最終ジャッジ日時 2024-12-25 19:52:46
合計ジャッジ時間 213,712 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 142
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

fn main() {
    input! {
        t: usize,
        ask: [chars; t],
    }
    use std::io::Write;
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for s in ask {
        let ans = solve(s);
        writeln!(out, "{}", ans).ok();
    }
}
// run 列挙で出てくる(p,l,r) について、 sum (r-l-2p) がO(NlogN) らしい
fn solve(s: Vec<char>) -> String {
    let run = run_enumerate(&s);
    let mut add = vec![];
    let mut del = vec![];
    for (k, &(p, l, r)) in run.iter().enumerate() {
        let s = l + 2 * p;
        add.push((s, k));
        del.push((r, k));
    }
    add.sort_by_key(|p| !p.0);
    del.sort_by_key(|p| !p.0);
    let inf = s.len() as i32 + 2;
    // dp[i]: S[..i] を最適に圧縮した時の長さ, 直前のやつ
    let mut dp = vec![(inf, !0); s.len() + 1];
    dp[0].0 = 0;
    let mut once = (inf, 0);
    let mut map = std::collections::BTreeMap::new();
    for i in 0..=s.len() {
        // S1 の遷移
        dp[i].chmin((once.0 + i as i32, once.1));
        // Sk の遷移を追加
        while add.last().map_or(false, |p| p.0 == i) {
            let k = add.pop().unwrap().1;
            map.insert(k, vec![]);
        }
        // 計算
        for (&k, list) in map.iter_mut() {
            let (p, l, _) = run[k];
            let pos = (i - l) % p;
            if list.len() == pos {
                list.push(Solver::new(p));
            }
            list[pos].add_src(i - 2 * p, dp[i - 2 * p].0);
            dp[i].chmin(list[pos].find_at(i));
        }
        // dp[i] が確定、S1の更新と使い切ったrunの削除
        let p = dp[i];
        once = once.min((p.0 - i as i32 + 1, i));
        while del.last().map_or(false, |p| p.0 == i) {
            let k = del.pop().unwrap().1;
            map.remove(&k);
        }
    }
    let mut ans = vec![];
    let mut pos = s.len();
    while pos > 0 {
        let (_, l) = dp[pos];
        let p = calc_period(&s[l..pos]);
        let q = (pos - l) / p;
        ans.extend(q.to_string().chars().rev());
        ans.extend(s[l..(l + p)].iter().cloned().rev());
        pos = l;
    }
    ans.reverse();
    ans.into_iter().collect()
}
fn calc_period<T: Eq>(a: &[T]) -> usize {
    let z = z_algorithm(a);
    for i in 1..a.len() {
        if z[i] == a.len() - i && a.len() % i == 0 {
            return i;
        }
    }
    a.len()
}
// run ごとの遷移を管理する
type Value = (i32, usize, usize);
struct Solver {
    period: usize,
    que: Vec<FoldableQueue<Value, fn(&Value, &Value) -> Value>>,
}
impl Solver {
    fn new(p: usize) -> Self {
        Self {
            period: p,
            que: vec![],
        }
    }
    fn add_src(&mut self, x: usize, v: i32) {
        if self.que.is_empty() {
            self.que.push(FoldableQueue::new(min_sp));
        }
        self.que[0].push_back((v + 1 + self.period as i32, x, x + self.period * 9));
    }
    fn find_at(&mut self, x: usize) -> (i32, usize) {
        let mut val = (std::i32::MAX, 0);
        let mut i = 0;
        while i < self.que.len() {
            while self.que[i].front().map_or(false, |p| p.2 < x) {
                let (v, x, r) = self.que[i].pop_front().unwrap();
                if i + 1 == self.que.len() {
                    self.que.push(FoldableQueue::new(min_sp));
                }
                self.que[i + 1].push_back((v + 1, x, r + self.period * 9 * 10usize.pow(i as u32 + 1)));
            }
            if let Some(v) = self.que[i].find() {
                val = val.min((v.0, v.1));
            }
            i += 1;
        }
        val
    }
}
fn min_sp(a: &Value, b: &Value) -> Value {
    std::cmp::min(*a, *b)
}
fn run_enumerate<T: Eq>(a: &[T]) -> Vec<(usize, usize, usize)> {
    let mut a = a.iter().collect::<Vec<_>>();
    let n = a.len();
    let mut memo = vec![vec![]; n / 2 + 1];
    for i in 0..2 {
        let mut list = vec![];
        let mut dfs = vec![(0, n)];
        while let Some((l, r)) = dfs.pop() {
            if r - l <= 1 {
                continue;
            }
            let m = (l + r + i) / 2;
            dfs.push((l, m));
            dfs.push((m, r));
            let b = a[l..m].iter().rev().collect::<Vec<_>>();
            let x = z_algorithm(&b);
            let c = a[m..r].iter().chain(a[l..r].iter()).collect::<Vec<_>>();
            let y = z_algorithm(&c);
            for i in 1..(m - l + 1) {
                let lb = if i < x.len() { m - i - x[i] } else { l };
                let rb = m + (r - m).min(y[r - l - i]);
                if rb - lb >= 2 * i {
                    list.push((i, lb, rb));
                }
            }
        }
        if i == 1 {
            list.iter_mut().for_each(|p| *p = (p.0, n - p.2, n - p.1));
        }
        for (p, l, r) in list {
            memo[p].push((l, r));
        }
        a.reverse();
    }
    let mut ans = vec![];
    let mut set = std::collections::BTreeSet::new();
    for (pd, mut p) in memo.into_iter().enumerate().skip(1) {
        p.sort_by_key(|p| (p.0, !p.1));
        p.dedup_by(|a, b| a.1 <= b.1);
        for (l, r) in p {
            if set.insert((l, r)) {
                ans.push((pd, l, r));
            }
        }
    }
    ans
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
fn z_algorithm<T: Eq>(s: &[T]) -> Vec<usize> {
    let len = s.len();
    let mut a = vec![0; len];
    a[0] = len;
    let mut i = 1;
    let mut j = 0;
    while i < len {
        while i + j < len && s[j] == s[i + j] {
            j += 1;
        }
        a[i] = j;
        if j == 0 {
            i += 1;
            continue;
        }
        let mut k = 1;
        while i + k < len && k + a[k] < j {
            a[i + k] = a[k];
            k += 1;
        }
        i += k;
        j -= k;
    }
    a
}
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
    fn chmin(&mut self, x: Self) -> bool;
    fn chmax(&mut self, x: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, x: Self) -> bool {
        *self > x && {
            *self = x;
            true
        }
    }
    fn chmax(&mut self, x: Self) -> bool {
        *self < x && {
            *self = x;
            true
        }
    }
}
// ---------- end chmin, chmax ----------
// ---------- begin Foldable Qeque ----------
pub struct FoldableQueue<T, F> {
    front: Vec<(T, T)>,
    back: Vec<(T, T)>,
    op: F,
}
impl<T, F> FoldableQueue<T, F>
where
    T: Clone,
    F: Fn(&T, &T) -> T,
{
    pub fn new(op: F) -> Self {
        FoldableQueue {
            front: Vec::new(),
            back: Vec::new(),
            op: op,
        }
    }
    pub fn find(&self) -> Option<T> {
        match (self.front.last(), self.back.last()) {
            (Some(a), Some(b)) => Some((self.op)(&a.1, &b.1)),
            (x, y) => x.or(y).map(|p| p.1.clone()),
        }
    }
    pub fn clear(&mut self) {
        self.front.clear();
        self.back.clear();
    }
    pub fn len(&self) -> usize {
        self.front.len() + self.back.len()
    }
    pub fn push_back(&mut self, val: T) {
        let sum = self
            .back
            .last()
            .map_or_else(|| val.clone(), |p| (self.op)(&p.1, &val));
        self.back.push((val, sum));
    }
    pub fn pop_front(&mut self) -> Option<T> {
        if self.front.is_empty() {
            let mut back = std::mem::take(&mut self.back);
            for (v, _) in back.drain(..).rev() {
                let sum = self
                    .front
                    .last()
                    .map_or_else(|| v.clone(), |p| (self.op)(&v, &p.1));
                self.front.push((v, sum));
            }
            self.back = back;
        }
        self.front.pop().map(|p| p.0)
    }
    pub fn front(&self) -> Option<&T> {
        self.front
            .last()
            .map_or_else(|| self.back.get(0).map(|p| &p.0), |p| Some(&p.0))
    }
}
// ---------- end Foldable Qeque ----------
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0