第二回全統プロ王 C Swaps
2019/11/10
数列$ A_1, ..., A_n、$ B_1, ..., B_nが与えられる
以下の操作を$ N-2回まで繰り返して、全ての$ iに対して$ A_i \leq B_iとできるか判定してください
$ Aの要素をswapする
自分なりの解説
まず、最終的な目標(配列の状況)を定めます。
単純に考えて、小さいものは小さいものに対応させた方が得なので、
$ Aと$ Bともに昇順をソートして対応させたものを$ N-2回以下のswapで構成できるかどうかを判定する問題
だと言い換えます。
①まず、単純に理想的な形($ Aと$ Bをソートして対応させたもの)にしても$ A_i \leq B_iを満たさない$ iが存在するなら、いかなるswapをしても達成できません。
②理想的な形で達成されうるなら、それを目標にします。(※問題では$ Aのswapとなっていますが、$ Bのswapでも同様なので、以下ではそう思っていただけると幸いです。)
$ Aを昇順で固定しても一般性を失いません。その状態で、$ Bを昇順に並び替えるのに必要なswapの回数を考えます。
元の$ Bの添字とソート後の$ Bの添字の対応関係は、その添字で表現されます。
例えば、図のような対応があったとき、下のように「置換」で表現できます。 https://gyazo.com/884f5d6670ced4a3464ba2cefe5c7469
(線形代数や群論で登場するようで、今回は知っていると得だと思いますが、私は今回の問題を見てから勉強し直しました。基本的なところがわかっていれば十分だと思います)
これは、以下のような二つの互いに素な巡回置換(editorialでは、「サイクル」と表現されています。以下、サイクル)で構成されています https://gyazo.com/d8df1de0498e6adf8bd92142136085bb
$ K次のサイクル($ K要素からなるサイクル)は,高々$ K-1個の互換(以下、swap)の積に分解できます。(参考: 物理のかぎしっぽ) 例えば、サイクルが$ N次の場合、$ N-1回のswapが必要となるということです。
また、サイクルが$ K次と$ N-K次に分かれている場合、高々合計$ (K-1) + (N-K-1) = N-2回のswapでいいということになります。サイクルが複数に分かれていた方がswap回数が少なくて済むということですね。
一般に、サイクルが$ M個に分かれていた場合は、高々$ N-M回のswapでいい(つまりサイクルの個数分swapの回数が少なくなる)ので、サイクルが$ 2個以上に分かれていれば$ N-2回以下のswapで置換を表現できるということになります。
問題は、サイクルが$ 1個の場合です。
例えば、図のような置換の場合、サイクルは$ 1つだけになっています。
https://gyazo.com/e4e1143c18e452eac0397535b74c3521
このままでは$ N-1回のswapが必要ですが、本当にこれ以上減らせないでしょうか?
減らせるとするなら、このサイクルを$ 2つに分離することができる場合でしょう。$ 2つに分離することができれば、$ N-2回のswapで置換を表現できます。
サイクルの分離は、下の行の2数を(今回の問題では目標側の$ Bの添字)を入れ替える操作をすることで実現されます。イメージはこうです。
https://gyazo.com/8da11e75025f135f1deb1267d3eecd52
一つをつなぎかえるとサイクルを分離することができるのがわかると思います。
この、「つなぎかえる操作」を今回の問題に戻って考えてみると、ソート済みの$ Bの要素をswapする操作に対応していることがわかると思います。
つまり、サイクルが$ 1つの場合、
ソート済みの$ Bの要素をswapできるかどうかが、$ N-2回以下のswapで置換を表せるかどうかの鍵になる
ということです。
最もswapしやすいのは隣り合う要素なので、$ B_iと$ B_{i+1}について考えてみましょう。
これらは、図のように、swapできる場合とできない場合があります。
https://gyazo.com/0042a285bfee70e8b30d7b1113be5a16
swapできるための条件を考えると、
$ A_i $ A_{i+1}
$ B_i $ B_{i+1}
という状態から
$ A_i $ A_{i+1}
$ B_{i+1} $ B_i
にしても条件が満たされればよく、
$ A_i \leq B_{i+1}(自明)
$ A_{i+1} \leq B_i(要確認)
なので、後者の条件を確認すればよいということがわかります。
これを満たす$ iが$ 1つでも存在すれば、$ 1つのサイクルで表されていた置換を少なくとも$ 2つのサイクルに分離することができるので、$ N-2回以下のswapで構成することができるようになります。
満たす$ iが$ 1つもなければ、$ N-1回のswapが必要になってしまい、答えは$ Noになります。
実装について一言触れると、サイクルの個数は、添字をまとめていけばよく、$ UnionFind木で表現できます。
code:c++
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i) #define rep1(i,N) for(int i=1;i<int(N);++i) #define all(a) (a).begin(),(a).end() typedef long long ll;
struct UnionFind{
vector<int> Parent;
vector<int> sizes;
UnionFind(int n):Parent(n),sizes(n,1){ rep(i,n)Parenti=i; } //find the root of x
int root(int x){
}
}
//merge x and y
void unite(int x,int y){
x = root(x);
y = root(y);
if(x == y) return;
if(sizesx < sizesy) swap(x, y); }
bool same(int x,int y){ return root(x) == root(y); }
int size(int x){ return sizesroot(x); } };
int N;
vector<int> A,B;
vector<pair<int, int>> A_sorted,B_sorted;
void INPUT(){
cin>>N;
A.resize(N);B.resize(N);
rep(i,N){
A_sorted.push_back({Ai,i}); }
rep(i,N){
B_sorted.push_back({Bi,i}); }
sort(all(A_sorted));
sort(all(B_sorted));
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
INPUT();
//sortしてAi<=Biを満たないならいかなるswapでも達成できない rep(i,N){
if(A_sortedi.first>B_sortedi.first){ cout<<"No"<<endl;
return 0;
}
}
//sortして達成可能な場合
//sortしたときの対応関係から、サイクルの数を数える
UnionFind uni(N);
rep(i,N){
uni.unite(A_sortedi.second,B_sortedi.second); }
//サイクルの個数(つまり、UnionFindのグループの数)
int cnt = 0;
rep(i,N){
if(uni.Parenti == i)cnt++; }
/*
サイクルが1つのとき、N-1個のswapの積で表現でき、
そこからサイクルが1つ増えるたびに、必要なswapの数は1ずつ減るので、
cnt > 1のときはN-2回以内のswapで達成可能
*/
if(cnt > 1){
cout<<"Yes"<<endl;
return 0;
}
/*
サイクルが1つのとき
Bの要素をswapしてもよければ、1つのサイクルを2つに分離できる
一番簡単なswapは隣り合う要素なので、そこを確認する
∧|| ∧||
*/
rep(i,N-1){
if(A_sortedi+1.first <= B_sortedi.first){ cout<<"Yes"<<endl;
return 0;
}
}
cout<<"No"<<endl;
}