ICPC2020 国内予選参加記

niu_mogu_moguでugisとplayrollerで組んで参加しました. うにもぐもぐ. コンテスト前 library-checker-porblemsをクローンしてきた. 16:30まで授業だったので, 授業を途中でブッチしました. 教員から「結果残してね♡」と言われる. コンテスト なんかアクセス…

hatena blogからGithub Pages + Hugo に移しました

はてなグループが消えてしまって, 競技プログラミングの記事が消えていくのをみて 僕も何か対策をしないとなあと思ってこうなりました toptreeとか消えるのいやだからね... How github.com これを使いました 画像が何故かダウンロードされなかったのでそれを…

約数畳み込みを使って最大公約数と集合をうまく扱うメモ

書いて置かないと頭に置いておけない気がしたのでメモを残す. 間違ってたらごめん これについて気になったので メビウス関数とかを導入するとより形式的に約数とかを扱えるようになるのかなあ— Niuez (@xiuez) 2020年1月22日 概要 約数畳み込み メビウス関数…

Suffix Array と LCP と 文字列検索の実装をした

この土日のメモです. SAとLCPのお気持ちをまとめたくなっただけ. 間違ってたらごめん 文字列アルゴの勉強する気が起きないたった一つの理由: Rolling Hash— νιυεζ (@xiuez) 2019年12月13日 これをやめたいので, 手始めにSuffix Arrayを使った文字列検索をや…

動的木上の最小シュタイナー木をtoptreeで解く

この記事は「データ構造とアルゴリズム Advent Calendar 2019」 14日目の記事です. 13日目は@ajalabさんのRun-Length FM-Index - koki, 15日目は@minaminaoさんのMerkle Patricia Tree まわりです. toptreeとは toptreeは今年競プロ界隈で話題になった動的木…

BFS Numbering

niuez.github.io

Toptree - Link & Cut編

niuez.hatenablog.com 引き続き, toptreeの解説をしていきます. Link link(v, w): 頂点vとwを辺vwで結ぶをします. 場合分けが多すぎるんじゃ が, vの次数が0, 1, 2以上で処理が変わり, またwの次数が0, 1, 2以上で処理が変わります. (ちなみに論文はどちらも…

Toptree 導入編

みんな日本語記事を待っていたはず....! toptreeがどんな感じで動いているのかを書いてみます 実装はここにあります https://github.com/niuez/toptree-rust 0. toptree is なに toptreeはlink-cut treeの上位互換です. 木を切ったりつなげたり, パスのクエ…

top-tree実装体験木

読者層が限定されすぎていませんか? Link Cut Treeを書いたことがない人はこちら! ei1333.hateblo.jp 部分木クエリについてはこちら! beet-aizu.hatenablog.com 最遠点クエリについてはこちら! ei1333.hateblo.jp え〜っと, 多分toptreeが書けました. 多…

ダイクストラとポテンシャルのはなし

はじめまして, niuezといいます. 競プロを少ししています. 最近勉強したことのメモ書きをしておきます. ダイクストラ法 ダイクストラ法(Dijkstra)は負の長さの無いグラフで始点からの最短距離を求めるアルゴリズムです. 具体的には 距離が未確定の頂点の中で…