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

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

区間スケジューリング

AtCoder ABC 131 D - Megalomania (400 点)

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題!!! 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべて…

Codeforces #547 Div. 3 F - Same Sum Blocks (Hard)

区間スケジューリングと聞いて 問題へのリンク 問題概要 要素からなる数列 が与えられる。以下の条件を満たす最大個数の区間を求めよ (どれか 1 つ復元せよ)。 どの 2 つの区間も交差しない どの区間についても含まれる値の総和が等しい 制約 考えたこと 区…

AOJ 3060 Rings (RUPC 2019 day2-J)

有理数さん。。。 誤差がとんでもなく厳しいらしく、有理数ライブラリを使うということをついに覚えた!!! あと、問題の解法自体は「区間串刺し」といういわゆる「区間スケジューリング問題」の亜種。 問題へのリンク 問題概要 とある水族館に住むイルカ君…

AtCoder ABC 103 D - Islands War (400 点)

問題へのリンク 実は、こないだの RUPC 2018 で出てたん (最後の部分のみほぼ同じ) AOJ 2873 - 検閲により置換 見た目は区間スケジューリング問題とは違うけど、実は区間スケジューリング問題なのん (こういうの双対問題と言ったりするん)。双対性の知識がま…