プロフィール
AtCoder PR

【AtCoder ABC221B Typescript】問題解説「B – typo」

 
AtCoder ABC221B解説
記事内に商品プロモーションを含む場合があります
Contents
  1. 問題の概要
  2. 考え方
  3. TypeScript 実装例
  4. 注意点とよくあるミス
  5. 動作確認用テスト例
  6. まとめ

問題の概要

AtoCoderのページ：https://atcoder.jp/contests/abc221/tasks/abc221_b

  • 文字列 S, T は同じ長さ（2～100）の英小文字列
  • 高々1回、S の隣接する2文字を選んで入れ替える操作（操作を行わない選択も可能）で、S を T と一致させられるか判定する
  • S と T の長さは等しいことが保証される
  • 出力は、一致可能なら “Yes”、不可能なら “No”
  • すでに S===T の場合も “Yes” （操作を行わない選択肢があるため）

考え方

  1. まず S と T が完全に同じなら “Yes”
  2. S と T を1文字ずつ比較し、不一致箇所のインデックスをすべて集める
  3. 不一致箇所の数が 0 → すでに同一 → “Yes”
  4. 不一致箇所の数が 1 → 文字1つだけ違う → 隣接スワップ1回では合わせられない → “No”
  5. 不一致箇所の数が 2 → 2つの位置 i, j (i<j) が隣接 (j == i+1) かどうかをまず確認し、隣接していれば S[i] と S[j] をスワップすることで T にできるか（S[i]===T[j] かつ S[j]===T[i]）をチェック。両方満たせば “Yes”、そうでなければ “No”。隣接でなければ1回の隣接スワップでは到達できないので “No”。
  6. 不一致箇所の数が 3 以上 → 1回の隣接スワップでは3文字以上を同時に直せない → “No”

この流れは O(N) 走査＋不一致箇所が最大2つの場合の比較だけなので、文字列長が100程度までであれば高速かつ明快です。ループ内で「次の文字が等しいから無理」といった局所的判断をする実装よりも、全不一致を集めてから場合分けする方式のほうがミスが少なくなります。

TypeScript 実装例

以下は Node.js 環境で fs.readFileSync("/dev/stdin", "utf8") から入力を受け取り、判定結果を出力するコード例です。

import * as fs from "fs";

function main(input: string): void {
  // 入力を改行で分割（Windows の \r\n も吸収）
  const lines = input.trim().split(/\r?\n/);
  if (lines.length < 2) return;
  const [strS, strT] = lines;
  const n = strS.length;

  // すでに一致していれば Yes
  if (strS === strT) {
    console.log("Yes");
    return;
  }

  // 不一致箇所を集める。3以上になったら途中で抜ける
  const unmatched: number[] = [];
  for (let i = 0; i < n; i++) {
    if (strS[i] !== strT[i]) {
      unmatched.push(i);
      if (unmatched.length > 2) break;
    }
  }

  // 不一致が2つ以外なら No
  if (unmatched.length !== 2) {
    console.log("No");
    return;
  }

  // 2つの不一致。隣接かつ swap 後に一致するか
  const [i, j] = unmatched;
  if (
    j === i + 1 &&
    strS[i] === strT[j] &&
    strS[j] === strT[i]
  ) {
    console.log("Yes");
  } else {
    console.log("No");
  }
}

// エントリポイント
const inputData: string = fs.readFileSync("/dev/stdin", "utf8");
main(inputData);

実装ポイント解説

  • input.trim().split(/\r?\n/) で改行を吸収。余分な空行や Windows 改行にも対応可能。
  • const unmatched: number[] = []; で型注釈を明示し、不一致インデックスを格納。
  • ループ中に unmatched.length > 2 で早期抜け。大きいケースは判定不要なので無駄な比較を避ける。
  • unmatched.length !== 2 の場合はすぐ “No” とし、2つだけの場合にのみ swap 判定。
  • 隣接チェックは j === i + 1。ここを逆に書くと常に false になるので注意。
  • swap 後の一致チェックは strS[i] === strT[j] && strS[j] === strT[i]。これが成り立たない場合は “No”。
  • TypeScript らしく関数戻り型に : void、変数名は n, unmatched, i, j など短く分かりやすいものを使う。

注意点とよくあるミス

  • ループ内で不一致箇所を見つけた都度に局所的判断をすると、本来スワップ可能なケースを見逃しがち。必ず最後まで不一致箇所を収集してから場合分けする。
  • 隣接インデックスの判定条件を逆に書くミス（indexA + 1 === indexB vs indexB === indexA + 1）。配列に push した順番が昇順であることを前提に、必ず先の要素 +1 で隣接をチェックする。
  • 入力が行数不足の場合などに備え、lines.length < 2 の早期 return を入れておくと安全。
  • 制約が小さい（100文字前後）なら過剰最適化は不要。文字列比較や配列操作は十分高速なので、可読性重視の実装で OK。

動作確認用テスト例

以下のような例で手元で確認してみると安心です。Node.js で実行する場合は、標準入力に次のように渡して動作を確認してください。

  • 同一文字列
    • 入力 abc abc 出力: Yes
  • 隣接スワップで合致するケース
    • 入力 ab ba 出力: Yes
    • 入力 abc bac 出力: Yes
    • 入力 bac abc 出力: Yes
    • 入力 xabcdey xabdcey (不一致箇所 3,4 の ‘cd’ ↔ ‘dc’)
      出力: Yes
  • 隣接スワップで合致しないケース
    • 入力 abc acb 1↔3 のスワップが必要になり隣接スワップ1回では不可 → 出力: No
    • 入力 abc abd 不一致1箇所のみ → No
    • 入力 abcd badc 不一致複数かつ隣接2箇所スワップ1回では合わない → No
    • 入力 ab cc スワップしても ‘ba’ ≠ ‘cc’ → No

まとめ

隣接スワップ1回で文字列を合わせる問題は、不一致箇所をリスト化して数が2つの場合だけ隣接チェック＋クロス一致を行う流れでシンプルかつ正確に解けます。N が小さい前提なら可読性重視の実装で十分高速です。TypeScript/JavaScript での実装例もそのまま競プロ用テンプレートに使える形で紹介しました。ぜひこの方式を理解し、類似問題や他の文字列操作問題にも応用してみてください。これでバグを防ぎ、メンテナンスしやすいコードを書く一助になれば幸いです。

RELATED POST