ferinの競プロ帳

競プロについてのメモ

2018-11-28から1日間の記事一覧

Mail.Ru Cup 2018 Round 2 C. Lucky Days

問題ページ 解法 g=gcd(ta,tb)とする。各区間についてgずらすことが可能である。la, lbを両方0に近づけるあたりに最適な区間がある。なので0に近づけた辺りをある程度探索すれば答えが求まる。 [la, ra] と [lb, rb] の共通部分はmax(0, min(ra,rb)-max(la,l…

Codeforces Round #523 (Div. 2)

問題ページ 考えたこと 区間スケジューリングっぽい DPができる気がしないので貪欲を考える 区間スケジューリングでは最後に仕事をした時刻を1つ持てばいいが今回は複数ある あるTV番組[l,r]があったとき、前に見たTV番組のうち終端がl未満で最大の区間につ…