置換の問題で添え字をバグらせない

色々雑です

縦線 $N$ 本から成るあみだくじの上部に $0,1,\dots,N-1$ と番号を割り振って、それらを辿って下部に番号を書き込んだとします。このときの下部の左から $i$ 番目の番号を $q_i$ とします。

このあみだくじが表す置換は $\begin{pmatrix} 0 & 1 & \cdots & N-1 \\ q_0 & q_1 & \cdots & q_{N-1} \\ \end{pmatrix}$ ではありません。
$q_i$ が表しているのは $i$ 番目に来る数であって、 $i$ の行き先ではないからです。（これややこしくないですか？？？）

つまり、このあみだくじが表す置換を $\begin{pmatrix} 0 & 1 & \cdots & N-1 \\ p_0 & p_1 & \cdots & p_{N-1} \\ \end{pmatrix}$ とすると、

$p_i$ は「 $i$ が左から何番目に行くか」
$q_i$ は「左から $i$ 番目に来る数は何か」

を表しています。

これを踏まえると、 $i = 0,1,\dots,N-1$ に対して $p_{q_i} = q_{p_i} = i$ です。

ところで、これは逆元の定義そのものです。

（意味を考えれば明らかではありますが）

これを意識することで見通しが良くなる場合があります。

例えばあるあみだくじがあり、それが表す置換が $\sigma = \begin{pmatrix} 0 & 1 & \cdots & N-1 \\ p_0 & p_1 & \cdots & p_{N-1} \\ \end{pmatrix}$ であるとします。
このあみだくじ最下部の、左から $k$ 番目と $k+1$ 番目の間に横線を引いたあみだくじの置換 $\sigma ' = ( k\ \ k+1 ) \sigma$ を考えます。

先程述べたように逆元を取ると位置を表す置換に変換されるので、逆元に変換→swap→逆元に変換とします。

$\tau$ を「置換を表す配列の左から $k$ 番目と $k+1$ 番目を swap する」ことに対応する互換とすると、

$\sigma ' = \left( \tau \sigma ^{-1} \right) ^{-1} = \sigma \tau$

です。

なので結局、あみだくじに線を引く（左から互換 $( k\ \ k+1 )$ を掛ける）操作は、右から互換 $\tau$ を掛けることと等価であるとわかりました。

ABC013D - 阿弥陀

atcoder.jp

あみだくじが表す置換が求まれば後はダブリングするだけです。

通常であれば置換を表す配列 $p_i$ だけでなく $i$ が $p$ のどこにあるのかも保持しなければなりませんが、先程の事柄を踏まえることで不要となります。

上から $i$ 番目の横線が表す互換を $\sigma _i$ とします。

あみだくじの表す置換は $\sigma_M \sigma_{M-1} \cdots \sigma_1$ ですが、これは $p = (1,2,\dots,N)$ に対し $i = M,M-1,\dots,1$ の順に $p_{A_i+1},p_{A_i}$ を swap するだけで求まります。

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

vector<int> inv(const vector<int> &p) {
  vector<int> q(p.size());
  for (int i = 0; i < p.size(); i++) q[p[i]] = i;
  return q;
}
vector<int> compose(const vector<int> &q, const vector<int> &p) {
  vector<int> r(p.size());
  for (int i = 0; i < p.size(); i++) r[i] = q[p[i]];
  return r;
}

int main() {
  int n, m, d;
  cin >> n >> m >> d;
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  vector<int> a(m);
  for (int i = 0; i < m; i++) cin >> a[i], a[i]--;
  for (int i = m - 1; i >= 0; i--) swap(p[a[i] + 1], p[a[i]]);

  // ダブリング
  vector<int> ans(n);
  iota(ans.begin(), ans.end(), 0);
  for (int k = 0; k < 30; k++) {
    if ((1 << k) & d) ans = compose(p, ans);
    p = compose(p, p);
  }
  for (int i = 0; i < n; i++) cout << ans[i] + 1 << "\n";
}

Submission #29633662 - AtCoder Beginner Contest 013

yukicoder No.326 あみだますたー

yukicoder.me

はじめに $A$ を対称群の逆元 $A'$ に変換しておくと、あみだくじの下部の番号の列を $A'$ にできるか？という問題になり、扱いやすくなります。

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

vector<int> inv(const vector<int> &p) {
  vector<int> q(p.size());
  for (int i = 0; i < p.size(); i++) q[p[i]] = i;
  return q;
}

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> b(n);
  iota(b.begin(), b.end(), 0);
  for (int i = 0; i < k; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    swap(b[x], b[y]);
  }
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i], a[i]--;
  a = inv(a);

  vector<pair<int, int>> ans;
  for (int i = 0; i < n; i++) {
    if (b[i] == a[i]) continue;
    int j;
    for (j = i + 1; j < n; j++) {
      if (a[i] == b[j]) break;
    }
    for (int k = j - 1; k >= i; k--) {
      ans.push_back({k + 1, k + 2});
      swap(b[k], b[k + 1]);
    }
  }
  cout << ans.size() << "\n";
  for (auto p : ans) cout << p.first << " " << p.second << "\n";
}

#741660 (C++17) No.326 あみだますたー - yukicoder