Codeforces #331 Div2 C. Wilbur and Points

競技プログラミング

※このエントリは競プロで圧倒的成長 Advent Calendar 2015の3日目のエントリです．

グリニッジ時間に生きていても，3日目に間に合ってない．

問題はこちら

リアルタイムで参加して解けなかった，Codeforces #331の問題．
英語が読めれば解けたんだぞ（たぶん）．

TLにも誤読した人が結構たくさんいたみたいなので，問題の要約も書いておく．

問題の要約

  • 以下の様な値を入力

[code lang=text] n x1 y1 x2 y2 ... xn yn w1 w2 ... wn [/code]

  • 入力された (x, y) 座標を以下の条件を満たすようにソート
    • yi - xi = wi
    • xi <= xj && yi <= yj ならば i <= j
  • 条件を満たすソートが可能なら「YES」とその結果を，不可能なら「NO」を出力

解法

条件を一つずつチェックする．

  • yi - xi = wi
    いくらでもやり方はあると思うけど，自分は以下のようにした．(あまり賢くなさそう)

    1. 入力時にmapを使ってp[y-x]に座標をpairとして全て記憶する．
    2. wiを順番にチェックする. p[wi]のサイズが0なら条件を満たさない．0でなければp[w[i]]の要素を1つ削除する．
  • xi <= xj && yi <= yj ならば i <= j

    • wが同じ値になるx, yについては普通にpairをソートすれば事足りる. よって1つ目の条件チェックの時に以下のような処理を追加する．

      1. 座標をpairとして記録する時，優先度付きキューを使ってpairの最小値が取り出せるようにする．
      2. wiのチェック時にpairの最小値を取り出して仮の答えのi番目とする．削除はpopで消す．

    • 上記の処理で作成された仮の答えはwが同じになる値については条件を満たしている．あとは全体が条件を満たすかをチェックする．
      そのために仮の答えのxi, yiを順番にチェックする．xj, yj (j < i)においてxi <= xj && yi <= yjとなる値があればアウト．
      これはRange Maximum Queryで実現できる．