プログラミングにおいて写像とか逆写像とか合成写像で混乱しないために

https://atcoder.jp/contests/abc392/tasks/abc392_c

　この問題で混乱している人を見ました。

　問題の要点をまとめると以下のようになります。

 - 写像 $P$ : 人→人の写像
 - 写像 $Q$ : 人→ゼッケンの写像
 - 求めたい写像 $S$ : ゼッケン→人→人→ゼッケンの写像

# 写像とは

　写像とは、ある集合（定義域）の各要素に対して、別の集合（値域）のちょうど1つの要素を対応させるルールのことです。

　狭義に「整数を整数に対応させる写像」に限定すると、例えば

```math
1 \to 3, \quad 2 \to 1, \quad 3 \to 4, \quad 4 \to 2
```

　と定義すれば、これは写像になります。重要な点として、この対応は **一方向** であり、例えば $(1 \to 3\)$ だからといって $\(3 \to 1\)$ とは限りません。

　プログラミング言語の配列は、この「整数を整数に対応させる写像」の具体例と見なすことができます。例えば、`[3, 1, 4, 2]` は、以下の写像に対応します。

$$
f: \{1,2,3,4\} \to \mathbb{Z}, \quad f(1) = 3, f(2) = 1, f(3) = 4, f(4)=2
$$

　問題における $R$ と $Q$ はそれぞれ、ある人を別の人に対応させる写像と、あるゼッケンをある人に対応させる写像であると言えます。

# 逆写像とは

　さて、問題の $Q$ は人$\to$ゼッケンを対応させる写像でした。そうであれば、「ゼッケン$\to$人」なる写像が欲しくなります。$Q$ は人 $X$ をゼッケン $Q_i$ に対応させるような写像なので、以下のように言い換えられます。

- ゼッケンが $Q_i$ になるような人 $X$ を返す写像を、$Q^{-1}$ とする

　これがスッと入ってくる人はそもそも混乱しないので、そうでない人は以下の愚直なコードを見た方が想像しやすいかもしれません。

```python
# 人からゼッケンへの対応（Q）
Q = [3, 1, 4, 2]  # 例: 人0はゼッケン3, 人1はゼッケン1, ...

# 逆写像を求める
Q_inv = [-1] * len(Q)  # 初期値を -1 にしておく

for idx in range(1, len(Q) + 1):  # ゼッケンは 1 から始まる
    for i in range(len(Q)):  # すべての人を確認
        if Q[i] == idx:  # ゼッケンが idx の人を探す
            Q_inv[idx - 1] = i + 1  # 逆写像を作る

print(Q_inv)  # [2, 4, 1, 3]  (ゼッケン1の人:1, ゼッケン2の人:3 ...)
```

　これは愚直なコードであり、実際は以下のように完結に記述できます。

```python
for i in range(len(Q)):
    Q_inv[Q[i]-1] = i+1
```

## 証明

　ある写像 $F$ があらゆる $i$ において、$F(i)=Q^{-1}(i)$ を満たすとする。
　このとき、$i$ に $Q(i)$ を代入してもこの式は成り立つため、
```math
F(Q(i))=Q^{-1}(Q(i)) 
```
　も当然成り立つ。

　右辺の $Q^{-1}(Q(i))$ について、$Q^{-1}$ と $Q$ の合成写像は定義上打ち消し合うため、

```math
F(Q(i))=i
```

　が成り立つ。

## 続き

　求める答え $F$ は、あるゼッケン $i$ に対して、

```math
F(i) = Q(P(Q^{-1}(i)))
```

　なる写像となります。なので、$Q^{-1}$ がわかれば以下の実装で解けます。

```python
n = int(input())
p = list(map(int, input().split(' ')))
q = list(map(int, input().split(' ')))
q_inv = [-1]*n
for i in range(n):
    q_inv[q[i]-1] = i+1
ans = [-1]*n
for i in range(n):
    ans[i] = q[p[q_inv[i]-1]-1]
print(*ans)
```

# 逆写像を持つ条件

　ある写像が逆写像を持つ条件は、その写像が **全単射** であることです。要は、写像元が写像先と一対一対応している必要があります。

　例えば、$2$ 人以上の人が同じゼッケンを着回す場合、そのゼッケンからその着用者を一意に定めることができません（単射ではないパターン）。他にも、ゼッケンを着ない人がいる場合、そのゼッケンから着用者を決めることはできません（全射でないパターン）。

　今回の問題の場合は、制約から全単射であることが保証されているため、安心して逆写像を取ることができます。

# 合成写像におけるテクニック

```math
F(i) = Q(P(Q^{-1}(i)))
```

　これについて、上の証明で用いたテクニックを用いると、以下のことが言えます。

```math
F(Q(i)) = Q(P(Q^{-1}(Q(i)))
```
```math
\Leftrightarrow F(Q(i)) = Q(P(Q^{-1} \circ Q(i)))
```
```math
\Leftrightarrow F(Q(i)) = Q(P(i))
```

　ユーザー解説で述べられていた解法は、論理的には上のような形で導出できます。

　一般に、以下のことが言えます。

```math
F(x) = A(B(x))
```
```math
\Leftrightarrow F(B^{-1}(x)) = A(x)
```

　これは $B$ が合成写像であるときも言えるので、これを利用すると面白い解法が得られます。

```math
F(i) = Q(P(Q^{-1}(i)))
```
　$P \circ Q^{-1}$ をまとめて写像 $G$ とみなす。
```math
F(i) = Q(G(i))
```

```math
\Leftrightarrow F(G^{-1}(i)) = Q(i)
```
```math
\Leftrightarrow F(Q(P^{-1}(i))) = Q(i)
```

　なので、$P^{-1}$ を求めた上で、以下のような解法でもいけます。

```python
n = int(input())
p = list(map(int, input().split(' ')))
q = list(map(int, input().split(' ')))
p_inv = [-1]*n
for i in range(n):
    p_inv[p[i]-1] = i+1
ans = [-1]*n
for i in range(n):
    ans[q[p_inv[i]-1]-1] = q[i]
print(*ans)
```

　更に極端に言えば、以下のような解法も成り立ちます。

```math
F(Q(P^{-1}(Q^{-1}(i)))) = i
```

（コードは省略）