テク:幅が小さいことに着目する(2^Wが小さい)
JOI
JOI予選
JOI難易度6
AOJ
AtCoder
全探索:ビット全探索
ある量を固定して考える
二次元グリッド
操作:flip
Greedy:各要素について独立に考えてよい
テク:幅が小さいことに着目する(2^Wが小さい)
典型要素を詰め合わせた教育的問題
幅が小さいので、幅についての 通りの探索が間に合う！ 問題へのリンク 問題概要 のマス目がある。各マスの値は 0 または 1 である。次の操作を好きな順序で好きな回数だけ行うことができる。 ある行を選択して、その行の数値をすべてひっくり返す (0 を 1 …
JOI
JOI予選
JOI難易度6
AOJ
AtCoder
DP
bitDP
ナップサックDP
数え上げ問題
操作列が文字列で与えられる
0と1と2の問題
DP状態:ビット
テク:幅が小さいことに着目する(2^Wが小さい)
勤怠を題材とした問題
スケジューリング
鍵やアイテムを題材とした問題
典型要素を詰め合わせた教育的問題
(定数)×Nのグリッド
J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それぞれの日において責任者が誰なのかが…
AtCoder
AtCoder500点
ABC-E
ある量を固定して考える
ある量を決めるとGreedy
Greedy
全探索:ビット全探索
全探索
二次元グリッド
区間
0と1の問題
水色diff
テク:幅が小さいことに着目する(2^Wが小さい)
指数探索系問題
区間分割の仕方を走査する問題
制約条件:K個以下
制約が縦方向の bit 管理を要求している感満載 問題へのリンク 問題概要 のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が 以下になるようにする。 これを実…
DP
ナップサックDP
行列
行列累乗
数え上げ問題
グラフ・盤面・数列の個数の数え上げ
二次元グリッド
bitDP
AtCoder1000点
unrated公式コン
AtCoder
ドミノ
DP状態:ビット
操作後の結果の数え上げ
操作によって作れるものの集合を考える(判定関数を考える)
テク:幅が小さいことに着目する(2^Wが小さい)
コンテスト終了後に「もう少しで解けそうだったのに...」と言ったのんな。アレは嘘だった...... 問題へのリンク 概要 H × W の盤面を白黒に塗り分ける方法のうち、白い部分を 1 × 2 の長方形のピースで隙間なく埋められるようなものは何通りあるか？ (998244…
