なんか初めて見たので。 DAG与えられます。それぞれの辺について、その辺を削除したときに、sからtにいけなくなるか答えてください(s, tは固定) DAGを無向グラフとみなして橋を求めるのはダメです。 4頂点4辺で、辺がそれぞれ 1 2 2 3 1 4 2 4 を結ぶような…

チームでICPC練をしていたらサイクルの数を数える問題に遭遇した(Count Cycles: Asia Tsukuba Regional 2017) サイクル基底を知らずに解けたけど(追記: 解けてなかった)サイクル基底を知らなかったのでついでに調べた。 サイクル基底 まず直感的な説明をしま…

拾ったLinkCutTreeの使い方がわからないことがたまにあったので自分で一番使いやすいと思うものを書きました。 けんしんのLazySegmentTreeやぼくのImplictTreapとまったく同じインターフェースで使えます。 たまに便利なモノイドが追加されるのでそれが一気…

はじめに 昨年のAdvent Calendarで書いた、Implicit Treapというとても有能なデータ構造があります。 xuzijian629.hatenablog.com 機能をもりもり盛り付けた平衡二分探索木で、セグ木でできるような操作が、配列の要素を反転したり削除したり挿入したりしな…

とりあえずいくつか面白い論文をみつけた Randomized Incremental Construction of Delaunay and Voronoi Diagrams Randomized Algorithms for Geometric Optimization Problems An Introduction to Randomization in Computational Geometry ひとつ読んだの…

YouTube Moviesでおすすめに出てきたので300円払って見た。 www.youtube.com ストーリーは、初代龍が如く、およびそのリメイクである龍が如く 極に沿った形になっているがだいぶショートカットされている。 高評価58低評価13ですでに心配だったが見終えてみ…

紹介 NumPyの配列操作の仕組みについて紹介します。生のPythonよりもできる操作が多いのでこちらで統一します。 さて、NumPyで a = [1,...,n] b = a[::-1] としたとき、2行目の操作はかかご存知ですか？まあこれはです。他にもNumPyは配列に関する多くの操作…

なぜか京都会場で申し込んだら台風で東京会場が中止になったので大勝利した KUPC2019の東京会場ですが、登録TAに勝利して楽しみにされていたことかと思いますが、残念ながら台風19号の参加により中止とします。オンラインでの参加は可能ですので、自宅からバ…