九州大学 2000年 理系 第5問 解説

方針・初手

• アルゴリズムの動作ルール（(c)の条件）を正確に読み取り、順方向にシミュレーションを行う。
• 逆操作を行う場合は、最後の状態から直前の状態をいかにして一意に復元できるかに着目する。(c)の操作により追加される要素は「$j$」または「$S$の先頭に置かれる$t$」のいずれかであるため、現在の順列 $S$ における要素の配置から、どの操作が行われたかを論理的に判定する。

解法1

(1)

$n=10, m=6$ のとき、操作(a)により $j$ は $10-6+1=5$ から始まり、$j=10$ まで1ずつ増加しながら(b)〜(e)を繰り返す。 与えられた $t$ の列に従って、順列 $S$ の変化を追う。開始時、$S$ は空である。

• $j=5$ のとき、$t=4$。$S$ に4はないので、先頭に4を入れる。 $$S = (4)$$

• $j=6$ のとき、$t=3$。$S$ に3はないので、先頭に3を入れる。 $$S = (3, 4)$$

• $j=7$ のとき、$t=6$。$S$ に6はないので、先頭に6を入れる。 $$S = (6, 3, 4)$$

• $j=8$ のとき、$t=3$。$S$ に3はあるので、3の直後に8を入れる。 $$S = (6, 3, 8, 4)$$

• $j=9$ のとき、$t=2$。$S$ に2はないので、先頭に2を入れる。 $$S = (2, 6, 3, 8, 4)$$

• $j=10$ のとき、$t=5$。$S$ に5はないので、先頭に5を入れる。 $$S = (5, 2, 6, 3, 8, 4)$$

よって、得られる順列 $S$ は 526384 である。

(2)

アルゴリズムの(c)の操作により、各ステップで順列 $S$ の要素が1つ増える。増える要素の規則は以下のいずれかである。

(i) $t$ が $S$ に入っている場合：$t$ の直後に $j$ が追加される。（このとき、$j$ は必ず $S$ の2番目以降に配置される） (ii) $t$ が $S$ に入っていない場合：先頭に $t$ が追加される。

したがって、直前の状態を逆算する際の判定条件は次のようになる。

• 現在の $S$ の2番目以降に $j$ が存在する場合：直前のステップで $j$ が追加されたことが確定する。その直前の要素が $t$ であり、1つ前の状態は $S$ から $j$ を除いたものである。
• 現在の $S$ の2番目以降に $j$ が存在しない場合（$j$ がない、または $j$ が先頭にある場合）：直前のステップで先頭に $t$ が追加されたことが確定する。先頭の要素が $t$ であり、1つ前の状態は $S$ から先頭の要素を除いたものである。

最終状態 $S = (8, 2, 7, 5, 9, 3)$ から逆順に $j=10, 9, \dots, 5$ の操作をたどる。

• $j=10$：$S$ に10はないので、先頭の8が追加された要素である。 $$t=8, \quad S = (2, 7, 5, 9, 3)$$

• $j=9$：$S$ の2番目以降に9がある。9の直前の数は5なので、5の直後に9が追加された。 $$t=5, \quad S = (2, 7, 5, 3)$$

• $j=8$：$S$ に8はないので、先頭の2が追加された要素である。 $$t=2, \quad S = (7, 5, 3)$$

• $j=7$：$S$ に7はあるが先頭にあるため「2番目以降」ではない。よって、先頭の7が追加された要素である。 $$t=7, \quad S = (5, 3)$$

• $j=6$：$S$ に6はないので、先頭の5が追加された要素である。 $$t=5, \quad S = (3)$$

• $j=5$：$S$ に5はないので、先頭の3が追加された要素である。 $$t=3, \quad S = \text{空}$$

これらを $j=5$ から順に並べると、$t$ の列は 3, 5, 7, 2, 5, 8 となる。

(3)

(2)で考察した逆算の論理を一般化し、算法として記述する。求める $t$ の列を記録するため、新たな列 $L$ を用意する。

算法 [以下(ア), (イ), (ウ), $\cdots$ の順に行う]

(ア) $j=n$ とし、$t$ の列を記録するための列 $L$ を空とする。 (イ) 順列 $S$ の2番目以降の位置に $j$ が存在するかどうかを判定する。 (ウ) $j$ が $S$ の2番目以降に存在するならば、$S$ における $j$ の直前の数を $t$ とし、$S$ から $j$ を削除する。 そうでないならば、$S$ の先頭の数を $t$ とし、$S$ の先頭の数を削除する。 (エ) 求めた $t$ を列 $L$ の先頭に追加する。 (オ) $j$ を1減らす。 (カ) $j \geqq n-m+1$ ならば、(イ)へもどる。$j < n-m+1$ ならば終了し、$L$ を結果として求める数の列とする。

解説

• 本問はアルゴリズムの順方向のトレースと、その逆操作（逆問題）を構成する情報数学的な論理的思考力を試す問題である。
• (2)での逆算において、「$j$ が $S$ に含まれるからといって、$j$ が追加されたとは限らない」という罠が仕掛けられている（$j=7$ のケース）。(c)のルール上、$j$ が追加される場合は必ず何かの直後に追加されるため、先頭に $j$ がある場合は「$j$ が $t$ として選ばれて先頭に追加された」と判定しなければならない。この点に気付けるかが(3)を矛盾なく記述できるかの最大の分水嶺となる。

答え

(1) 526384

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

(3) (ア) $j=n$ とし、$t$ の列を記録するための列 $L$ を空とする。 (イ) 順列 $S$ の2番目以降の位置に $j$ が存在するかどうかを判定する。 (ウ) $j$ が $S$ の2番目以降に存在するならば、$S$ における $j$ の直前の数を $t$ とし、$S$ から $j$ を削除する。そうでないならば、$S$ の先頭の数を $t$ とし、$S$ の先頭の数を削除する。 (エ) 求めた $t$ を列 $L$ の先頭に追加する。 (オ) $j$ を1減らす。 (カ) $j \geqq n-m+1$ ならば、(イ)へもどる。$j < n-m+1$ ならば終了し、$L$ を結果とする。