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

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

区間の連結関係に関する問題

AOJ 2880 エレベータ (RUPC 2018 day1-G)

昔はこういうの苦手だったけど、今ならできる! 問題へのリンク 問題概要 階建ての建物があって、後述するエレベータの建設をなくしては、下への移動は自由にできるが、上への移動は自由にできない。 個のエレベータ建設計画がある。 番目の計画では、 日目…

AtCoder ARC 104 C - Fair Elevator (黄色, 600 点)

コーナーケースがえぐい!! 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…

第6回 ドワンゴからの挑戦状 2020 予選 E - Span Covering (赤色, 1100 点)

すごく面白かった!!!!!!! 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …

yukicoder No.801 エレベーター

累積和による DP 高速化のすごく面白い問題! 問題へのリンク 問題概要 階建てのビルに 個のエレベーターがあり、 番目のエレベーターは区間 [ ] の間を動いており、区間内の任意のフロアから任意のフロアへと移動することができる (同じフロアへの移動もエ…

全国統一プログラミング王決定戦 本選 E - Erasure (700 点)

700 点は絶対落とさないようにしたい!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間があ…