Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

交差点をすばやく数えよう!

CodeIQの「交差点をすばやく数えよう!」に挑戦してみました。
結果は、以下のように解答は間違っていませんでしたが、3秒以内で実行することが出来ませんでした。

交差点の数がバブルソートの要素の交換回数と同じであることに気付いたのですが、これではO(n^2)の計算量なので3秒を切ることはできません。ソートの問題に置き換えることができるのならクイックソート等を工夫すれば3秒切ることができるのではと思ったのですが、そこでギブアップとなってしまいました。
この問題を通して、

  • やはりO(n log n)アルゴリズムは速いことを実感
  • 逆転数
  • 逆転数を求めるのにマージソートが使える
  • BIT: Binary Indexed Tree (Fenwick Tree)
  • idx & -idx で、idxの一番右の1のビット位置を求めることができる

などなど、多くのことを学ぶことができました。