Codeforces Round #431 (Div. 2) D. Rooter's Song

解法

まず、各ダンサーが待つ時間をスタート位置を変えるという形で処理する。(p[i], 0)からスタートするダンサーであれば(p[i], -t[i])、(0, p[i])からスタートするダンサーであれば(-t[i], p[i])からスタートすると扱うことで全てのダンサーが単位時間あたり1マス進むと処理することが出来る。
次に各ダンサーがどのダンサーと衝突するか考える。全てのダンサーは単位時間あたりにxまたはyが1増加するので最初の時点でx+yが等しいダンサーはどの時点であってもx+yは等しいといえる。したがってx+yの値が等しくないダンサーと衝突することは絶対にありえないといえる。
x+yの値によってダンサーをグループ分けし、それぞれのグループで衝突した結果どうなるか考えることにする。以下の図のように左上からy座標の大きい順に、3 4 5 1 2のダンサーが衝突しなかった場合にたどり着く最終地点が割り当てられる。x軸のダンサーをxについて昇順、y軸のダンサーをyについて降順で貪欲に割り当てていくことで衝突を考慮した最終地点が求められる。
f:id:ferin_tech:20170902100603p:plain