AtCoder Beginner Contest 145 F - Laminate

問題 のいずれとも異なる高さに変更する意味はないので、番目に小さい列の高さとおき、に高さを変更する場合を考える。 左端から塗っていくことを考えると、新たに塗り直さなければならない回数は最も右側の列の高さから求められるので、以下のようなdpを考…

第2回全国統一プログラミング王決定戦予選 C - Swaps

問題 任意の置換は巡回置換の積に分解できる。また、n要素の巡回置換は、n-1個の互換の積に分解できる。したがって、ある置換がn-2個の互換で表せる⇔2つ以上の巡回置換の積に分解できる。 ここで、を昇順にソートするような置換を考える。が2個以上の巡回…