AtCoder精選良問「E - Strings of Impurity」Diff 1257

この記事はAtCoderの精選良問集マガジンの中の記事です。
私が良問だと思った問題を解説付きでまとめています。

https://note.com/kuri_tter/m/m622eeb3d9ca2

問題リンク

E - Strings of Impurity

問題概要

英小文字からなる二つの文字列sとtが与えられます。
次の条件を満たす整数i（1≤i≤10^100 * |s|）が存在するかを判定し、存在する場合はそのようなiの最小値を求める。

条件：

1. sを10^100個連結して得られる文字列をs'とする。

2. tは、文字列s'の先頭i文字（s'1, s'2, ..., s'i）の部分列であること。

部分列とは、文字列から0文字以上を削除して残った文字を相対的な順序を保ったまま連結して得られる文字列のことをいう。例えば、「contest」の部分列には「net」、「c」、「tst」などがある。

考え方

まず問題の意味を把握するために入力例１をみてみる。

contest
son

"contest"という文字を10^100個つなげることを考えて、"son"という部分列が最初に表れるようなindexを探すということになる。

conte[s]tc[o][n]test

わかりやすいように[]でくくってみた。contestを２回つなげると、sonという部分文字列が現れる。ここで最後の[n]のインデックスである10が答えとなる。

まず、簡単に分かることとして、文字列Tの"s","o","n"のうち、どれか一つでも文字列Sに含まれていなかったらできない。
逆に全てが含まれている場合は、Sは10^100と果てしなく続けることができるので、かならずできる。

次につなげていったときに最小で何番目か、ということを考えていく。

考えやすいように以下のように文字ごとの出現インデックスを記録しておく。

contest
=>
c:[1]
o:[2]
n:[3]
t:[4,7]
e:[5]
s:[6]

最後に見つかったインデックスを保持しながら次のインデックスを探索していくイメージ。
最後に見つかったインデックスより後に、次の文字のインデックスがあれば、新たに文字列Sを連結する必要がない。
そのまま答えをインクリメントできる。
ない場合は、文字列Sを連結して答えをインクリメントしてから、探索を開始するイメージ。探索には二分探索を使う。

実装

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";

/**
 * 
 * @param arr ソート済みの配列
 * @param x 検索値
 * @returns 
 * 値 x が最初に現れるインデックスを返す。
 * x が arr 内に存在しない場合は、x を挿入するためのインデックスを返す
 */
export const bisectLeft = (arr: number[], x: number, lo: number = 0, hi: number = arr.length): number => {
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (arr[mid] < x) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

function main() {
    const s = next()
    const t = next()
    const sLen = s.length
    const indexList: Record<string, number[]> = {}
    // 文字ごとのインデックスを記録する
    for (let i = 0; i < sLen; i++) {
        const c = s[i]
        if (indexList[c]) {
            indexList[c].push(i + 1)
        } else {
            indexList[c] = [i + 1]
        }
    }
    let ans = 0
    // 最後のインデックス 初期値は０
    let lst = 0
    // tを繰り返す
    for (const nowChar of t) {
        // 文字が存在しない場合、明らかにできない
        if (!indexList[nowChar]) {
            log(-1)
            exit()
        }
        const arr = indexList[nowChar]
        // 最後のインデックス以上であるような今の文字のインデックスを二分探索
        const j = bisectLeft(arr, lst + 1)
        if (j == arr.length) {
            // みつからなかったためsをまるごと足すイメージ
            const cnt = Math.ceil(ans / sLen)
            ans = cnt * sLen
            // 次は一番最初を採用
            const idx = arr[0]
            // こたえにたす
            ans += idx
            // lstを更新
            lst = idx
        } else {
            // みつかった場合
            const idx = arr[j]
            // 最後のインデックスとの差分を答えに足す
            const diff = idx - lst
            ans += diff
            lst = idx
        }
    }
    log(ans)
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = next();
    return arr;
}
function nextNums(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextNum();
    return arr;
}
function nextBigInts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
    return arr;
}

// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
    const stream = createInterface({
        input: process.stdin,
        output: process.stdout,
    });
    stream.on("line", (line) => {
        inputs += line;
        inputs += "\n";
    });
    stream.on("close", () => {
        inputArray = inputs.split(/\s/);
        main();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
}