Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

順列の性質をまとめる

競プロで頻出の順列P。大抵は順列であることを利用して解く。

en.wikipedia.org

順列の問題に出会った時に、どういう性質を使ったかを書きとめていく。

ふつうの数列と何が違うか?

  • 重複がない
    • 自分より前の要素がわかれば、自分より後ろの要素が確定する
    • k個目の要素が一つに特定出来る
  • 1から連続している
    • 別に1からじゃなくていいと思うけど、これによりQ[P[i]] = iみたいな索引(転置インデックスと呼ぶの?)を考えることが出来るようになる
    • これから「ある数値とある数値の前後関係」がわかる。特に連続した2つ
    • どの要素がどこにあるかをO(1)で知るための前処理としても頻出