きままにものづくり

日々の気付いたことなんかを書いてます。

SRM641Div1Medium

問題

サイズ2Nの配列が与えられる。サイズ2Nの昇順にソートされている配列から、与えれた配列に変更するための最小な操作数を求めよ。以下の操作を1とする。

  • 先頭のN個と次のN個に分け、前者を集合A、後者を集合Bとする。
  • Aの要素とBの要素を交互に繰り返し、2Nの配列を作成する。

解法

与えられた配列の奇数要素と偶数要素を調べることで、以前の集合Aと集合Bが求まる。その集合を得るための操作回数を調べることで、答えが求まる。Nが奇数の場合は、ソートされている配列のBの要素を全てAの集合に移すのに2回の操作が必要になるが、Nが偶数の場合は、一回の操作で十分である。

計算量

 O(N)
ソート: O(N log N)
ソートをしなくても、解ける。

コード