結果

問題 No.3000 Optimal Run Length Encoding
ユーザー akakimidoriakakimidori
提出日時 2024-12-17 22:28:23
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 9,362 bytes
コンパイル時間 13,195 ms
コンパイル使用メモリ 403,364 KB
実行使用メモリ 285,572 KB
最終ジャッジ日時 2024-12-24 23:51:25
合計ジャッジ時間 142,139 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 262 ms
7,168 KB
testcase_02 AC 260 ms
7,168 KB
testcase_03 AC 248 ms
7,168 KB
testcase_04 AC 254 ms
7,168 KB
testcase_05 AC 239 ms
7,168 KB
testcase_06 AC 231 ms
7,168 KB
testcase_07 AC 243 ms
7,296 KB
testcase_08 AC 243 ms
7,296 KB
testcase_09 AC 234 ms
7,168 KB
testcase_10 AC 224 ms
7,168 KB
testcase_11 AC 233 ms
7,168 KB
testcase_12 AC 241 ms
7,168 KB
testcase_13 AC 229 ms
7,296 KB
testcase_14 AC 219 ms
7,168 KB
testcase_15 AC 215 ms
7,168 KB
testcase_16 AC 229 ms
7,168 KB
testcase_17 AC 214 ms
7,040 KB
testcase_18 AC 151 ms
5,632 KB
testcase_19 AC 345 ms
6,528 KB
testcase_20 AC 354 ms
6,016 KB
testcase_21 AC 383 ms
5,888 KB
testcase_22 AC 376 ms
5,888 KB
testcase_23 AC 350 ms
6,016 KB
testcase_24 AC 345 ms
6,144 KB
testcase_25 AC 349 ms
6,272 KB
testcase_26 AC 332 ms
6,144 KB
testcase_27 AC 300 ms
5,632 KB
testcase_28 AC 350 ms
5,760 KB
testcase_29 AC 396 ms
5,504 KB
testcase_30 AC 396 ms
5,248 KB
testcase_31 AC 416 ms
5,248 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 AC 2,646 ms
146,604 KB
testcase_46 AC 2,345 ms
163,692 KB
testcase_47 AC 2,546 ms
149,492 KB
testcase_48 AC 2,489 ms
164,208 KB
testcase_49 AC 2,340 ms
135,600 KB
testcase_50 AC 2,422 ms
162,988 KB
testcase_51 AC 2,428 ms
143,928 KB
testcase_52 AC 2,480 ms
142,656 KB
testcase_53 AC 2,584 ms
153,592 KB
testcase_54 AC 2,242 ms
136,564 KB
testcase_55 AC 2,746 ms
146,604 KB
testcase_56 AC 2,571 ms
131,860 KB
testcase_57 AC 2,455 ms
136,148 KB
testcase_58 AC 2,328 ms
149,820 KB
testcase_59 AC 2,604 ms
175,028 KB
testcase_60 AC 2,659 ms
146,480 KB
testcase_61 AC 2,574 ms
134,452 KB
testcase_62 AC 2,368 ms
136,816 KB
testcase_63 AC 2,453 ms
141,220 KB
testcase_64 AC 2,392 ms
163,820 KB
testcase_65 WA -
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 AC 1,142 ms
285,572 KB
testcase_71 AC 391 ms
33,728 KB
testcase_72 AC 793 ms
64,904 KB
testcase_73 AC 512 ms
69,356 KB
testcase_74 WA -
testcase_75 AC 441 ms
72,000 KB
testcase_76 WA -
testcase_77 AC 463 ms
45,344 KB
testcase_78 AC 709 ms
57,724 KB
testcase_79 AC 475 ms
44,052 KB
testcase_80 AC 634 ms
67,348 KB
testcase_81 AC 65 ms
5,248 KB
testcase_82 AC 1,018 ms
167,796 KB
testcase_83 AC 1,045 ms
166,192 KB
testcase_84 AC 1,048 ms
166,472 KB
testcase_85 AC 1,041 ms
162,092 KB
testcase_86 AC 1,019 ms
153,944 KB
testcase_87 AC 1,032 ms
179,680 KB
testcase_88 AC 1,033 ms
157,856 KB
testcase_89 AC 1,060 ms
179,676 KB
testcase_90 AC 970 ms
147,328 KB
testcase_91 AC 1,064 ms
152,512 KB
testcase_92 AC 1,040 ms
166,340 KB
testcase_93 AC 1,003 ms
165,968 KB
testcase_94 AC 1,061 ms
165,752 KB
testcase_95 AC 1,014 ms
165,208 KB
testcase_96 AC 1,012 ms
164,940 KB
testcase_97 AC 349 ms
58,320 KB
testcase_98 AC 298 ms
39,196 KB
testcase_99 AC 310 ms
41,324 KB
testcase_100 AC 320 ms
51,040 KB
testcase_101 AC 340 ms
52,864 KB
testcase_102 AC 431 ms
44,728 KB
testcase_103 AC 433 ms
46,060 KB
testcase_104 AC 465 ms
46,664 KB
testcase_105 AC 446 ms
44,800 KB
testcase_106 AC 489 ms
48,052 KB
testcase_107 AC 427 ms
42,876 KB
testcase_108 AC 446 ms
50,836 KB
testcase_109 AC 417 ms
35,192 KB
testcase_110 AC 485 ms
41,988 KB
testcase_111 AC 549 ms
49,156 KB
testcase_112 AC 766 ms
64,192 KB
testcase_113 AC 775 ms
64,100 KB
testcase_114 AC 778 ms
64,144 KB
testcase_115 AC 760 ms
63,996 KB
testcase_116 AC 769 ms
59,480 KB
testcase_117 AC 748 ms
64,128 KB
testcase_118 AC 759 ms
67,812 KB
testcase_119 AC 754 ms
58,860 KB
testcase_120 AC 752 ms
63,052 KB
testcase_121 AC 782 ms
62,828 KB
testcase_122 AC 774 ms
63,972 KB
testcase_123 AC 783 ms
62,000 KB
testcase_124 AC 760 ms
61,976 KB
testcase_125 AC 806 ms
87,632 KB
testcase_126 AC 848 ms
103,748 KB
testcase_127 AC 776 ms
63,976 KB
testcase_128 AC 807 ms
86,108 KB
testcase_129 AC 850 ms
90,300 KB
testcase_130 AC 798 ms
68,824 KB
testcase_131 AC 818 ms
89,212 KB
testcase_132 AC 1,089 ms
231,412 KB
testcase_133 AC 1,158 ms
226,540 KB
testcase_134 AC 1,121 ms
221,748 KB
testcase_135 AC 1,126 ms
213,184 KB
testcase_136 AC 1,044 ms
199,828 KB
testcase_137 AC 1,013 ms
197,620 KB
testcase_138 AC 1,015 ms
195,232 KB
testcase_139 AC 1,027 ms
192,904 KB
testcase_140 AC 1,026 ms
190,204 KB
testcase_141 AC 1,012 ms
186,040 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 + p as i32 + 1);
            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, 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) / 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