応用情報技術者 2015年 春期 午後 問03

解答の論理構成

1. kiseki
2. isekik
3. sekiki
4. ekikis
5. kikise
6. ikisek
7. 次に「このブロックを行単位で辞書式順にソートし(⑥)」ます。6行を昇順に並べ替えると
   1. ekikis
   2. ikisek
   3. isekik
   4. kikise
   5. kiseki ←入力文字列
   6. sekiki
8. 「ソート後のブロックの各行の文字列から一番右の文字を行の順に取り出して並べた文字列」として(⑦)
   ・ekikis → s
   ・ikisek → k
   ・isekik → k
   ・kikise → e
   ・kiseki → i
   ・sekiki → i
   を連結すると “skkeii” になります。
9. 「ソート後のブロックにおいて入力文字列に一致する行の行番号」を求めると、入力文字列“kiseki”は5行目なので行番号は5です。

誤りやすいポイント

• 巡回シフト方向を逆にしてしまい、行列自体が間違う。
• ソート後の行番号ではなく、シフト生成時の行番号を答えてしまう。
• 同じ文字が続く場合、辞書式順で「添字の順（安定ソート）」になることを忘れ、不安定ソートの結果を用いてしまう。
• 末尾文字列を作る際に行順を崩してしまい、“skkeii” の文字順を取り違える。

FAQ

解答の導き方

1. 最初のforループの始点（ア）について
   図3の先頭で rString ← InputString と初期化されています。また表2の説明に「EncodeArray[n]は巡回シフト後のブロックを格納する。配列の添字は1から始まる」とあります。ループは rString を順に EncodeArray に格納し、毎回 rotation(rString) を行って次の巡回シフトを得るので、巡回シフトをすべて（元の文字列を含めて）格納するには添字を1から始めて n 回繰り返す必要があります。したがってアは 1 です。
2. ループの終点（イ）について
   上と同じ理由でループは入力文字列の長さ分だけ実行し、全ての巡回シフト（合計 $n$ 個）をEncodeArray[1]～EncodeArray[$n$] に格納します。問題文ではnを「入力文字列の長さ」と定義しているので、ループ終点はInputStringの長さ になります。よってイはInputStringの長さ です。
   （根拠となる記述：図3 のループ内で毎回 rString ← rotation(rString) を行うこと、表2 の rotation の説明「文字列Stringを1文字左に巡回シフトした結果を返す」、および「配列の添字は1から始まる」。）
3. 条件式（ウ）について
   図3ではsort1(EncodeArray) の後にソート済みの各行（EncodeArray[k]）の末尾文字をBlockSortStringに追加し、該当行の行番号をLineに格納する処理があることが分かります。問題文の変換処理の説明に「ソート後のブロックにおいて入力文字列に一致する行の行番号を変換結果とする」と明記されているため、ソート後の各行が元の入力文字列と一致するかを判定して一致した行の添字をLineに代入すれば要件を満たします。したがってウはEncodeArray[k]がInputStringと同一 です。
4. 実装上の注意（重要）
   ここまでで空欄は次のように決まります。
   ア：1
   イ：InputStringの長さ
   ウ：EncodeArray[k]がInputStringと同一
   ただし重要な補足として、InputStringに周期性がある（例：「aaaa」「ababab」など）と巡回シフトで同じ文字列が複数行生成され得ます。その場合、ソート後に同一の文字列が複数存在するため、単に文字列比較だけではどの行が「元の入力文字列の行」に対応するかが確定できません。これを正しく扱うためには、sort1が等しい要素間の相対順序を保持する「安定ソート」であることを保証するか、ソート時に元の添字を第二キーとして保持する実装（添字を一緒にソートする、あるいは添字をキーにしてソートする）にする必要があります。問題文でも図4側の実験でsort2に不安定なアルゴリズム（クイックソート）を使うと復元が一致しなかったことが指摘されており、等しい要素の扱い（安定性）が正否を分けます。

誤りやすいポイント

• 配列の添字が1始まりである点を見落とし、0始まりで実装してしまう（オフバイワンによる誤り）。表2に「配列の添字は1から始まる」とあることを確認する。
• 「EncodeArray[k]の末尾の1文字」を取り出す箇所で先頭文字を使ってしまうなど、末尾／先頭の取り違えをする。
• 巡回シフトで生成される行は必ず一意だと誤解すること。周期性のある文字列では重複行が生じるため、重複時の扱い（安定ソートまたは添字の保持）を考慮しないとencode/decodeが噛み合わない。
• sort1（1次元配列のソート）とsort2（2次元配列をキーでソートする）の役割を混同し、どちらに安定性が必要かを誤る。復元処理ではsort2の安定性が特に重要である。

FAQ

解答の論理構成

1. 表1の手順3は、まず行番号で指示された位置から1文字を取り出し、次にその添字をたどる操作を繰り返します。原文は
   「変換結果の行番号 “4” から、ソート後の文字列 “a(4),a(5),a(6),p(2),p(3),y(1)” の4番目の要素 “p(2)” を取り出して並べる。」
   と記述しており、この “4番目の要素” がDecodeArrayの行Lineに相当します。したがって、最初に追加する1文字は
   DecodeArray[1][Line] です。
2. 同じく手順3には
   「“p(2)” の添字が2であることから、2番目の要素 … を取り出して並べる。」
   とあるため、次に参照すべき行番号は行Lineに格納されている添字、すなわちDecodeArray[2][Line] となります。
3. ループをいつ止めるかについて表1は
   「並べた要素の個数が変換結果の文字列の長さと同じになるまで … を繰り返す。」
   と述べています。プログラムでは “個数” をOutputStringの長さで、 “変換結果の文字列の長さ” をBlockSortStringの長さで表現するため、条件は
   OutputStringの長さがBlockSortStringの長さより小さい です。

誤りやすいポイント

• 行番号Lineを “添字” と取り違え、DecodeArray[2][Line] ではなくDecodeArray[2][n] を初期値に入れてしまう。
• ループ終了条件を “以下” と書いてしまい、1文字足りない／多い出力になるoff-by-oneエラー。
• sort2を不安定ソートで実装し、同じ文字の順序が崩れて復元不能になる。設問本文の「(β)ソートアルゴリズム、ソートキーのいずれかを見直す必要がある」はこの典型例。

FAQ

解答の論理構成

1. 復元処理decodeは、まずOutputStringに1文字だけ追加します。
    引用：「OutputStringの末尾に エ に格納されている1文字を追加する」
2. その後、whileループ内の下線部 (α) で1回の繰返しにつき1文字ずつ追加します。
    引用：「OutputString の末尾に DecodeArray[1][n] に格納されている 1 文字を追加する ← (α)」
3. ループの継続条件は カ で示されており、表1の手順3に対応します。
    引用：「並べた要素の個数が変換結果の文字列の長さと同じになるまで…繰り返す。」
4. 問題文で「BlockSortStringの長さがp」と与えられていますから、最終的にOutputStringにはp文字が入るまで繰返します。
5. すでに1文字はループ外で追加済みなので、残りはp-1文字。
6. 従って、下線部 (α) が実行される回数はp-1回となります。

誤りやすいポイント

• ループ外で1文字追加していることを見落とし、p回と答えてしまう。
• 表1の手順3は「要素を取り出して並べる」処理全体を指すと誤解し、(α) の部分的なカウントを間違える。
• カ の条件を「DecodeArrayが空になるまで」などと曲解し、実際の停止タイミングを読み違える。

FAQ

解答の論理構成

• 表1手順2には「“同じ文字の場合は添字の順に並べる。”」と明記されています。
  これはソートの結果が安定（元の並びを保持）していることを要求しています。
• ところが問題文は「Array[ ][1]の要素をキーにしてクイックソート（不安定なソート）を使用した場合には復元処理の結果が入力文字列と一致しなかった。」と述べています。
  不安定ソートでは同じ文字の相対順が崩れ、添字に従うという手順2の条件を満たせず、復元が失敗します。
• よって(β)の見直し案①
  「同じ文字の場合に元の順序を保持するソートを使用する」＝安定ソートに切替える、が正解となります。
• 見直し案②はソートキーの追加です。手順2の条件をキーで強制的に保証するため、一次キーに文字、二次キーに添字を設定すれば、不安定ソートでも結果は正しくなります。
  そこで「2番目のソートキーにArray[2]の要素を加える」と記述します。

誤りやすいポイント

• クイックソートが常に誤りになると決めつける。安定ソートに改良したクイックソート（例えば安定版実装）なら問題ありません。
• 「添字で並べる」処理をループで別途行えばよいと考え、ソート自体の安定性を無視する。
• ソートキー追加案で一次キーを添字、二次キーを文字と誤って設定し、辞書式順を壊してしまう。

FAQ