彩色問題
共通テスト数学 IA にも似た問題が出ていた! 問題へのリンク 問題概要 頂点数が のサイクルグラフが与えられる。このグラフの各頂点を色 のいずれかの色で塗る。 どの隣接する頂点対も異なる色で塗られるようにする方法の個数を 998244353 で割った余りを求…
コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…
面白かった 問題へのリンク 問題概要 のグリッドがある。各マスには数値が書かれている。 個の数値を集めると、 が 個ずつある。 今、各行について、その 個の数値を自由に並び替えていく。 その結果として、すべての列が の順列であるようにすることが可能…
これ茶色はさすがにびっくりした! 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…
な bit DP としてよく知られている問題ですね! 問題へのリンク EDPC U - Grouping の類題と言える! atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…
本質的には彩色数を求めるだけだけど、幾何パートがちょっと面倒... 問題へのリンク 問題概要 二次元平面上に 個の多角形領域 (すべて単純) がある。各領域はそれぞれある国に属している。異なる多角形領域が同一の国に属していることもある。今、国ごとに「…
軽めの構築問題!! 今回は「最大次数」というのが割と明らかだけど、しっかり構築法踏まえて証明する練習をすると、高難易度問題にも繋がりそう! 問題へのリンク 問題概要 頂点の木が与えられる。 本の辺に対して、なるべく少ない種類の色を用いて色を塗っ…
木の走査って 根の方から情報を配っていく 子ノードたちの情報を引っ張ってくる (いわゆる木 DP) という二つの方向性があって、状況に応じてうまいこと使い分けるとよいイメージがある。 問題へのリンク 問題概要 頂点の木があたえられる。木の各頂点を 色に…
最大 22 頂点のグラフの彩色数を求める問題 問題へのリンク 問題概要 本の折れ線が与えられる。折れ線に対応した 頂点のグラフを考える。対応する折れ線同士が交差するところに辺を張る。 このグラフの彩色数を求めよ。 制約 解法 前半の幾何は虚無。実質的…