トップ› 九州大学› 2000年› 文系第7問

九州大学 2000年文系第7問解説

方針・初手

アルゴリズムの操作 (a)〜(e) を1ステップずつ丁寧にトレースする。特に操作 (c) において、要素が「先頭に追加される」場合と「$t$ の直後に挿入される」場合の違いに着目する。これにより、結果として得られた順列から逆算して操作履歴を復元することが可能になる。

解法1

(1)

$n=10, m=6$ のとき、操作 (a) より $j$ の初期値は $10 - 6 + 1 = 5$ である。各ループにおける順列 $S$ の変化を追う。最初は $S$ は空である。

1回目のループ ($j=5$) 選ばれた数 $t=4$。$4$ は $S$ に入っていないので、$4$ を先頭に入れる。 $S$ は $4$ となる。

2回目のループ ($j=6$) 選ばれた数 $t=3$。$3$ は $S$ に入っていないので、$3$ を先頭に入れる。 $S$ は $3, 4$ となる。

3回目のループ ($j=7$) 選ばれた数 $t=6$。$6$ は $S$ に入っていないので、$6$ を先頭に入れる。 $S$ は $6, 3, 4$ となる。

4回目のループ ($j=8$) 選ばれた数 $t=3$。$3$ は $S$ に入っているので、$3$ の直後に $j=8$ を入れる。 $S$ は $6, 3, 8, 4$ となる。

5回目のループ ($j=9$) 選ばれた数 $t=2$。$2$ は $S$ に入っていないので、$2$ を先頭に入れる。 $S$ は $2, 6, 3, 8, 4$ となる。

6回目のループ ($j=10$) 選ばれた数 $t=5$。$5$ は $S$ に入っていないので、$5$ を先頭に入れる。 $S$ は $5, 2, 6, 3, 8, 4$ となる。

次の操作で $j=11$ となり、$j > 10$ を満たすので終了する。よって、得られる順列は $526384$ である。

(2)

最終的な順列 $S$ から、逆順に操作をたどる。操作 (c) に着目すると、各ステップで $S$ に追加される要素とその位置について、以下の法則がある。

・$t$ が $S$ に入っている場合、$t$ の直後に $j$ が挿入される。このとき、$j$ は必ず直前に要素 $t$ を持つため、先頭にはならない。・$t$ が $S$ に入っていない場合、$t$ が先頭に追加される。

したがって、あるステップの直後の順列 $S$ を見たとき、・$S$ に $j$ が含まれ、かつ先頭でないならば、前者の操作が行われたとわかる。直前の数は $t$ であり、ステップの前に $j$ は存在しなかった。・そうでない（$S$ に $j$ が含まれない、あるいは $j$ が先頭にある）ならば、後者の操作が行われたとわかる。先頭の数が $t$ であり、ステップの前にその先頭の数（$t$）は存在しなかった。

最終結果 $S$ は $8, 2, 7, 5, 9, 3$ であり、$j=10$ から逆算する。

$j=10$ のとき $10$ は $S$ に含まれない。よって、先頭の $8$ が $t$ として追加された。 $t=8$ であり、追加前の $S$ は $2, 7, 5, 9, 3$ となる。

$j=9$ のとき $9$ は $S$ に含まれ、かつ先頭ではない。よって、$j=9$ が挿入された。 $9$ の直前の数は $5$ であるため、$t=5$。追加前の $S$ は $2, 7, 5, 3$ となる。

$j=8$ のとき $8$ は $S$ に含まれない。よって、先頭の $2$ が $t$ として追加された。 $t=2$ であり、追加前の $S$ は $7, 5, 3$ となる。

$j=7$ のとき $7$ は $S$ に含まれるが、先頭である。よって、挿入されたのではなく、先頭の $7$ が $t$ として追加された。 $t=7$ であり、追加前の $S$ は $5, 3$ となる。

$j=6$ のとき $6$ は $S$ に含まれない。よって、先頭の $5$ が $t$ として追加された。 $t=5$ であり、追加前の $S$ は $3$ となる。

$j=5$ のとき $5$ は $S$ に含まれない。よって、先頭の $3$ が $t$ として追加された。 $t=3$ であり、追加前の $S$ は空となる。

以上より、(b) で選ばれた数 $t$ の列は、順に $3, 5, 7, 2, 5, 8$ である。

(3)

(2) の逆算の考え方を一般化し、算法として記述する。与えられた順列 $S$ に対し、$j$ を $n$ から $n-m+1$ まで 1 ずつ減らしながら逆操作を行い、各ステップで求まった $t$ を記録していく。

算法［以下 (a), (b), (c), $\cdots$ の順に行う］ (a) 空の列 $T$ を用意し、$j=n$ とする。 (b) $j$ が順列 $S$ に入っており、かつ $S$ の先頭ではないならば、$S$ において $j$ の直前にある数を $t$ とし、$S$ から $j$ を取り除く。そうでないならば、$S$ の先頭にある数を $t$ とし、$S$ からその先頭の数を取り除く。 (c) $t$ を列 $T$ の先頭に入れる。 (d) $j$ を1減らす。 (e) $j \geqq n-m+1$ ならば、(b) へもどる。$j < n-m+1$ ならば、終了する。このとき得られた列 $T$ が求める列である。

解説

アルゴリズムの順操作において、$j$ が追加される位置が必ず「ある要素の直後」となり、先頭にならないという制約に気付けるかが鍵である。この性質により、事後の順列から「$t$ が先頭に追加された」のか「$t$ の直後に $j$ が挿入された」のかを一意に判定でき、完全な復元（逆操作）が可能になる。(3) では、求まった $t$ を列 $T$ の先頭に順次追加していくことで、最終的に順方向の $t$ の列を容易に構築できる。

答え

(1) $526384$

(2) $3, 5, 7, 2, 5, 8$

(3) 算法［以下 (a), (b), (c), $\cdots$ の順に行う］ (a) 空の列 $T$ を用意し、$j=n$ とする。 (b) $j$ が順列 $S$ に入っており、かつ $S$ の先頭ではないならば、$S$ において $j$ の直前にある数を $t$ とし、$S$ から $j$ を取り除く。そうでないならば、$S$ の先頭にある数を $t$ とし、$S$ からその先頭の数を取り除く。 (c) $t$ を列 $T$ の先頭に入れる。 (d) $j$ を1減らす。 (e) $j \geqq n-m+1$ ならば、(b) へもどる。$j < n-m+1$ ならば、終了する。このとき得られた列 $T$ が求める列である。