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

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

O(3^N)なbitDP

AtCoder ARC 171 D - Rolling Hash (黄色, 600 点)

コンテスト後に解いた。こっちの方が解きやすかった。 問題へのリンク 問題概要 制約 考えたこと 最初は の指数を気にするのかな......などと考えていたが、考えていくうちに の値など、ただの飾りであることがわかってきた。 まず、問題の条件を言い換える…

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

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

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

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