Xmas Contest 2019

今年もやりました。コンテストページ：Xmas Contest 2019 - AtCoder 特設ページ：Xmas Contest 2019 たくさんのご参加ありがとうございました！

2019-09-05

TTPC2019 Fの一般版

まず、なぜF - Road ConstructionにDAG制約があったのかに気付くのかなりむずい。で、一般の有向グラフ版がO(V(V+E) log V)で解けて驚き。結構見たことない感じのアルゴリズムで面白かった。togetter.comところで、TTPCの問題面白かった。 E,J,L,Nが特に好…

2019-06-09

GCJ 2019 R3

BC２完で48位。惜しかったような惜しくなかったような。 final行けなかったのは残念だけど、問題面白くて楽しかったので勝ち（とは）togetter.com

2019-05-07

二部マッチングでTLEに苦しんだ話

競プロ Algorithm

opencupで二部マッチングを使う問題があって、自分のライブラリが遅くてTLEにハマりました。そのときに得た知見をまとめておきます。頂点は合計200,000個、辺は200,000本、TLは3秒で、writerや他の人は400msくらいで通ってたらしい。

2019-03-16

グリッドを白く塗る問題

togetter.com

2019-01-23

タイルを永遠に置き続ける問題

雑談競プロパズル

CF後twitterで話してたのでまとめた。楽しかった。togetter.com3*Nに対するエレガントな解答を募集しています。

2019-01-20

DPの区間クエリ的なやつ

Algorithm 競プロ

雑な記事。競プロテクをtweetしただけだといつか流れてどっか行くので、とりあえずまとめといた。togetter.com

2019-01-16

木と計算量後編〜全方位木DP〜

Algorithm 競プロ

前編はこちら前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。予習全方位木DPについて予習します。全方位木DP、有向辺に関するDPだと思うのが分かりやすい。1. 青い矢印は普通の木DPで下から順に求まる2. 根から出る矢印は全部求まっ…

2019-01-15

木と計算量前編〜O(N^2)とO(NK)の木DP〜

Algorithm 競プロ

この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました（嘘）最近、木上のアルゴリズムの面白い計算量解析が２つ話題になったのでまとめておきます。予備知識まず、https://web.archive.org/web/20150819082918/https:…