グラフ
ちょっと実装が重たい。 問題へのリンク 問題概要 グリッドが与えられる。最初、どのマスにもなんらかの色（整数値）がついている。 マス から辺で接しているマスへの移動を繰り返し、マス と色が異なるマスに入ることなく移動できるマスの集まりを、マス の…
Euler Tour して、遅延評価セグ木（区間加算 + 区間 min）に乗せて......という解法を考えていたところに、あまりにもシンプルな想定解法を目にして、感動した！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる。 に対して、次の問に答えよ。 個…
実はクエリごとに毎回愚直に Dijkstra 法を回しても間に合う！ 問題へのリンク 問題概要 最初、辺数 0 本、頂点数 個のグラフが与えられる。頂点番号は である。このグラフに対して 回のクエリが投げられる。 クエリタイプ 0：2 頂点 が指定されるので、頂点…
これ結構難しい気がする！ グラフの問題の一種。 問題へのリンク 問題概要 人 がいる。高橋君（ 人のいずれとも異なる）は、自分の秘密を、この中の人 に知られてしまった。 一般に、人 は新たに秘密を知ったときには、人 にも伝えてしまう。 高橋君の秘密は…
「グラフ」の基礎になるような、配列上のシミュレーションの問題。 問題へのリンク 問題概要 整数 が与えられる。 このとき、ボタンを押すと、画面の数値 () が に変わる。 最初の数値が 0 であるとき、ボタンを 3 回押すと、どんな数値に変わるか？ 考えた…
木の直径の問題！ 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は、頂点 と頂点 を結んでおり、長さは である。 いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めよ。 制約 考えたこと もし仮…
資源配分問題などとも呼ばれる、貪欲法が使える問題！ 問題へのリンク 過去によく似た類題を出題したことがある。 drken1215.hatenablog.com 問題概要 正の整数からなる長さ の数列 がある。頂点 をもつ木をすべて考えたときの、 の最小値を求めよ ( は頂点 …
いろんな解法あり。 問題へのリンク 問題概要 頂点数 の無向木が与えられる。各頂点 には色 が塗られている。 このグラフにおいて、 であるような頂点組 () についての、2 点 間の距離の総和を求めよ。 制約 考えたこと マージテクで考えた。例によって頂点 …
ChatGPT が問題文コピペのみで解けたと話題になった！ 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。 先手と後手が交互にゲームする。交互にまだ残っているカードのうち、表の値が等しいか、裏の値が等しいような 2 枚のカー…
面白かった！！ 上手に変数変換することで「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 つ…
