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

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

bitを遷移させていくナップサックDP

JOI 予選 2014 D - 部活のスケジュール表 (AOJ 0595, 難易度 6)

J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それ…

AtCoder ARC 058 E - 和風いろはちゃん (橙色, 700 点)

5 + 7 + 5 = 17 なの、よくできてる! 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…

Codeforces CodeCraft-20 (Div. 2) E. Team Building (R2300)

これは楽しい!!! 順番をうまく決めれば、全部の情報を持たなくても、個数のみの情報に落とせる系。 問題へのリンク 問題概要 要素の数列 と、 の二次元数列 が与えられる。 個の の中から 個を選び、 残りの 個の index の中から 個分、 の行ベクトルを選…

キーエンス プログラミング コンテスト 2020 D - Swap and Flip (青色, 700 点)

隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる!!! drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…

AtCoder ABC 142 E - Get Everything (水色, 500 点)

個人的には bitDP は「順列を全探索するもの」というイメージがあるけど、今回はそれとはまた違う bitDP という感じ! 問題へのリンク 問題概要 個の宝箱がある。宝箱を開けるための鍵が 個あって、それぞれの鍵はいくつかの宝箱に対応している。鍵 を用いる…

MUJIN 2018 H - タイル張り (1000 点)

コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だったのん... 問題へのリンク 概要 H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか? (99824…