atcoder.jp 解法 k=0の時は元の数列のまま、転倒数を求めればよい。 愚直に求めようとするとO(N2)になるが、BITを使うとO(NlogN)で求めることができる。 具体的には、下の記事がわかりやすい。 scrapbox.io あとはk=1~N-1の時を考えればよいが、k=iからk=i+1…

atcoder.jp 解法 テレポートが使えなければ、BFSするだけで解ける。 テレポートを無制限に使用できるとすると大量の辺が追加されることになって、時間内に探索を完了するのが難しくなる。 そこで、同じ文字のテレポートは１回しか使用できないという制限を加…

atcoder.jp 解法 全探索しようとするとO(2N)になり、制約が N ≦ 40 なのでこれでは間に合わない。 そこで、半分全列挙というテクニック使ってO(2N/2)で解くことを考える。 N個の問題を2つのグループに分けて、それぞれのグループごとに問題の選び方を全探索…