この記事は IQ1アドベントカレンダー2019 の 5日目の記事です。adventar.org今回はちょっとした小ネタ記事として、splay treeのvisualizationを簡易的に作った話を書きます。

(2019/09/15 20:50頃追記) ただAuxiliary Treeと書くと(一般的すぎて)齟齬を生む可能性が高いので、タイトル及び一部文章を変更しました。申し訳ないです。今回はLCAをベースに構築するAuxiliary Treeについて取り上げてます。最近、LCAを元に構築する Auxil…

グラフのchain decompositionと、それを使って橋と関節点を求める手法のメモ橋と関節点を求める手法といえばlowlinkを用いた手法が存在するが、他の手法としてchain decompositionを用いた手法が存在する。(WikipediaのBridge (graph theory)とBiconnected c…

Segment Tree Beats(SGT Beats)のHistoric Informationまわりについて自分が理解した範囲のメモこの記事は以下の続き。これらの説明を前提に書いてある。

Historic Informationまわりの勉強で解いた。解法メモuoj.ac 問題概要 の番号がついたタンクがある。番目のタンクには最初mの高さの水が入っている。以下のクエリを合計回処理せよ。 の各タンクの水の高さをm上昇させる の各タンクの水の高さをm減少させる (…

前回の記事の続き smijake3.hatenablog.comコドフォのSegment Tree Beatsの説明の例題として挙がっているTask 3,4を実装したので、そのあたりの考え方含めて書いておく A simple introduction to "Segment tree beats" - Codeforces

Segment Tree Beats(SGT Beats)の基本的なところの自分の理解をまとめておく。 今回は主に考え方や実装の説明メインで、Historic Informationや計算量解析周りの説明は含まない。(ここらへんも理解できて書けたら書く)

Link-Cut Tree(Link-Cut 木)を実装したのでそのメモみたいなもの

非再帰版の遅延評価セグメント木(Segment Tree with Lazy Propagation)の実装メモ。

Li Chao (Segment) Treeについて理解をまとめた

CodeChefのMay Challenge 2018の問題: Rubber Band (Code: RUBBER) 問題: https://www.codechef.com/MAY18A/problems/RUBBERコンテスト中解けなかった問題。解法メモ。 問題概要 ボード上に個のnailが固定されている。そこに、個の線分で輪っかが構成された1…

TopCoder SRM 733のMedium "BuildingSpanningTreesDiv1"解法メモ

頑張ってPythonで解いた。C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder

2017年最初の記事。Kitamasa法をとりあえず理解できた気がするのでメモ

機会があったので、少し気になってたDeep Q-Network (DQN)について数日で勉強してみた。 既にいろんなところでまとめられてN番煎じだけど、自分なりに整理するために強化学習やDQNについて簡単にまとめておく。