結果

問題 No.3000 Optimal Run Length Encoding
ユーザー akakimidoriakakimidori
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 327 ms
7,168 KB
testcase_02 AC 320 ms
7,168 KB
testcase_03 AC 299 ms
7,168 KB
testcase_04 AC 316 ms
7,168 KB
testcase_05 AC 284 ms
7,168 KB
testcase_06 AC 295 ms
7,296 KB
testcase_07 AC 312 ms
7,168 KB
testcase_08 AC 302 ms
7,296 KB
testcase_09 AC 286 ms
7,168 KB
testcase_10 AC 274 ms
7,296 KB
testcase_11 AC 291 ms
7,168 KB
testcase_12 AC 302 ms
7,168 KB
testcase_13 AC 299 ms
7,040 KB
testcase_14 AC 273 ms
7,168 KB
testcase_15 AC 278 ms
7,296 KB
testcase_16 AC 288 ms
7,168 KB
testcase_17 AC 283 ms
7,040 KB
testcase_18 AC 191 ms
5,632 KB
testcase_19 AC 446 ms
6,400 KB
testcase_20 AC 443 ms
6,016 KB
testcase_21 AC 441 ms
5,888 KB
testcase_22 AC 446 ms
6,016 KB
testcase_23 AC 449 ms
6,016 KB
testcase_24 AC 437 ms
6,144 KB
testcase_25 AC 433 ms
6,272 KB
testcase_26 AC 439 ms
6,144 KB
testcase_27 AC 392 ms
5,504 KB
testcase_28 AC 443 ms
5,760 KB
testcase_29 AC 491 ms
5,376 KB
testcase_30 AC 514 ms
5,248 KB
testcase_31 AC 525 ms
5,248 KB
testcase_32 AC 579 ms
5,248 KB
testcase_33 AC 639 ms
5,320 KB
testcase_34 AC 780 ms
13,192 KB
testcase_35 AC 469 ms
31,220 KB
testcase_36 AC 470 ms
31,096 KB
testcase_37 AC 471 ms
31,092 KB
testcase_38 AC 463 ms
31,096 KB
testcase_39 AC 468 ms
31,088 KB
testcase_40 AC 461 ms
30,320 KB
testcase_41 AC 466 ms
30,236 KB
testcase_42 AC 479 ms
31,348 KB
testcase_43 AC 476 ms
31,220 KB
testcase_44 AC 465 ms
30,324 KB
testcase_45 AC 3,914 ms
144,664 KB
testcase_46 AC 3,342 ms
163,440 KB
testcase_47 AC 4,152 ms
146,724 KB
testcase_48 AC 3,527 ms
162,904 KB
testcase_49 AC 4,120 ms
135,428 KB
testcase_50 AC 3,612 ms
164,392 KB
testcase_51 AC 3,614 ms
153,404 KB
testcase_52 AC 3,474 ms
142,328 KB
testcase_53 AC 3,629 ms
153,976 KB
testcase_54 AC 3,320 ms
136,296 KB
testcase_55 AC 3,821 ms
147,732 KB
testcase_56 AC 3,554 ms
129,456 KB
testcase_57 AC 3,520 ms
137,096 KB
testcase_58 AC 3,357 ms
149,692 KB
testcase_59 AC 3,874 ms
176,916 KB
testcase_60 AC 3,770 ms
147,856 KB
testcase_61 AC 3,777 ms
131,320 KB
testcase_62 AC 3,369 ms
136,940 KB
testcase_63 AC 3,778 ms
141,420 KB
testcase_64 AC 3,302 ms
163,436 KB
testcase_65 AC 834 ms
52,764 KB
testcase_66 AC 549 ms
32,756 KB
testcase_67 AC 833 ms
52,288 KB
testcase_68 AC 526 ms
32,628 KB
testcase_69 AC 835 ms
44,784 KB
testcase_70 AC 1,552 ms
285,572 KB
testcase_71 AC 547 ms
33,600 KB
testcase_72 AC 1,057 ms
65,416 KB
testcase_73 AC 710 ms
69,616 KB
testcase_74 AC 1,123 ms
69,836 KB
testcase_75 AC 586 ms
72,008 KB
testcase_76 AC 1,133 ms
75,804 KB
testcase_77 AC 628 ms
45,096 KB
testcase_78 AC 963 ms
57,756 KB
testcase_79 AC 659 ms
44,212 KB
testcase_80 AC 874 ms
67,344 KB
testcase_81 AC 82 ms
5,248 KB
testcase_82 AC 1,408 ms
167,672 KB
testcase_83 AC 1,421 ms
166,172 KB
testcase_84 AC 1,389 ms
166,344 KB
testcase_85 AC 1,388 ms
162,220 KB
testcase_86 AC 1,352 ms
153,944 KB
testcase_87 AC 1,415 ms
179,420 KB
testcase_88 AC 1,369 ms
157,824 KB
testcase_89 AC 1,431 ms
179,416 KB
testcase_90 AC 1,336 ms
147,328 KB
testcase_91 AC 1,356 ms
152,388 KB
testcase_92 AC 1,370 ms
166,216 KB
testcase_93 AC 1,410 ms
165,840 KB
testcase_94 AC 1,397 ms
165,832 KB
testcase_95 AC 1,377 ms
165,168 KB
testcase_96 AC 1,361 ms
164,812 KB
testcase_97 AC 480 ms
58,324 KB
testcase_98 AC 389 ms
46,108 KB
testcase_99 AC 351 ms
41,452 KB
testcase_100 AC 423 ms
51,172 KB
testcase_101 AC 473 ms
52,868 KB
testcase_102 AC 556 ms
44,680 KB
testcase_103 AC 577 ms
46,108 KB
testcase_104 AC 646 ms
46,660 KB
testcase_105 AC 572 ms
44,872 KB
testcase_106 AC 636 ms
48,544 KB
testcase_107 AC 576 ms
43,884 KB
testcase_108 AC 628 ms
50,724 KB
testcase_109 AC 537 ms
38,924 KB
testcase_110 AC 610 ms
41,760 KB
testcase_111 AC 696 ms
49,496 KB
testcase_112 AC 1,001 ms
64,448 KB
testcase_113 AC 1,007 ms
64,484 KB
testcase_114 AC 991 ms
64,420 KB
testcase_115 AC 1,004 ms
64,636 KB
testcase_116 AC 986 ms
59,736 KB
testcase_117 AC 1,010 ms
64,256 KB
testcase_118 AC 1,005 ms
68,196 KB
testcase_119 AC 972 ms
60,012 KB
testcase_120 AC 990 ms
63,308 KB
testcase_121 AC 983 ms
62,828 KB
testcase_122 AC 976 ms
64,228 KB
testcase_123 AC 1,065 ms
62,132 KB
testcase_124 AC 988 ms
62,360 KB
testcase_125 AC 1,054 ms
88,020 KB
testcase_126 AC 1,087 ms
104,132 KB
testcase_127 AC 1,003 ms
64,104 KB
testcase_128 AC 1,054 ms
86,236 KB
testcase_129 AC 1,059 ms
90,564 KB
testcase_130 AC 1,009 ms
69,204 KB
testcase_131 AC 1,063 ms
89,596 KB
testcase_132 AC 1,477 ms
231,488 KB
testcase_133 AC 1,600 ms
226,664 KB
testcase_134 AC 1,550 ms
221,744 KB
testcase_135 AC 1,542 ms
213,180 KB
testcase_136 AC 1,456 ms
199,740 KB
testcase_137 AC 1,494 ms
197,748 KB
testcase_138 AC 1,430 ms
195,308 KB
testcase_139 AC 1,411 ms
192,904 KB
testcase_140 AC 1,410 ms
190,200 KB
testcase_141 AC 1,401 ms
186,124 KB
testcase_142 AC 1,345 ms
175,748 KB
権限があれば一括ダウンロードができます

ソースコード

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 ----------
0