グラフ
コンテストページ: AtCoder Beginner Contest 294 - AtCoder コンテスト中AC: A〜E, G G - Distance Queries on a Tree G - Distance Queries on a Tree 値の一点更新が可能な、木上のパスクエリを処理するデータ構造があれば、そのまま適用して解けます。 …
コンテストページ: https://atcoder.jp/contests/abc287 コンテスト中AC: A〜E C - Path Graph? D - Match or Not E - Karuta C - Path Graph? パスグラフのとき、両端の次数は1で、それ以外は2です。また、連結成分の数はただ1つになる必要があります。 以…
コンテストページ: UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder コンテスト中AC: A〜E D - Money in Hand 公式解説とは異なる方法でとする方法を書いておきます。 Sliding Window Agrregationを使います。 DP遷移の一例を…
コンテストページ:https://atcoder.jp/contests/abc267 コンテスト中AC: A〜D コンテスト中にもう少しのところでACできなかったEについてコンテスト後に解けたので書きます。 E - Erasing Verticles 2 とり得る値の最小値を求める問題では、二分探索できない…
コンテスト後に自力ACしましたが、記事を書いていて計算量の見積もりが誤っていたので、公式解説を読みました。 頂点集合を以下の通りとします。 は独立集合であるという条件から、4-cycleをもつ条件は以下に限定されます。 に属するある頂点と、に属するあ…
