問題 111 History Grading

判りにくい説明といい加減な例。それに引っかかる人が多いのも無理がない。

例をもって説明するね。教師の正解は 3, 1, 2 だとする。事件1、事件2、事件3がある。どういう順番で事件がおきていたのだろうか。

 事件3 → 事件1 → 事件2

と理解したら大間違い!

正しくは、事件1が3番目、事件2が1番目、事件3が2番目で起きていたというふうに理解しないといけない。つまり、順番として、

 事件2 → 事件3 → 事件1

が正しい。

それで、Sample Input 2 の正解 3 1 2 4 9 5 10 6 8 7 と 2番目生徒の解答 4 7 2 3 10 6 9 1 5 8 を時間軸に直す。

  正解 3 1 2 4 9 5 10 6 8 7 → 2 3 1 4 6 8 10 9 5 7
  解答 4 7 2 3 10 6 9 1 5 8 → 8 3 4 1 9 6 2 10 7 5

それでやっと正解数5が得られる。つまり、4通りの最長一致部分列 3 (1|4) 6 10 (7|5) があるから。最初の間違った理解ではどうやっても5が出てこない。

さて、飛び飛びではあるけど、二つの文字列から、最長一致部分列(LCS)を選び出す方法を次のグラフで考えてください。


最長一致文字列の求め方

つまり、両文字列に文字の一致するところを○つけ、○が繋ぐような、右下方向にもっとも長く伸びるパスがその答えとなる。矢印はひとつの解だが、ほかにも長さの同じパスが3本存在する。

Comments are closed.

Post Navigation