思考力を試す、ナゾ解き！出題者は、アルゴリズムの書籍や競技プログラミングの解説記事を多数執筆する大槻兼資さんです。今回はdiffコマンドにも使われている技術が題材。ぜひお楽しみください。（第2回にして、やや難しめの問題が届きましたよ…！）
本連載では、実際に社会の中で役に立っている数学を題材として、簡単なクイズを出題していきます。読者の中には、中学校や高校で数学の学習に苦しんだ方もいるかもしれません。「こんなことを学んで何の役に立つのだろうか？」と感じた方も多いかもしれません。しかしながら、数学は私たちの暮らす社会の中で、さまざまに使われています。学生時代に数学が苦手だった方も、ぜひ肩の力を抜いて、挑戦してみてください！ 大槻兼資
問題
次の2つの文字列S,Tを考えます。
Sに次の3通りの操作を繰り返すことで、Tに一致させたいとします。
【削除】S中の文字を1つ選んで削除する
【挿入】Sの好きな箇所に好きな文字を1文字挿入する
操作回数の最小値を求めてください。
例題
たとえば、次の2つの文字列S,Tを考えます。
この場合は、次の表に示す4回の操作で、SをTにすることができます。これが操作回数の最小値です。
アドバンスト
この問題が難なく解けたという方は、2つの文字列の大きさが1000程度になってもコンピュータを活用して解くことのできる方法を考えてみてください。
クイズの応用例
この問題は、2つの文字列の類似度を測りたいという問題です。一般に、2つの文字列の類似度を測る問題は、次のような多種多様な応用があり重要です。
- diffコマンド（2つのファイルの差分を教えてくれるコマンドです）
- バイオインフォマティクス（2つのDNA間の類似度を測る問題は重要です）
- スペルチェッカー（ミスタイプされた文字列に対して、類似度の高い英単語を探索します）
- 指紋認証
- 録音した会話の文字起こし
解答
それでは、正解を発表します。
・
・
・
正解は5回です。次の表に示す5回の操作で、S=“engineer”をT=“continue”に変換することができます。
みなさんは正答できたでしょうか。できた方は、なぜこの方法が最適なのか、その理由まで考えてみましょう。
解説
それでは、解説を始めます。少し難しいかもしれませんが、具体的な例に対して手を動かすなどして、少しでも感覚をつかんでみてください。
突然ですが、今回の「文字列Sから文字列Tへと変形させていく文字列操作の列」は、下の図に示すグラフにおいて、左上のノードから右下のノードへと至る経路に対応させて考えることができます。
このグラフで、
- 下方向への移動（実線）は、文字列Sの文字を削除することを表していて
- 右方向への移動（実線）は、文字列Sに文字を挿入することを表していて、
- 斜め右下方向への移動のうち
- 実線で表した部分は、文字列Sの文字を変更することを表し、
- 点線で表した部分は、文字列Sの文字が文字列Tの文字と一致するので何もする必要がないことを表しています。
たとえば、下の図に示す経路を考えてみましょう。
この経路は、次の操作列を表します。
なお、上のグラフにおいて、図中の実線で示した移動については、長さが1である（移動に1のコストを要する）ものと考えて、点線で示した移動については、長さが0である（移動にコストを要さない）ものと考えてみましょう。
このとき、左上のノードから右下のノードへと至る経路全体を移動するためのコストの総和は、文字列Sから文字列Tへと変形するための操作回数に一致します。実際、上の図の経路においては
- 実線で表した移動：9回
- 点線で表した移動：2回
ですが、この経路に対応する文字列操作の回数は9回となっています。
以上から、下の図に示すグラフで、左上から右下へと最短経路を求めればよいことがわかりました。
このグラフの最短経路は、前回のクイズ「カーナビ」の解法と同じ方法で求めることができます。まず、下の図のように、スタートノードに「0」と数値を書き込んだ上で、スタートノードから1手で行けるノードに「1」と数値を書き込みます。
次に、下の図のように、「1」と書かれたノードから1手で行けるノードに「2」と数値を書き込みます。ただし、すでに数値の書かれているマスには書き込みません。これらのマスはスタートから2手で行けるマスでもあります。
ここで、点線で示した部分はコスト0で移動できることに注意しましょう。上から3行目、左から4列目のノードは、上から2行目、左から3列目のノード（2と書き込まれています）からコスト0で移動できるため、「2」と書き込まれています。
これ以降も同様に、3、4、...... と数値を書き込んでいくと、最終的には下の図のように、ゴールのノードには5と書き込まれます（具体的な最短経路を赤色で示しています）。以上より、最短経路の長さは5であると分かりました。
つまり、文字列S=“engineer”を文字列T=“continue”に変形するための必要な操作回数の最小値は5回です。
おわりに
最後に、このクイズの解法と数学との関連を紹介します。
前回のカーナビと同様に、「すでに数が書き込まれたマスの数を用いて、新しいマスに書き込む数を求める」という方法で最短経路を求めました。このような、すでに分かっている値を用いて、分かっていない値を求めていくという考え方は、数学Bの単元「数列」に登場する漸化式でもお馴染みです。
次回も、数学の考え方を用いて解くことのできるパズルを出題します。ぜひ、楽しみにしてください！
アドバンス問題の解答
以下に示すプログラムは、迷路の大きさが1000×1000になっても、コンピュータを活用して解くことのできるものです。C++で記述しています。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 無限大を表す値
const int INF = 1<<29; // 十分大きい値にする
int main() {
// 2 つの文字列 S, T の入力を受け取る
string S, T;
cin >> S >> T;
int n = S.size(), m = T.size(); // S, T の文字数
// 各ノードへの最短距離を表すテーブル
vector<vector<int>> table(n + 1, vector<int>(m + 1, INF));
// 初期化
table[0][0] = 0;
// 各ノードを更新していく
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
// 下方向への移動を考える
if (i-1 >= 0) table[i][j] = min(table[i][j], table[i-1][j] + 1);
// 右方向への移動を考える
if (j-1 >= 0) table[i][j] = min(table[i][j], table[i][j-1] + 1);
// 斜め方向への移動を考える
if (i-1 >= 0 && j-1 >= 0) {
if (S[i-1] == T[j-1]) {
// 変更の必要がないとき
table[i][j] = min(table[i][j], table[i-1][j-1]);
} else {
// 変更の必要があるとき
table[i][j] = min(table[i][j], table[i-1][j-1] + 1);
}
}
}
}
// 答えを出力する
cout << table[n][m] << endl;
}
筆者・出題者：大槻 兼資さん
株式会社NTTデータ数理システム顧問、モノグサ株式会社コンテンツアーキテクト。数学や情報科学の諸分野の教材開発や啓蒙活動に従事。「けんちょん」の愛称で親しまれている。著書に『問題解決力を鍛える！アルゴリズムとデータ構造』（講談社）がある。数理最適化や機械学習を活用した数理コンサルティング業務の経験も多数。趣味は競技プログラミング、虫食算作り、国内旅行など。
ファクトチェック：増井 敏克さん
増井技術士事務所代表。技術士（情報工学部門）。情報処理技術者試験にも多数合格。ビジネス数学検定1級。「ビジネス」×「数学」×「IT」を組み合わせ、コンピュータを「正しく」「効率よく」使うためのスキルアップ支援や、各種ソフトウェアの開発、データ分析などを行う。著書は『プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問』『プログラマを育てる脳トレパズル 遊んでおぼえるPythonプログラミング＆アルゴリズム』（翔泳社）など多数。
