Round 2

A

使えるやつで一番上のから貪欲に使うだけ

B

現在位置とその段で掘られている区間を状態としてDPすればいい
現在位置は掘られている区間の左端か右端のどちらかなので状態はO(RC^2)
次の状態は左右に移動して穴に落ちるか、ある区間を掘ってその左端・右端で落ちるかでO(C^2)
合計O(RC^4)で解ける

C

最初貪欲でよくね？と思って組んだがそんなことはなかったorz
彩色問題のように見えるが、折れ線に上下の順序があるため、昔実プロでやったゴミ拾い問題のように二部マッチングで解ける
頂点をinとoutの二つに分割して折れ線iの上に折れ線jをもってこれるなら辺out(i)->in(j)を引っ張って二部マッチングして全体から引けばよい

D

半径決めると、置く候補は二円に接する場所なのでO(n^2)個あって、そいつらの組全部について可能か調べるのでO(n^5)
二分探索の反復50回くらいと合わせてかなりきついなーと思い、BitsetでOR演算定数倍高速化ーとかやったが十分すぎた
しかも高速化したせいでバグ埋め込んで再提出orz

全問通って4位でRound2通過
しかしid:iwiwiに4秒差で負けたorz