\(K=1\) の場合

\(K=1\) の場合、操作はバブルソートと呼ばれるアルゴリズムに登場するものとなります。
バブルソートが正当であることから分かるように、\(K=1\) の場合の答えは Yes となります。より具体的には、まず一番小さい値を左端に、二番目に小さい値を左から \(2\) 番目に、\(\ldots\) という順にすると良いです。

\(K\) が一般の場合

\(K\) 個の数列 \(B_0,\ldots,B_{K-1}\) を次のように定めます。

• \(i=0,\ldots,K-1\) に対し、\(B_i=(a_{i+1},a_{K+i+1},a_{2K+i+1},\ldots)\)

この時、操作は「ある \(B_i\) において隣り合う \(2\) つの項を入れ替える」といえます。
ある数列 \(B_i\) でどのように操作したかは他の数列に影響しないため、それぞれについて独立に昇順に並び替えた上で元の位置に戻す形で操作後の \(A\) を考え、これが昇順かどうかを調べることで本問題を解くことが出来ます。

効率の良いソートアルゴリズムの利用

本解説の冒頭でバブルソートについて触れましたが、実際にこれを用いて並び替えを行うとTLE(実行時間制限超過)となります。これは、バブルソートの時間計算量が \(\mathrm O(N^2)\) であり、本問題の制約・実行時間制限に対して効率が悪すぎるためです。
より効率の良い \(\mathrm O(N\log N)\) のソートアルゴリズムとして マージソート や ヒープソート 等が知られており、それらを使うことで本問題に正答することが出来ます。また、これらのアルゴリズムの実装を自力で行う必要は必ずしもなく、たとえばC++では次のように書くことでソートを \(\mathrm O(N\log N)\) で行えます。

sort(a.begin(),a.end());

実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
    
	int N,K;
	cin>>N>>K;
	
	vector<vector<int>> b(K);
	
	vector<int> a(N);
	for(int i=0;i<N;i++){
		cin>>a[i];
		b[i%K].push_back(a[i]);
	}
	
	for(int i=0;i<K;i++){
		sort(b[i].rbegin(),b[i].rend());
	}
	
	sort(a.begin(),a.end());
	
	vector<int> na;
	for(int i=0;i<N;i++){
		na.push_back(b[i%K].back());
		b[i%K].pop_back();
	}
	
	if(a==na)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
    return 0;
}