virtual
A
やる
B
やる
C
え、そもそもの(問題文の)日本語が難しい
理解するのにとんでもなく時間かかった
うーん、まず全探索を考える
bit全探索を用いると[tex:O(210)]位になると思うのだが間に合うだろうか
TLEのみ心配だったけど普通に高速でした
D
区間スケジューリング問題->貪欲法かDPの匂い
制約の一つ、S-0.5の部分は面倒なので、
と置き換えると、始点と終点のみに着目して計算していけば良さそうであることが容易に理解できる
それを時間でsortしていけばいいとわかる
さて、まず使うデータ構造だが、配列だと厳しいところがありかつsortする必要があるのでpriority_queueを、時間は「始まりか終わりか」「何のチャンネルか」という３つの要素が必要であるからtupleを使用する(tupleにしたのはqueueの型をvectorにするときの挙動がわからなかったため、pairであれば分かるので要素数も定まっているしtupleを用いようと思った)
また、今各チャンネルについて録画をしているか否かを判定するhantei、今使用している録画機の数curを設ける
多分一番の肝となるのは「終点と始点が重なったとき」の処理だろう
だが、これを処理するのは案外簡単で、
同じチャンネルで複数のテレビ番組が同時に放送されることはありません。
という制約を利用することにより始点優先ソート(おそらく昇順ソートなので始点を0、終点を1と保存)にしておいてhanteiを用いすでにそのチャンネルが録画されているときは追加しないとすればよい
かなりいかれたコードが出来上がった(多分自分が今までに書いたコードで一番汚い)が、WAを食らった
しかも1つのテストケース(04.txt)だけで食らっているのでおそらくコーナーケース
なのでひたすらいろんな自作ケースを与え、コーナーを探す
そしたら恐らくこれというものが見つかりました
4 3 1 4 1 2 6 2 4 8 1 6 10 3
t=6の時、録画機は3台使われている必要がありますが、2と出力された
なので現在時刻を管理するnowなどが必要になります
紆余曲折あり、なんとかAC
つらかった...
Submission #22327988 - AtCoder Beginner Contest 080
展望
もっと問題を解くのが早くなるといいね
