順列の問題で使えるかもしれない基礎知識

これはCompetitive Programming Advent Calendar Div201315日目の記事です。

今回は順列について少し扱おうと思います。
と言っても、僕はそこまで深く順列の知識があるわけでもないので、
こういったことを知っていると問題を順列に帰着したときに役に立つかなあ、
という基礎知識的な部分にサラッと触れる感じにしたいと思います。

ちなみに、内容が決まらなかった場合に予定していたD問題のモノマネも裏記事として書いたので、とてつもなく暇を持て余している人はどうぞ。

数列としての順列

まず始めに、ここで扱う順列について定義しておきます。
順列とは、n個の要素からなる数列a_1 a_2 ... a_nであり、以下の性質を満たすものです。

  1. 1 ≦ a_i ≦ n, for 1 ≦ i ≦ n
  2. a_i ≠ a_j, if i ≠ j

要は、1~nまでの数がちょうど1つずつ現れる数列です。
高校数学ではnPkのようなものを順列と言ったりしたかもしれませんが、ここではnPnに対応するもののみを順列として扱う、ということになります。
そういう意味では、順列というより置換です。

全探索

長さnの順列はn!通り存在します。これはとても大きな数で、2^nよりも大きいです。
2^20=1048576に対し、20!=2432902008176640000となり、64bit整数型で表すのもギリギリになってきます。
問題を解くとき、順列を総当たりで計算するようなアルゴリズムに帰着した場合、
たいていはそれぞれの順列の中身も見なければならないため、O(n・n!)以上の計算量になることが多いです。
こうなるとn=10を超えるとTLE 1secが怪しくなり始めます。
逆にいうと制約が厳しいため、nが小さすぎる場合は順列全探索などを簡単に予測することができます。
(罠の可能性もなくはないですが)

順列のDP

順列としての特徴、すなわち同じ要素が一度しか出現しないことを利用する場合のDPは、いわゆるbitDPになってO(2^n・f(n))のような計算量で解けることが割と多いです。

例えば、有名なハミルトンパス問題(ここでは、グラフ上の特定の始点sから終点tまで、全ての頂点を辿るような最短パスを求める問題とする。任意の始点・終点で存在判定をしたり、パスの総数を数え上げることもある)も、
「頂点をどの順番で辿って行くか」を考えているので順列の問題に帰着することができます。
この場合、例えば以下のように最短パスを求めることができます。

int ans = INF; //INFは十分大きな値
int edge[N][N]; //edge[i][j]はiからjへの辺の重みを表す
int a[N];
for(int i=0;i<N;i++)a[i] = i;

do{
  int sum = 0;
  if(a[0] != s || a[N-1] != t)continue;
  for(int i=1;i<N;i++)sum += edge[a[i-1]][a[i]];
  ans = min(ans, sum);
}while(next_permutation(a,a+N));

return ans;

この解法だとO(n・n!)です。
しかし、全ての順列を考える必要はなく、sからtへの有効なパスの数はもっと少ない可能性があるので、それだけ考えればよいです。
しかしこのパスの総数も完全グラフの場合に最悪で(n-2)!通り存在する*1ため、結局まだO(n・n!)です。
ここで、ある頂点vに辿り着いたとき、ここから先のパスの選び方に関してはそれまで実際にどのようなパスを辿ってきたかは重要ではなく、どの頂点を通ったかだけが重要であることに気づきます。
パスが違っても、通った頂点集合が同じであれば、これから先選べるパスは変わりません。
よって、同じ頂点集合を通り、ある頂点vに着く中で、最も短いパスのみを覚えて保持しておけば十分です。
これを利用すると、以下のようなbitDPが可能です。

int edge[N][N]; //edge[i][j]はiからjへの辺の重みを表す
int dp[1<<N][N]; //dp[今までに通った頂点集合][今いる頂点]

//INFで初期化
for(int i=0;i<(1<<N);i++){
  for(int j=0;j<N;j++)dp[i][j] = INF;
}
dp[1<<s][s] = 0;

for(int bit=0;bit<(1<<N);bit++){
  for(int v=0;v<N;v++){
    if( (bit>>v) & 1 == 0)continue;
    //今、頂点vにいるとする
    for(int u=0;u<N;u++){
      //次の行き先を頂点uにする。uにすでに訪れていればcontinue
      if( (bit>>u) & 1)continue;
      //今までに訪れた頂点集合がbit∪{u}で、いまuにいるときの最小パスを更新
      dp[bit | (1<<u)][u] = min(dp[bit | (1<<u)][u], dp[bit][v] + edge[v][u]);
    }
  }
}

return dp[(1<<N)-1][t];

このように、今まで使ったかどうかをbitで保持することで、O(n^2・2^n)で解くことができました。
順列であれば同じ要素の出現回数が高々1回なので、このように使う/使わないの2値に落とすことができます。
もちろん、同じ頂点を高々k回まで通ってよい、など同じ要素が複数回現れる場合も、同様にO(n^2・(k+1)^n)で解くことができます。

部分列の順列判定

ICPC Asia Regional Tehran 2010のG問題は、2つの順列について、同じ長さの連続する部分列のうち、一方が他方の並べ替えになっているような部分列の個数を数え上げる問題です。
それぞれの同じ長さの部分列をすべて比較するナイーブな方法だと、長さがn通り、長さkの部分列がn-k+1通り、一致判定にO(n)でO(n^4)かかります。
n=3000なので間に合いません。計算量的にO(n^2)程度が求められます。
1つの順列の連続部分列の個数がO(n^2)なので、Aの連続部分列それぞれに対し、A'に対応する連続部分列が存在するかどうかをO(1)で判定できればよさそうです。

要素xがA'に出現する位置をpos_xとします。すなわち、A'[pos_x] = xです。
このとき、A[i]からA[i+k]までの長さkの連続部分列について、pos_A[i]からpos_A[i+k]までが全てある値jからj+kに収まっていると、A'[j]からA'[j+k]までがA[i]からA[i+k]までの連続部分列の並べ替えになっていることがわかり、これが必要十分条件です。
また、ある値jはpos_A[i]からpos_A[i+k]の最小値であり、j+kは最大値であることもわかります。
よって、A[i]からA[i+k]までの連続部分列に対応するA'の連続部分列が存在するかを判定するには
pos_A[i]からpos_A[i+k]までの最小値と最大値を覚えておけばよく、これはA[i]からA[i+k-1]までの結果からO(1)で更新できるため、1つの区間につきO(1)で判定ができます。
このアルゴリズムを実装したものが以下のコードです。

int n;
int a[3030],b[3030],pos[3030];
int ans = 0;

for(int i=0;i<n;i++)pos[b[i]] = i;
 
for(int i=0;i<n;i++){
  int r = i+1;
  int minv = pos[a[i]], maxv = pos[a[i]];
  while(r<n){
    minv = min(minv,pos[a[r]]);
    maxv = max(maxv,pos[a[r]]);
 
    if(maxv - minv == r-i)ans++;
    r++;
  }
}
return ans;

これはA,Bともに順列になっており、ある要素の場所が1通りに定まることを利用しています。

反転数

順列には反転というものが定義されています。
これはa_i>a_jかつi

全単射としての順列

長さnの順列a_1 a_2 ... a_nは1~nまでの要素がちょうど1つずつ現れます。
これは見方を変えると関数aによってiをa_iに写像していると考えることができ、
このとき関数aは正の整数集合Nについて*2、a:N→Nの全単射関数です*3。
こうなってくるとまさに置換ですがあえて順列と呼び続けます。

順列を全単射として見る場合は二行記法が用いられることがあります。
例えば5 2 1 4 3という順列は、
$\Big( \begin{matrix} 1~2~3~4~5 \\ 5~2~1~4~3 \end{matrix} \Big)$
などと表記します。
まどろっこしいように思えるかもしれませんが、こうすることで1行目から2行目への写像であることがわかりやすくなったり、逆写像を考えるとき2行目から1行目への写像であると見ればよいので楽になったりします。

順列を関数と考えるのは、並べ替えの問題でしばしば有効です。
並べ替えを表す順列を関数のように合成することで、複数回の並べ替えの繰り返しを1つの順列として表現できるからです。

巡回と周期

JOI模擬予選2012 問題6は、M回のシャッフルを1セットとして、昇順に並んだカードがまた昇順に並び直されるまでにかかるセットの回数を求める問題です。

M回のシャッフルはすべて並べ替え、すなわち順列です。
これは実際にシャッフル操作を行って得ることもできますし、シャッフルによって定義される順列を全単射として合成することでも得られます。
(この問題ならたぶん普通にシャッフルをシミュレートする方が実装が楽です)
全単射としての合成と言うと難しく感じるかもしれませんが、
実際コード上での順列AとBの合成Pは、

int P[N],A[N],B[N];
for(int i=0;i<N;i++)P[i] = B[A[i]];

のように書くだけなので、そんなに難しいことではありません。
このコードでは、A[N]は最初i番目のカードがシャッフルAによってA[i]番目に行くことを表していて、
B[ A[i] ]がシャッフルAの後にシャッフルBをするとき、最初i番目のカードがB[ A[i] ]番目に行くことを表しています。
(注意：このコードの場合、長さnの順列は0~n-1までの要素で構成されています)

さて、M回のシャッフル1セットによる並び替えを表す順列Pが得られたので、
後はこの並び替えを何回繰り返せば昇順に戻るのか、を求める必要があります。
すなわち、Pをk個合成することをP^kと表記し、昇順の順列をeとすると、P^k = eとなるkを求める必要があります。
このkは順列の周期と呼ばれることもあります。つまり、この問題は順列の周期を求める問題です。
順列の周期を求めるためには順列のサイクル表記を知っていると理解の一助になります。

順列3 5 1 4 6 7 2の写像の様子をグラフにしたものが下図です。

このように見ると、写像がいくつかの独立なサイクルを構成し、各要素は高々1つのサイクルに含まれていることがわかります。
このサイクル分解を利用した表記がサイクル表記で、上の例をサイクル表記にすると、
(1 3)(2 5 6 7)
となります。これは、1→3→1、2→5→6→7→2というサイクルを表しています。
4→4は冗長なので通常書きませんが、あえて書くなら(4)です。

問題に戻ります。長さkのサイクル(a[i_1] a[i_2] ... a[i_k])に注目すると、a[i_x]がまたa[i_x]に戻ってくるには、k回かかることがわかります。
すなわち、長さkのサイクルに含まれるすべての要素は、一周するのにk回かかることになります。
つまり、すべての要素が元の位置に戻るためには、すべてのサイクルが整数周する必要があり、このような最小の整数が求める順列の周期です。
これは全てのサイクルの長さの最小公倍数に等しく、簡単かつ高速に求めることができます。
2つの正整数A,Bの最小公倍数はO(log(max(A,B))で求めることができ、
この問題では答えが2^63-1に収まることからこれは定数(高々63程度)と考えることができます。

よって、この問題はM回のシャッフル1セットの並び替えを求めるのにO(NM)、サイクルに分解するのにO(N)、周期を求めるのにO(1)の最小公倍数演算をO(N)回行う、となります。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int c[100100],tmp[100100];
int n,m;
int op,k;

ll gcd(ll a, ll b){ return b?gcd(b,a%b):a; }
ll lcm(ll a, ll b){ return a/gcd(a,b)*b; }

void riffle(void){
  for(int i=0;i<n/2;i++)tmp[2*i+1] = c[i];
  for(int i=n/2;i<n;i++)tmp[2*(i-n/2)] = c[i];
  for(int i=0;i<n;i++)c[i] = tmp[i];
}

void put(void){
  for(int i=0;i<k;i++)tmp[n-k+i] = c[i];
  for(int i=k;i<n;i++)tmp[i-k] = c[i];
  for(int i=0;i<n;i++)c[i] = tmp[i];
}

int main(){
  cin >> n >> m;
  for(int i=0;i<n;i++)c[i] = i;
  
  //シャッフルのシミュレーション
  for(int i=0;i<m;i++){
    cin >> op;
    if(op == 1)riffle();
    if(op == 2)reverse(c,c+n);
    if(op == 3){ cin >> k; put(); }
  }

  //サイクル分解
  vector<int> v;
  bool use[100100];
  for(int i=0;i<n;i++)use[i] = false;

  for(int i=0;i<n;i++){
    int now = i, cnt = 0;
    while(!use[now]){
      use[now] = true;
      cnt++; now = c[now];
    }
    if(cnt)v.push_back(cnt);
  }

  //最小公倍数の計算
  ll ans = v[0];
  for(int i=1;i<v.size();i++)ans = lcm(ans,v[i]);
  cout << ans << endl; 
}
その他写像を用いる問題

The First KMCMonthly ContestのH問題やanta's LAST CONTESTのC問題などでも順列を写像とみることによって並べ替え問題を解いています。
が、都合上これらの問題の解説は割愛させていただきます*4。
興味のある方は解説を読んだりしながら考えてみるとよいでしょう。

まとめ

なんかもっとよいことが言えればよかったんですがごちゃごちゃと順列の問題をやるだけになってしまい申し訳ないです。
今回取り上げた問題のポイントは、

  • O(n!)はたいてい遅すぎなので、順列の特徴をうまいこと利用して計算量を落とす必要がある
  • 各要素が1つしか現れないことを利用すると、
    • DPでは、すでに使った/使わないを利用したbitDPと相性がよい
    • 区間判定では、最大値-最小値 = 長さになることを利用するとよい

あたりだと思います。
個人的には後半の並べ替えを全単射として扱ってごにょごにょする感じが好きなので、そういう問題を他にも知っている方はぜひ教えてください。

ここまで読んでくださった方、ありがとうございました。
明日の担当はsnukeさんとsuneさんです。楽しみですね。綴りが似てますね。

*1:始点・終点が固定されているので、2点は順列に含めない

*2:別に非負で定義してもよいです

*3:n

*4:単に自分がまだ解いていないだけ