7K12 blog

猫でも分かるアルゴリズム解説

ABC150 C - Count Order

f:id:tkr987:20200707150907p:plain

https://atcoder.jp/contests/abc150/submissions/14879069

  • std::next_permutationは辞書順に順列を列挙してくれる 

f:id:tkr987:20200707151347p:plain

「辞書順で」という問題設定になっているが、STLnext_permutationは辞書順に順列を列挙してくれる。現在の順列が何番目かcount変数で管理するだけで良い。k番目の順列がxやyと同じかどうかは O(N)で判定できるので、計算量は O(N! N)になる。