競技プログラミング用 知識集積所
T - Permutation
最終更新：
sport_programming
-
view
問題
必要知識
ABCのB以下レベルの内容は省略
考え方
入力例1のところにある5つの順列を見てみる。
末尾が4のものは2つあるが、最後の4を削除すれば、最初3つの全ての並び順になる。
末尾が3のものは2つあるが、最後の3を削除して4を3に書き換えれば、最初3つの全ての並び順になる。
末尾が2のものは1つあるが、最後の2を削除して4を3に、3を2に書き換えれば、最初3つの並び順のうち末尾が1のものになる。
末尾が4のものは2つあるが、最後の4を削除すれば、最初3つの全ての並び順になる。
末尾が3のものは2つあるが、最後の3を削除して4を3に書き換えれば、最初3つの全ての並び順になる。
末尾が2のものは1つあるが、最後の2を削除して4を3に、3を2に書き換えれば、最初3つの並び順のうち末尾が1のものになる。
要するに、最後が'<'である場合、末尾がjであるものは、1つ少ない順列で末尾がj未満であったものと同じ個数ある。
同様に、最後が'>'である場合、末尾がjであるものは、1つ少ない順列で末尾がj以上であったものと同じ個数ある。
よって、それらを累積和で高速処理できるようにしておけば、動的計画法部分は簡単。
同様に、最後が'>'である場合、末尾がjであるものは、1つ少ない順列で末尾がj以上であったものと同じ個数ある。
よって、それらを累積和で高速処理できるようにしておけば、動的計画法部分は簡単。
