AtCoderで赤になるまでにしたこと - てんぷらのぷらはC++のぷら
赤コーダーになりました！！！！ チュートリアル修了！！！！！ pic.twitter.com/WMPzYqnfrL — てんぷら (@tempura_cpp) September 21, 2019 ひとつの到達点なので。 自己紹介 ・京都大学理学研究科M2(数学系) ・公立高校出身 ・ぎりぎり数オリ勢(春合宿参加1回で数オリ勢名乗るのおこがましい) ・競技プログラミングも含めてプログラミングを始めたのは2018年1月から(当時B4) したこと 問題を解いた Solved By tempura0224 TopCoder: 19 CodeForces: 432 AtCoder: 1076 AOJ: 181 yukicoder: 95 Sum: 1803 https://t.co/JyHa0kaQ4F — てんぷら (@tempura_cpp) September 23, 2019 1800問く
【全方位木DP】明日使える便利な木構造のアルゴリズム - Qiita
この記事について この記事では、一部で全方位木DP、Rerooting等と呼ばれているアルゴリズムの紹介/解説と、その実装についての簡単な説明を行います。 全方位木DPなどと物騒そうな名前がついていますが、発想自体は全く難しくありません。また、実装もそこまで難しいものではないです。 前提知識として、最低限のグラフ理論の知識(特に木構造について)を要求します。(有向木の根/部分木等…) 謝辞 この記事中に挿入されている図は、殆どを @259_Momone さんに提供して頂きました。素晴らしく美しい図を提供して頂き、この記事を分かりやすいものとして頂いたことに感謝いたします。 全方位木DPとは 各点から深さ優先探索を行って解くことができる問題のうち特定の条件(後述)を満たすものについて、全頂点についての答えを同等の計算量で求めることができるアルゴリズムです。 まず、全方位木DPで解くことができ
競技プログラミングにおけるLCA問題まとめ [auxiliary tree] - はまやんはまやんはまやん
LCA Lowest Common Ancestor 根付き木のある2頂点u,vの共通祖先で最も根から遠い頂点を高速に見つけること yukicoder上でのantaさんの解説 アルゴリズムはいくつかある「ダブリング」「HL分解」「RMQ使用」RMQが最速っぽいけど、体感HL分解の方が早いような… LCA＋根からある頂点への情報(深さとかコスト和とか)を使う解法が多い 例) 頂点aから頂点bへの距離はdist(根,a) + dist(根,b) - 2*dist(根,lca(a,b))となる LCAは単体では余り使われないので、これだけ知っててもしょうがなかったりするが、無いと解けない問題はある 根が変わる場合のLCA 問題 AOJ Lowest Common Ancestor ABC014 D.閉路 yukicoder No.898 tri-βutree 解説 yukicoder No.38
![競技プログラミングにおけるLCA問題まとめ [auxiliary tree] - はまやんはまやんはまやん](https://cdn-ak-scissors.b.st-hatena.com/image/square/58f48f9f6495b1e4bfe5bf3fdc1cce218b4a6d9e/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F10328537792368951407%2F10328749687242644924%2F1583048158)
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
