home/compro

https://atcoder.jp/contests/typical90/tasks external_link

2022/04/04

精進

うーんREの原因がわかっていないな...

https://atcoder.jp/contests/abc246/submissions/30714526 external_link

普通のBFSが通ってるように見える. うーん

https://atcoder.jp/contests/abc246/submissions/30717048 external_link

というかこの差分の持ち方かっこいいな

const DIR: [(usize, usize); 4] = [
    (1, 1),
    (1, 1_usize.wrapping_neg()),
    (1_usize.wrapping_neg(), 1),
    (1_usize.wrapping_neg(), 1_usize.wrapping_neg()),
];

うーん解けない バグったプログラムを一定時間以上眺めてても解けないんだよなあ

multisetがないから, できないみたいになってる・

AVLTreeを実装するぞ!!!

AVL木, 赤黒木, B木を造ってベンチマークを取ろう!! Rust, Goで!!!

  • ABC 245 バチャ

倒せ!!

→Multiset問題が倒せない..

https://atcoder.jp/contests/abc245/tasks/abc245_e external_link

典型問題を解く

2022/04/05

BTreeMapがfirst, lastに対応しないなら自分で対応させればいいんじゃ

https://github.com/eqv/avl_tree external_link NodeとAVLTreeのルートをわけるのはなんでなんだろね

あと, Iteratorが別に実装してるのが微妙に気になる https://doc.rust-lang.org/src/alloc/collections/btree/map.rs.html#2091 external_link なんか, 怖いことやってるなBTreeのiteratorは

2022/04/06

まず普通のBSTを書くべきか 読みながら, 機能ごとにうつしていくか

  • insertを実装
  • deleteを実装
  • getを実装
  • get_orを実装

とりあえず, コードを読んで理解はした 最終的に非再帰にしたい https://stnkien.hatenablog.com/entry/avl-tree external_link

2022/04/07

2022/04/08

コドフォをやる

2022/04/16

  • rotate_heavy_{left, right}を実装した
fn is_sorted_left<K: Ord, D>(node: &Box<Node<K, D>>) -> bool {
    node.left.as_ref().map_or(true, |succ| succ.key < node.key)
}

fn is_sorted_right<K: Ord, D>(node: &Box<Node<K, D>>) -> bool {
    node.right.as_ref().map_or(true, |succ| succ.key > node.key)
}

fn is_avl_node<K: Ord, D>(node: &Box<Node<K, D>>) -> bool {
    let sorted = is_sorted_left(node) && is_sorted_right(node);
    let balanced = node.height == cmp::max(height(&node.left), height(&node.right)) + 1;
    return sorted && balanced;
}

pub fn is_avl_tree<K: Ord, D>(root: &Option<Box<Node<K, D>>>) -> bool {
    (*root).as_ref().map_or(true, is_avl_node)
}

2022/04/18

  • AVL木, マップを作る