Learning Algorithms

アルゴリズムの勉強メモ

QUPC G. Tapu & Tapi 2

G - Tapu & Tapi 2最終的にたぷちゃんとたぴちゃんの両方が存在するような連結成分が存在しなければOKなのでそれ以外の3つの状態をすべて持つことにします。$dp1[u] :=$ $u$ を含む連結成分にたぷちゃんもたぴちゃんも存在しないもので有効な状態にする最小…

codeFlyer 参加記

参加しました。https://beta.atcoder.jp/contests/bitflyer2018-final開始前、wifiが接続できない感じで不安でしたが、近くにnuipさんがいたおかげで安心してコンテストに臨めました。コンテスト中、ほぼすべての時間を使ってFとGを解こうとしました。Fを解…

ICPC 2018 国内予選参加記

今年も神戸大学のチームとして、アルゴリズムのプロkimiyukiさん、マラソンマッチのプロkurenai3110さん、えんぴつ画を描くのが上手な僕KokiYmgch、の3人で出ました。僕はいま東京に住んでいるので朝7時に出発して神戸大学に向かいます。ワクワク!11時半に…

全方位木dp

全方位木dpについてです。基本的にここにまとまっていて、僕自身もこの記事から学びました。本記事では、これよりもわかりやすく簡潔な実装します。名前が大げさですが、普通の木dpを少し拡張するだけです。上のサイトの例題 $1$ にもありますが、次のような…

木の辺の最大値のダブリング

木上のパスが含む辺の中で、その重みの最大値(最小値)を対数時間で求めるライブラリです。よく知られたダブリングというテクニックを使っています。ダブリングについてはここでは書きませんが、parmax[k][u] というのは、頂点 $u$ から根に向かってパスを $2…

二重頂点連結成分分解木

二重頂点連結成分分解木のライブラリです。誰も使わないと思います。これの続きです。任意の無向グラフから二重頂点連結成分と関節点を頂点とする木を構築できます。それをやってくれるライブラリです。 //e2i[edge] -> index of the edge //tree index : [0…

二重頂点連結成分分解

二重頂点連結成分分解の実装です。追記:誤りがあったので大幅に変更しました。名前が似ていますが、二重辺連結成分分解とは異なります。そちらについてはこの記事をご覧ください。任意の無向グラフを、その部分グラフであって「その部分グラフにおける関節…