こんにちは!Gt 長津です
突然ですが皆さん競技プログラミングというものをご存知ですか?
日本最大のコンテストサイト,AtCoder によれば,
決められた条件のもとで与えられた問題,課題をプログラミングを用いて解決し,その過程や結果を競うものを競技プログラミングといいます.
様々なジャンルの出題がされますが,プログラミングや思考力,数学力,知識を活用します.
だそうです.下のリンクの記事を参考にみんなも始めてみよう!
せっかくなので,問題も作ってみました.ぜひ挑戦してみてください.解説はこのブログの一番最後に載せておきます.
問題文
太郎君は,多さ過剰ビッグバンドジャズフェスティバルに行こうと思っています.このフェスティバルは出演バンドの多さが過剰なことで有名で,今年も非常に多くのバンドが出演します.
フェスティバルは1日中開催されており,N 個のバンドが出演します.i 番目のバンドの名前は Si であり,時刻 li から時刻 ri まで演奏します.あるバンドの演奏を聴くためには,そのバンドの演奏時間全体,すなわち時刻 li から時刻 ri までを会場で過ごす必要があります.また,i 番目のバンドを聴いたときに得られる幸せは hi です.
太郎君は都合により,連続した T 分間しか会場にいることができません.すなわち,ある時刻 s を選び,時刻 s から時刻 s+T までを会場で過ごします.この間に演奏が完全に含まれるバンド,すなわち s ≤ li かつ ri ≤ s+T を満たすバンドをすべて聴くことができます.
太郎君が得られる幸せの合計を最大化してください.ただし,条件を満たす選び方が複数ある場合は,以下の優先順位で選んでください.
- 聴くバンドの数が最も多くなるもの
- それでも複数ある場合は,聴くバンドの中で最初に演奏が始まるバンドの開始時刻 li が最も早いもの
聴くべきバンドの名前を,演奏する順(時刻 li が早い順)に1行ずつ出力してください.
入力
入力は以下の形式で与えられます.
出力
聴くべきバンドの名前を,時刻 li が早い順に1行ずつ出力してください.
制約
- 1 ≤ N ≤ 2×105
- 1 ≤ T ≤ 109
- 0 ≤ li < ri ≤ 109
- ri − li ≤ T
- バンドの演奏時間は被らない(i ≠ j ならば区間 [li, ri) と [lj, rj) は共通部分を持たない)
- 1 ≤ hi ≤ 109
- Si は英小文字からなる長さ 1 以上 10 以下の文字列
- Si はすべて異なる
- 入力はすべて整数
入力例 1
出力例 1
時刻 2 から時刻 12 までを会場で過ごすと,nw, gamma, delta の3つのバンドを聴くことができ,幸せの合計は 20+30+40=90 となります.時刻 5 から時刻 15 までを会場で過ごすと delta, epsilon を聴くことができ,幸せの合計は 40+50=90 で同じく最大ですが,聴くバンドの数は2つです.幸せの合計が等しい場合は聴くバンドの数が多い方を選ぶため,nw, gamma, delta が答えとなります.
入力例 2
出力例 2
時刻 0 から時刻 10 までを会場で過ごすと pp のみを聴くことができ,幸せの合計は 30 です.時刻 18 から時刻 28 までを会場で過ごすと nw, rr, ss を聴くことができ,幸せの合計は 10+10+10=30 で同じです.幸せの合計が等しい場合は聴くバンドの数が多い方を選ぶため,nw, rr, ss が答えとなります.
ところで,多さ過剰ビッグバンドジャズフェスティバルってなんなんでしょうね.
ん?
多さ過剰?
おおさかじょう...
大阪城ビッグバンドフェスティバルの季節がやってきたぞーーー!!!!!!!!!!
我々 nw は 6/21 (日) の16:20 から演奏させていただきます!
チケット購入まだの方!!!!!!ぜひメンバーにお声がけください!!!!1枚1000円!!!!!1000円で10演目聴けますよ!!!!超お得!!!!激レア科学大ロスガラとか国立音大ニュータイドとか聴ける!!!!これはアツい!!!!!!!!
ぜってー来てくれよな!!!!!!!
問題の解説
バンドを開始時刻 li の昇順にソートします.演奏時間は互いに重ならないため,li の順は ri の順とも一致します.
ここで,ある時間帯 [s, s+T] で聴けるバンドの集合は,ソートした列の連続した部分列に対応します.ソート済み列の区間 [i..j] のバンドをすべて聴くためには rj − li ≤ T であれば十分で(s = li とすればよい),それを超えると不可能であると言えます.
したがって,尺取り法ですべての有効な区間を O(N) で列挙でき,各区間の幸せの合計は累積和で O(1) で計算できます.
全体の計算量はソートがボトルネックとなって O(N log N) となります.














