けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

O(3^N)

AtCoder ABC 321 G - Electric Circuit (橙色, 600 点)

除原理! 学びの多い問題だった。Subset Convolution の方はちょっと頑張ってこの後復習する。 問題へのリンク 問題概要 頂点番号が であるグラフ がある。最初、辺は 1 本もない。 以上 以下の値からなるサイズ の 2 つの数列 と がある。 今、これら 2 つ…

AtCoder ABC 310 D - Peaceful Teams (水色, 400 点)

再帰関数を使った全探索が書けるかどうかが試される! 問題へのリンク 問題概要 人のスポーツ選手を 個のグループに分けたい。 ただし、仲の悪いスポーツ選手の組が 組ある。任意の に対して、選手 と選手 を同じグループに属させてはならない。 この制約を…

AOJ 2345 Network Reliability (JAG 冬コン 2011 F) (700 点)

ABC 213 G の類題に挙がっていたのでやってみた! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。また 以上 以下の整数 が与えられます。 グラフの各辺は % の確率でそれぞれ独立に消失します。グラフ全体が連結である確率を求め…

AtCoder ABC 213 G - Connectivity 2 (橙色, 600 点)

面白かった!! より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…

AtCoder ABC 187 F - Close Group (青色, 600 点)

な bit DP としてよく知られている問題ですね! 問題へのリンク EDPC U - Grouping の類題と言える! atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…

AtCoder ABC 169 F - Knapsack for All Subsets (青色, 600 点)

どこかでめっちゃ似たのを解いたことあると思ったらコレだった! drken1215.hatenablog.com 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 個の整数 の空でない部分集合 は 通りあるが、そのそれぞれについて、 = の部分集合のう…

AOJ 3034 Explosion (RUPC 2018 day2-I)

最小包含円シリーズ!!! 問題へのリンク 問題概要 二次元平面上に 個の点がある。これを 個の円ですべて覆うようにしたいです。 これを実現できるような 個の円の半径の最大値として考えられる最小値を求めよ。 制約 考えたこと まず要素技術として、 通り…

Codeforces Round #584 (Div. 1 + Div. 2) E. Rotate Columns (R2400)

すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…

JOI 予選 2015 F - 財宝 (AOJ 0613, 難易度 8)

スライド最小値の練習 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテム…

AOJ 2136 Webby Subway (JAG 夏合宿 2008 day2-F)

最大 22 頂点のグラフの彩色数を求める問題 問題へのリンク 問題概要 本の折れ線が与えられる。折れ線に対応した 頂点のグラフを考える。対応する折れ線同士が交差するところに辺を張る。 このグラフの彩色数を求めよ。 制約 解法 前半の幾何は虚無。実質的…

yukicoder 733 分身並列コーディング

一見 な bitDP だけど、これはアレだ!!! よくある にできるやつだ!!!!! 問題へのリンク 問題概要 個の数 がある。これを最小個数のグループに分けて、各グループの合計値が 以下となるようにせよ。 制約 解法 とりあえず一見 な bitDP に見える。AGC…

AtCoder ARC 100 E - Or Plus Max (黄色, 700 点)

高速ゼータ変換の練習第二弾! 問題へのリンク 問題概要 長さ の整数列 があります。 を満たすすべての整数 について、以下の問題を解け: を < , を満たす整数とするとき、 の最大値を求めよ。 制約 考えたこと 個の要素を一斉に変換する何かをさせている感…

TopCoder TCO 2018 Round 3B Medium - TestProctoring

楽しい!!!!!!!!!すごく勉強になったん!!!!! 大きく 2 つのやり方があって、高速ゼータ変換を用いた O(3n) から O(n2n) への高速化や、期待値に関する重要な考察をするなど色々やれるん。 問題概要 人がテストを行う。 毎秒ごとに 番目の人がテ…