読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

京都大学プログラミングコンテスト 2015 G ケンドー

解法

Bのワザマエの大きい方から対応するAの人を決めていく。
どう決めるかというと、B[i]に対応するAの要素は、B[i]よりもワザマエが大きい、かつまだ選んでいないAの人のうち、一番右にいる人を選べばよい。具体的には、Aをワザマエ順にソートしておいて、B[i]よりも大きいワザマエをもつAのインデックスを優先度付きキューに入れていく。このキューは、B[i-1]に対応するAを決めるときにも流用できる。
交換回数(自分より右に何人いるか)は、Fenwick木(BIT)のよく使うテクニック(最初、Fenwick木の要素を全て1にしておいて、右に何個あるかを区間和を求めて、使った要素を0にする)を用いればよい。

計算量

O(NlonN)

コード


感想

  • コンテスト中に考えていた解法がわりと外れていなかった(優先度付きキューを使う方法が思いつかなかった)ので、正解者の多かったEに逃げずに最後までやればよかった
  • Fenwick木のよく使うテクニック、わりとよくある気がするのに記事がなかった
    • まあ蟻本のp.162の転倒数を求めるのとほとんどいっしょではある
    • ARC031のC、indeedなう本戦BのEとかの解説を探せばわかるかも