CodeIQの「交差点をすばやく数えよう！」に挑戦してみました。
結果は、以下のように解答は間違っていませんでしたが、3秒以内で実行することが出来ませんでした。
交差点の数がバブルソートの要素の交換回数と同じであることに気付いたのですが、これではの計算量なので3秒を切ることはできません。ソートの問題に置き換えることができるのならクイックソート等を工夫すれば3秒切ることができるのではと思ったのですが、そこでギブアップとなってしまいました。
この問題を通して、
- やはり
のアルゴリズムは速いことを実感
- 逆転数
- 逆転数を求めるのにマージソートが使える
- BIT: Binary Indexed Tree (Fenwick Tree)
- idx & -idx で、idxの一番右の1のビット位置を求めることができる
などなど、多くのことを学ぶことができました。
参考
- もちろん結城( id:hyuki )さんの評価フィードバック
- CodeIQ のアルゴリズム問題「交差点をすばやく数えよう！」by @hyuki に解答しました - 名古屋で数学するプログラマ(仮)
