応用情報技術者 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. ループの開始値
   【問題文】では「EncodeArray[n]…配列の添字は1から始まる」と規定されています。
   したがって、最初に格納する行は添字「1」であり、[ア]＝1 となります。
2. ループの終了値
   Block-sorting で作るブロックは入力文字列を1文字ずつ左に巡回シフトした“全通り”を並べます。
   【問題文】「注記　n は入力文字列の長さを表す」
   巡回シフトの回数も行数も“長さ”と同数になるので、ループの上限は「InputStringの長さ」、[イ]＝InputStringの長さ です。
3. 入力文字列と一致する行の特定
   【問題文】「ソート後のブロックにおいて入力文字列に一致する行の行番号を変換結果とする」と明示されています。
   よって if 文では「EncodeArray[k]がInputStringと同一」かを判定し、一致したときに Line に行番号 k を格納します。
   これが [ウ]＝EncodeArray[k]がInputStringと同一 となる理由です。

誤りやすいポイント

• 配列添字の開始を 0 と思い込み、[ア]に 0 を入れてしまう。問題文は「1から始まる」と明記。
• ループの終了条件を InputStringの長さ−1 にして行数が1行不足するミス。
• if 条件を EncodeArray[k] == rString など直前の巡回シフト文字列と比較する誤解。求めたいのは“元の入力文字列”との一致です。

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