プロフィール
AtCoder PR

【AtCoder ABC103B Typescript】問題解説「String Rotation」

 
AtCoder ABC103B解説
記事内に商品プロモーションを含む場合があります
Contents
  1. 問題の概要
  2. アプローチと実装アイデア
  3. TypeScript 改善版
  4. テスト例
  5. コードを書くときのポイント
  6. まとめ

問題の概要

本家サイト：https://atcoder.jp/contests/abc103/tasks/abc103_b

  • 英小文字からなる同じ長さの文字列 S, T が与えられる。
  • S の文字を何回か回転（最後の文字を先頭に移動する、など）して T と一致させられるか判定する。
  • 制約：2 ≤ |S| ≤ 100, |S| = |T|。存在しない入力は与えられないが、安全策として長さチェックを入れておくと頑健です。
  • 一致すれば Yes、できなければ No を出力。

たとえば S=”kyoto”, T=”tokyo” の場合、S を 2 回回転させると “tokyo” となるため、出力は Yes 。

アプローチと実装アイデア

直接回転を繰り返す方法

文字列長が最大 100 であれば、S を一文字ずつ回転して T と比較する方法で十分間に合います。

  • 最初に S===T ならすぐ Yes。
  • 1 回の回転操作は「最後の文字 + 先頭から末尾直前まで」で得られる新しい文字列。
  • 最大 N 回（正確には N-1 回）繰り返し、いずれかで一致すれば Yes。最後まで一致しなければ No。

TypeScript の例(私の初回回答):
ACでしたが、並び替え前に一致してたらYesで
即Returnとかにすればいいかなと思いました。

//解くのに8分くらい
import * as fs from "fs";

// エントリポイント　inputに入力データ全体が入る
function Main(input: string) {
	const [strS, strT] = input.trim().split('\n');
	const initialLength = strS.length;

	let reorderedStrS = strS;
	for(let i=0; i<initialLength; i++) {
		reorderedStrS = reorderedStrS[initialLength-1]+reorderedStrS.slice(0, initialLength-1);
		if(reorderedStrS === strT) {
			console.log("Yes");
			return;
		}
	}
	console.log("No");
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
const inputData: string = fs.readFileSync("/dev/stdin", "utf8")
Main(inputData);

文字列連結 + 部分文字列検索による方法

あとで他の方法を検討しました。
より短くシンプルに書きたい場合は、S を自身と連結した文字列 A = S + S の中に T が含まれるかどうかを調べる方法があります。この性質は、回転操作されたすべてのパターンが A の部分文字列として現れるというものです。

if ((s + s).includes(t)) {
  console.log("Yes");
} else {
  console.log("No");
}

これも O(N²) ですが、N≤100 の問題では十分高速です。コード量が少なく、意図が読みやすいのでおすすめです。

例えば、
kyotokyotoとすると
上の太字にtokyoがいるので、含まれるかどうか見るだけいいという手法です。

TypeScript 改善版

以下は標準入力から S, T を読み込んで判定するひとまとまりのコードです。競プロ環境で使いやすいように、早期リターンやコメントを最小限に抑えつつ、意図が分かりやすい構造にしています。あと、いろいろリファクタリングしました。

import * as fs from "fs";

function main(input: string): void {
  const lines = input.trim().split(/\r?\n/);
  if (lines.length < 2) return;
  const s = lines[0];
  const t = lines;

  // 同長ではないなら即 No
  if (t.length !== s.length) {
    console.log("No");
    return;
  }
  // 回転ゼロ回で一致するケース
  if (s === t) {
    console.log("Yes");
    return;
  }
  // S+S に T が含まれるかで判定
  if ((s + s).includes(t)) {
    console.log("Yes");
  } else {
    console.log("No");
  }
}

const inputData = fs.readFileSync("/dev/stdin", "utf8");
main(inputData);

テスト例

いくつかの例をブログ本文で示すと読者の理解が深まります。

  • S=”abcde”, T=”cdeab” → Yes（2 回回転）
  • S=”aaa”, T=”aaa” → Yes（回転ゼロ、または任意回転でも同じ）
  • S=”ab”, T=”ba” → Yes（1 回回転）
  • S=”ab”, T=”ab” → Yes（回転ゼロ）
  • S=”abc”, T=”acb” → No（どの回転でも一致しない）
  • S=”xyz”, T=”xyzxyz”.slice(0,3) など、長さ不一致テスト: No

実際に手で例を挙げることで、「なぜ includes で一致判定できるのか」「ゼロ回転チェックを忘れるとどうなるか」を体感できます。

コードを書くときのポイント

  • まず問題文をよく読み、回転操作の定義と出力フォーマット（Yes/No 大文字）を確認する。
  • 制約を把握し、O(N²) の実装が許容されるかを検証。N≤100 なら安心。
  • 関数名や変数名は短くても意図がわかるように。TypeScript/JavaScript の場合、main, s, t, n といった命名で問題ありません。
  • 早期リターンを活用し、ネストを浅く保つ。特に「長さ違い」「初期一致」の処理は先に扱う。
  • 文字列操作（連結・部分検索）の性質を理解しておくと、パフォーマンスや可読性のトレードオフ判断がしやすい。
  • 競プロ以外の環境やユニットテストを意識するなら、入力チェックやエラーハンドリングを追加しても良い。

まとめ

  • 回転一致判定は「文字列連結 + 部分文字列検索」というアイデアでシンプルに実装可能。競プロでは覚えておくと便利。
  • 手動回転ループで比較する方法もあるので、両方を理解すると応用範囲が広がる。
  • 初期一致チェックや長さチェックを先に行い、早期リターンでコードをすっきり保つ。
  • TypeScript で書くときは、split(/\r?\n/) など入力処理も頑健にし、動作検証用のテスト例を記事に載せると読者に優しい記事になります。

ぜひ実際にコードを動かしながら動作を確認し、競技プログラミングの練習として活用してください。回転文字列判定のテクニックは、他の文字列・循環バッファ系の問題にも応用できるので、知識としてしっかり身につけておくと役立ちます。

RELATED POST