区間の連結関係に関する問題
昔はこういうの苦手だったけど、今ならできる! 問題へのリンク 問題概要 階建ての建物があって、後述するエレベータの建設をなくしては、下への移動は自由にできるが、上への移動は自由にできない。 個のエレベータ建設計画がある。 番目の計画では、 日目…
AtCoder
AtCoder1100点
DP
個数のみわかれば遷移が作れるDP
連結性を管理するDP
挿入DP
探索順序を工夫して解く
ソート
包除原理
数え上げ問題
被覆する方法の数え上げ
区間
ナップサックDP
選択肢が広い方か狭い方から決めていく
調和級数
見積り大事
二項係数
被覆
ARC-like
赤色diff
ARC-E
区間の連結関係に関する問題
すごく面白かった!!!!!!! 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …
累積和による DP 高速化のすごく面白い問題! 問題へのリンク 問題概要 階建てのビルに 個のエレベーターがあり、 番目のエレベーターは区間 [ ] の間を動いており、区間内の任意のフロアから任意のフロアへと移動することができる (同じフロアへの移動もエ…
AtCoder
AtCoder700点
unrated公式コン
数え上げ問題
DP
包除原理
ナップサックDP
二項係数
区間
操作
操作:区間
被覆する方法の数え上げ
ダブルカウントを防ぐ場合分けのテクニック
操作:上書き
補集合を考える
被覆
区間の連結関係に関する問題
700 点は絶対落とさないのん!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間がある。 これ…