問題

$n$ 個の要素からなる数列 $a$ が与えられる。ただし、 $i$ 個目の要素は ${a}_{i}$ である。

ここで、 $a$ の部分列のうち、 $k$ 個以下の長さのものを逆順にする、という作業が何回でもできるとき、 $a$ を昇順にすることができるかどうかを判定せよ。

ただし「逆順にする」とは、整数 $i, j$ を $1 \leq i \leq j \leq n$ とするとき、 $[ {a}_{1}, {a}_{2}, \cdots , {a}_{i - 1}, {a}_{i}, {a}_{i + 1}, \cdots, {a}_{j}, {a}_{j + 1}, \cdots , {a}_{n} ]$ を $[ {a}_{1}, {a}_{2}, \cdots , {a}_{i - 1}, {a}_{j}, {a}_{j - 1}, \cdots, {a}_{i + 1}, {a}_{i}, \cdots , {a}_{n} ]$ とすることを指す。また、この場合の部分列の長さは $(j - i + 1)$ である。

入力

まず最初の1行目に、テストケースの個数を表す整数 $t$ が与えられる。

その後、 $t$ 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

最初の1行目には、整数 $n, k$ が与えられる。
次の1行には、整数 ${a}_{i}$ が順に $n$ 個与えられる。

条件

$1 \leq t \leq 100$
$1 \leq k \leq n \leq 100$
$1 \leq {a}_{i} \leq {10}^{9}$

出力

$t$ 行にわたり、各テストケースについて昇順にできる場合は Yes を、できない場合は No を出力すること。

解法

逆順にする部分列の長さを $2$ とした場合、数列 $a$ の ${a}_{i}$ と ${a}_{i + 1}$ の順番を入れ替えることになります。この作業を何回でも行うことができるため、部分列の長さを $2$ とした場合では、数列 $a$ の要素を任意の順番にすることができます。

この問題では、与えられた $k$ 個以下の長さの部分列をすべて逆順にすることができるため、 $k \geq 2$ の場合では必ず $a$ を昇順にすることができます。

また $k = 1$ の場合については、数列 $a$ の順番が入れ替わることはありません。そのため、与えられた数列 $a$ が最初から昇順で並んでいるとき以外については、昇順にすることができません。

以上から、この問題の答えについては

のとき
- 与えられた数列 $a$ が昇順のとき: YES
- そうでないとき: NO
$k \geq 2$ のとき: YES

ということになります。

ソースコード

入力された値をもとに、昇順にすることができるかどうかを判定する関数 solve() を以下のように実装しました。

int n, k, a[105];

bool solve() {
  // 値の入力
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  // k >= 2 ならば必ず成立するので true を返す
  if (k >= 2) {
    return true;
  }

  for (int i = 0; i < n - 1; i++) {
    if (a[i] > a[i + 1]) {
      return false; // k = 1 で昇順になっていないならば false を返す
    }
  }

  return true; // k = 1 で昇順であるならば true を返す
}