2004/Contest/愛媛大会

Problem E : Confusing Login Names †

問題概要 †

解法 †

主に二通りあると考えられる。

一つは d > 2 にも適用できる解法。 Dynamic Programming の代表例 : Edit Distance (Longest Common Sequence の応用) を用いて本当に文字列間の距離を求めてしまう方法。

もう一つは d <= 2 であり、かつ全操作が可逆であるからこそできる解法。 d = 1 のときは簡単なので省略。 d = 2 のときは、ある文字列から距離 1 で到達できる文字列を全ての文字列について全列挙する。対応する文字列集合に重複が存在した文字列同士は、距離 2 で到達可能である、と言える。

前者の Edit Distance を用いる方法は swap をどう扱うかをうまく考えないとならない。全体的には後者のほうがコーディングはラクかな? (三廻部; Nov 26, 2004)

別解（動的計画法） †

Edit Distance を適用する方法について一言述べておく．

交換操作は隣接する 2 つの文字についてしか適用できないため

間の文字を削除 → 交換 → 間に文字を挿入

という手順を踏むことになる．ここで間の文字について削除操作と挿入操作の両方を適用する場合は交換操作よりも置換操作 2 回のほうが操作回数が少なくてすむ（あるいは同じになる）ことに注意すれば

• 交換 → 間に文字を挿入
• 間の文字を削除 → 交換

の場合だけを考えればよいことになる．したがって，挿入操作あるいは削除操作をさかのぼれば交換操作の適用の可否を判断できる．［泉，28 Nov 2004］

議論・その他 †

• 単一操作で生成できる文字列を列挙する方法の場合，本来であれば d = 2 のときは最初に距離 1 で到達可能であることを調べる必要があるが，いずれの操作も 2 回の操作に置き換えることができることから，実際には距離 2 で到達可能であることを調べるだけでも構わない．［泉，28 Nov 2004］
  • A を挿入 → B を挿入 + B を A に置換
  • A を削除 → A を B に置換 + B を削除
  • A を B に置換 → A を削除 + B を挿入
  • A と B を交換 → A を B に置換 + B を A に置換
• コードに誤りがあったので修正．［泉，4 Dec 2004］

ファイルを添付する †

izumi_E.cpp

E.cpp

mikurube_E.cpp