2020-12-03から1日間の記事一覧
JOI
JOI予選
JOI難易度6
AOJ
AtCoder
DFS
二次元グリッド
迷路
ハニカム
補集合を考える
番兵法
連結成分
連結成分ごとに分解して考える
BFS
【問題集】DFS・BFSのステップアップ
壁マス
ハニカムつらい 問題へのリンク editorial 問題概要 下図で表されるようなハニカム状のグリッドが与えられる (図は問題文より)。 黒色マスは建物があるマスを表している。赤太線は、「外側」から見て見える外壁を表している。 このような のマップが与えられ…
JOI
JOI本選
JOI難易度6
AOJ
AtCoder
DP
前処理
累積和テク:左右両端からの累積和や累積結果を前処理
部分和
ナップサックDP
累積和
累積和テク:累積和や累積結果を前処理しておく
最大スコア
ナップサック
最適化問題
左右からナップサックした結果を前処理する系! (他の解法もあり) 問題へのリンク editorial 問題概要 (意訳) (実際の問題文は時刻に関する問題) 個の品物がある。それぞれ の番号がついている。番号が の品物は 価値が 重さが となっている。これらを 2 つ…
幾何だ!! ジャッジページへのリンク editorial 問題概要 の長方形の紙上に 個の点がある。これらの点は互いに相異なる。 これらの点から 4 つの点 A, B, C, D を選ぶ (選ぶ順番も考慮する)。そして、点 A を中心として点 B を通る円を O1 とし、点 C を中…
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 人が所属する部活動がある。 日間の活動が行われる。それぞれの日において責任者が誰なのかが…