bitDP
ABC 213 G の類題に挙がっていたのでやってみた！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。また 以上 以下の整数 が与えられます。 グラフの各辺は % の確率でそれぞれ独立に消失します。グラフ全体が連結である確率を求め…
面白かった！！ より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
な bit DP としてよく知られている問題ですね！ 問題へのリンク EDPC U - Grouping の類題と言える！ atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…
J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それ…
状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…
TLE が厳しかった... 問題へのリンク editorial 問題概要 頂点数 の単純無向グラフ が与えられる (連結とは限らない)。各頂点 には重み がついている。 頂点 1 を含む の安定集合をすべて考えたときの、安定集合中の頂点の重もの総和の最大値を求めよ。 制約…
5 + 7 + 5 = 17 なの、よくできてる！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…
TSP だ！！ 問題へのリンク 問題概要 3 次元空間内に 個の都市、都市 1 から 都市 N がある。 座標 の都市から の都市に移動する際には のコストがかかる。 都市 1 からスタートし、全ての都市を 1 度以上巡って都市 1 に戻るまでの最小コストを求めよ。 制…
この問題に似てた drken1215.hatenablog.com 問題へのリンク editorial 問題概要 の順列 を最適化したい。以下の手順にしたがって、各要素 のスコアが定まる。この 個のスコアの最大値の最小値を求めよ。 値が のいずれかであるような数列 ( 項) が与えられ…
比較的簡単枠だとは思っていたけど、B よりも解かれたのはびっくり！ 問題へのリンク 問題概要 北海道高校には 個の科目があり、それぞれ 1, 2, 3 の 3 段階で成績がつけられる。 各生徒の成績は長さ の文字列で表される 生徒 が生徒 の「上位互換」であると…
これは楽しい！！！ 順番をうまく決めれば、全部の情報を持たなくても、個数のみの情報に落とせる系。 問題へのリンク 問題概要 要素の数列 と、 の二次元数列 が与えられる。 個の の中から 個を選び、 残りの 個の index の中から 個分、 の行ベクトルを選…
遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…
面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…
こういうのを素早く処理できるようになりたい 問題へのリンク 問題概要 長さ の 種類の文字からなる文字列 が与えられる。いま、 種類の文字の順列 として考えられる 通りの並びのうち最適なものを求めたい。 順列のスコアは、 上のすべての連続する 2 文字…
隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる！！！ drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…
最小包含円シリーズ！！！ 問題へのリンク 問題概要 二次元平面上に 個の点がある。これを 個の円ですべて覆うようにしたいです。 これを実現できるような 個の円の半径の最大値として考えられる最小値を求めよ。 制約 考えたこと まず要素技術として、 通り…
個人的には bitDP は「順列を全探索するもの」というイメージがあるけど、今回はそれとはまた違う bitDP という感じ！ 問題へのリンク 問題概要 個の宝箱がある。宝箱を開けるための鍵が 個あって、それぞれの鍵はいくつかの宝箱に対応している。鍵 を用いる…
すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…
冷静になれば自然な構成ではあるね...企業コンのラス問だと身構えてしまうのがよくない 問題へのリンク 問題概要 頂点からなる重みつき無向単純完全グラフであって、 通り考えられるハミルトンパスに対して始点と終点が同じものを同一視して得られる 通りの…
こういうの素早く解けるようになりたいね。 いわゆる「トポロジカルソート順の数え上げ」という高難易度でたまに見るパターンの問題。 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。ここで、辺 が全域木を形成していることが保証されている。 …
最大 22 頂点のグラフの彩色数を求める問題 問題へのリンク 問題概要 本の折れ線が与えられる。折れ線に対応した 頂点のグラフを考える。対応する折れ線同士が交差するところに辺を張る。 このグラフの彩色数を求めよ。 制約 解法 前半の幾何は虚無。実質的…
一目見て bitDP なのはわかるのだけど、手こずった...ウチ弱すぎるのん... 問題へのリンク 問題概要 匹の猫をステージ に順番に送り込む 猫 がステージ をクリアできる確率は 猫 がステージ をクリアしたら、次のステージ もその猫で挑まなければならない 猫…
一見 な bitDP だけど、これはアレだ！！！ よくある にできるやつだ！！！！！ 問題へのリンク 問題概要 個の数 がある。これを最小個数のグループに分けて、各グループの合計値が 以下となるようにせよ。 制約 解法 とりあえず一見 な bitDP に見える。AGC…
コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だったのん... 問題へのリンク 概要 H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか？ (99824…
高速ゼータ変換の練習第二弾なん！ 問題へのリンク 問題概要 長さ の整数列 があります。 を満たすすべての整数 について、以下の問題を解け: を < , を満たす整数とするとき、 の最大値を求めよ。 制約 考えたこと 個の要素を一斉に変換する何かをさせてい…
楽しい！！！！！！！！！すごく勉強になったん！！！！！ 大きく 2 つのやり方があって、高速ゼータ変換を用いた O(3n) から O(n2n) への高速化や、期待値に関する重要な考察をするなど色々やれるん。 問題概要 人がテストを行う。 毎秒ごとに 番目の人がテ…
難しく考えすぎてしまった。 文字列問題をみてもひるまずに解けるようになりたい。 問題概要 m 文字からなる文字列が n 個与えられる。 {0, 1, 2, …, m-1} の部分集合 bit のうち、 どの 2 つの文字列を選んでも、それらの文字列の bit に対応する部分文字列…
