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

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

区間スケジューリング

JOIG 春合宿 2023 day2-1 Smartphone (2D, 難易度 8)

JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…

AtCoder ABC 325 D - Printing Machine (水色, 450 点)

とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…

AtCoder ABC 206 F - Interval Game 2 (黄色, 600 点)

Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。 問題へのリンク 問題概要 個の区間が与えられる。 個目の区間は となっている。 Alice と Bob は次のようなゲームを行う。 まだ残っている区間のうち、「今までに選ばれた…

AtCoder ARC 106 C - Solutions (水色, 500 点)

面白かった 問題へのリンク 問題概要 以下の条件を満たすような 個の区間 ( 番目を とする) を構築したい。 はすべて互いに相異なる整数 これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君…

キーエンス プログラミング コンテスト 2020 B - Robot Arms (緑色, 200 点)

区間スケジューリング問題そのものだった!!! ...とはいえ 200 点というのは衝撃!!! 問題へのリンク 問題概要 ある工場では、 数直線上に 個のロボットが設置されている。 ロボット は座標 に設置されていて、左右に長さ のアームを伸ばしている。 これ…

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

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

AOJ 3060 Rings (RUPC 2019 day2-J)

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

AtCoder ABC 103 D - Islands War (水色, 400 点)

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