\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) PAST15K 解法 コストの最小を求めるが,下界を求めてそれを実現する例を与える. 下界を求める過程は,必要条件を求めるのに近い. Sub problem: コスト無し コストを無視して \(P_{i}\) と \(P_{i+1}\) の swap を考える. \(P\) を昇順にするには,小さい \(P_{i}\) から左に寄せていくと, 少ない回数でソートできる. Sub problem: コスト有り コストがある場合も,コスト無しの場合と似た方法で出来る. \(P_{[0,i)}\) までソートされてい…