グラフ
面白かった！！ 上手に変数変換することで「2 変数劣モジュラ関数の和の最小化」になるタイプの問題だった。 問題へのリンク 問題概要 考えたこと 一目見て、2 変数劣モジュラ関数の最小化 (燃やす埋める) っぽいと感じた。値が 500 以下というのも怪しい。 …
これは面白かった。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。 について、 である 制約 考えたこと グラフの問題として考えることにした。つまり、0-indexed で表現すると 頂点数 、…
本当に色んな解法がある問題っぽい！！ 問題へのリンク 問題概要 頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。 クエリタイプ 1：頂点 間に辺を結ぶ クエリタイプ 2：頂点 の双方に隣接する頂点がある…
全方位木 DP の練習問題！！ が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみ…
とても典型的で教育的な「燃やす埋める」の練習問題！ 問題へのリンク 問題概要 枚のカード があり、カード を使用するには だけコストがかかる。 一方、いくつかのカードを使用した場合、次の 種類のボーナス があり、ボーナス をクリアすると だけスコアを…
コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…
備忘録として。解説よりもおそらく面倒な DP をした。 問題へのリンク 問題概要 考えたこと 基本的に木 DP のノリで考えることにした。 根を 1 つとったとき、異なる部分木間で交換される頂点はただだか 1 個以内である。そこで次の DP をした。 dp[v][k] ← …
北大セットの D 問題。人生で初めて行列木定理を使った！ 問題へのリンク editorials 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。 今、このグラフにおいて連結性を保ったまま 本の辺を削除する。そしてこのとき閉路が 1 個残るので、閉路…
next_combination を使った！ 普通に STL の next_permutation() でもできる。 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き無向グラフが与えられる。 このグラフの全域木をすべて考えたときの、全域木に含まれる辺の重みの総和を で割ったあま…
2 変数劣モジュラ関数の和の最小化を最小カットにするやつ！ 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…
まず、これをグラフの問題として捉えるところに、一つ山がある印象だけど、みんなあっさり超えていてすごい！ 問題へのリンク 問題概要 以下の正整数からなる長さ の数列 、 が与えられる。これらの数列の組が次の条件を満たすかどうかを判定せよ。 0 と 1 …
次数制約つきのグラフを構築するためには、次数の大きいところから Greedy というよく知られた問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 以下の条件を満たすような、頂点数 のグラフが存在するかどうかを判定せよ。 単純…
最大流を流す練習問題 問題へのリンク 問題概要 人の人 がいる。ある人からある人には魔法パワーを渡していくことができる。具体的には、 組について 人 から人 に対して、最大で だけ魔法パワーを渡せる () ということが指定される。また、 人のうち、 人 …
最小カットの練習問題。問題設定がとても面白い！ 問題へのリンク 問題概要 のグリッドがある。いくつかのマスにはヤギがいる。具体的な入力では、ヤギのいるマスは文字 'X' で表される。 6 6 ...... ...... ..X... .X..X. ..X... ...... グリッドの外周は外…
「与えられたグラフを強連結成分分解すると DAG になるので、DAG 上で DP する」というのが想定解だが、フローでも解けると話題になった問題！ 問題へのリンク 問題概要 頂点数 の有向グラフがある。最初、すべての頂点は白色である。以下の操作を 2 回行う…
実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…
少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題！ 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…
またまた登場！！ グラフの連結成分の個数を求める問題！ 問題へのリンク 問題概要 下図のような のグリッドが与えられる。このグリッドにおいて、上下左右と斜めに隣接している '#' は一つの塊とみなす。 このとき、グリッド内に何個の '#' の塊があるかを…
「平均値の最小化」に基づく二分探索 + 最小全域問題 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の重み付き単純無向グラフが与えられる。各辺 は、重みが であり、長さが である。 グラフの辺集合のうち、すべての頂点を連結にするものを考える。そのよ…
グラフ探索の問題として、人生で最初に解きたい問題！！ 問題へのリンク 問題概要 頂点数 、辺数 の単純な無向グラフが与えられる。 このグラフの連結成分の個数を求めよ。 制約 解法 まず、単純グラフや連結成分という概念についてはこちら！ algo-method.c…
除原理！ 学びの多い問題だった。Subset Convolution の方はちょっと頑張ってこの後復習する。 問題へのリンク 問題概要 頂点番号が であるグラフ がある。最初、辺は 1 本もない。 以上 以下の値からなるサイズ の 2 つの数列 と がある。 今、これら 2 つ…
広く捉えれば「各スロットに対して止める秒数を割り当てる」方法を考える割当問題だと言えそう。 問題へのリンク 問題概要 のグリッド が与えられる。各マスには 0 から 9 までの数字が描かれている。 今、次の条件を満たす 0 以上の整数値 を考えたとき、 …
Polynomial Taylor Shift が使えた！ 問題へのリンク 問題概要 頂点数 の木が与えられる。各 に対して、次の問いに答えよ。 頂点から 個の頂点を選ぶ 通りの方法それぞれについて その 個の頂点をすべて含む連結な部分グラフのサイズとして考えられる最小値…
Functional Graph のサイクル列挙！！！ ライブラリ整備したことがあったおかげでライブラリ使えてよかった！ 問題へのリンク 問題概要 (意訳) 要素数 の数列 があって、はじめは全要素が 0 となっている。以下の操作を好きな回数だけ行って、数列を の状態…
プリューファーコードが使える問題！ 今でこそ高度典型となったが、当時は知られていなかった気がする。 問題へのリンク 問題概要 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 …
また一つ、プリューファーコードの練習問題が増えた！ 問題へのリンク 問題概要 正の整数値 が与えられる。 頂点数 の重み付き木であって、以下の条件を満たすものの個数を 1000000007 で割った余りを求めよ。 各辺の重みは 以上 以下の整数値である 2 頂点 …
点素パスのパッキング系の問題、出ないな〜〜と思っていたら出た！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。3 頂点 が指定される。 2 頂点 を端点とする単純パスであって、頂点 を通るものが存在するかどうか判定せよ。 制約 …
二重辺連結成分分解とか low-link とか色々考えたけど、結果的に最後は「ただ DFS 木を作るだけ」になるという、すごく印象的な問題！ 問題へのリンク 問題概要 以上 以下の整数からなるサイズ の 2 つの数列 、 が与えられる。 今、0 と 1 のみからなるサイ…
Library Checker というと難しいイメージがあるけど、この問題のように基本的な問題もある。でも、「最短路の復元」を要求する問題は意外と少ないので、とても貴重な問題！ 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き有向グラフが与えられる。…
強連結成分分解の verify 問題へのリンク 問題概要 単純とは限らない、頂点数 、辺数 の有向グラフが与えられる。 このグラフを強連結成分分解して、トポロジカルソート順に出力せよ。 制約 解法 まず、強連結成分分解自体の意味は次の記事に書いた。 drken1…
