京都大学プログラミングコンテスト 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とかの解説を探せばわかるかも
