アルゴリズム忘備録

競技プログラミングとかデータ分析とか

CS Academy Round 42 - Sorting Steps

csacademy.com

 

バブルソートを行う。一回のステップを擬似コード(原文参照、インデックスの上から下まで一回づつやるイメージ)の通り行うとき、何回のステップでソートできるか?

 

いわゆる単純なバブルソートのSwap回数ということであれば、転倒数が答えであるが、この場合はステップの考え方がちょっと違う。擬似コードをシミュレートしてみると、あるべき場所よりも右にある要素は1個づつIndexがデクリメントされていき、あるべき場所よりも左にある要素は一気に幾つかインクリメントされる。その為、デクリメントされる回数が最も多い要素を見つけたら、そのデクリメント回数がそのままステップ数になる。

 

見つけ方としては、元の要素とインデックスを持ったa[N][2]配列を用意し、もとの要素でソートする。その後、「元のインデックス - 現在のインデックス」の最大値が答えである。支配項はソートであり、O(N logN)。