Submission #70453829

---

Source Code Expand

/** @type {(a: unknown, b: unknown) => number} Array#sort()でcompareFnを指定しなかったときのデフォルトの挙動と同じ挙動を示す比較関数 */
const DEFAULT_COMPARE_FN = (a, b) => {
    const [A, B] = [String(a), String(b)];
    return (A < B) ? -1 : (A > B) ? 1 : 0
};
/** @template {any} T */
/** @type {(array: T[], target: T, compareFn?: (a: T, b: T) => number) => boolean} 配列`array`に`target`と等しい値が存在するかどうかを、二分探索を用いて判定する。 */
const binary_search = (array, target, compareFn = DEFAULT_COMPARE_FN) => {
    let low = 0;
    let high = array.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const cmp = compareFn(array[mid], target);

        if (cmp === 0) return true;
        if (cmp < 0) low = mid + 1;
        else high = mid - 1;
    }

    return false;
};
/** @template {any} T */
/** @type {(array: T[], target: T, compareFn?: (a: T, b: T) => number) => number} 配列`array`の中で、`target`以上と判定される最初の要素のインデックスを返す。(`array`内に`target`以上の要素が存在しない場合は`array.length`を返す。) */
const lower_bound = (array, target, compareFn = DEFAULT_COMPARE_FN) => {
    let low = 0;
    let high = array.length;

    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        const cmp = compareFn(array[mid], target);

        if (cmp < 0) low = mid + 1;
        else high = mid;
    }

    return low;
};
/** @template {any} T */
/** @type {(array: T[], target: T, compareFn?: (a: T, b: T) => number) => number} 配列`array`の中で、`target`より大きいと判定される最初の要素のインデックスを返す。(`array`内に`target`より大きい要素が存在しない場合は`array.length`) */
const upper_bound = (array, target, compareFn = DEFAULT_COMPARE_FN) => {
    let low = 0;
    let high = array.length;

    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        const cmp = compareFn(array[mid], target);

        if (cmp <= 0) low = mid + 1;
        else high = mid;
    }

    return low;
};

// ==== ここからほんへ ====
const inputText = await Deno.readTextFile("/dev/stdin");
const input = inputText.trim().split("\n").map(row => row.split(" "));
(() => {
    // 処理
    const [N, M, C] = input[0].map(n => +n);
    const A = input[1].map(n => +n);
    
    // Aを3周分に伸ばしてソートしてランレングス圧縮します
    for (let i = 0; i < N; i++) {
        A.push(A[i] + M);
        A.push(A[i] - M);
    }
    A.sort((a, b) => a - b);
    const A_compressed = [];
    (() => {
        let latest;
        A.forEach((Ai) => {
            if (latest?.pos !== Ai) {
                if (latest != null) {
                    A_compressed.push(latest);
                }
                latest = { "pos": Ai, "humans": 1 };
            } else {
                latest.humans++;
            }
        });
        if (latest != null) {
            A_compressed.push(latest);
        }  
    })();
    
    // A_compressedに「そこまでに何人いるか(そこ含む)の情報(total)を追加します」
    (() => {
        let all_count = 0;
        A_compressed.forEach(Ai => {
            all_count += Ai.humans;
            Ai.total = all_count;
        });
    })();
    // console.log(A_compressed); // 確認用 (posに場所、humansに人数、totalに合計人数)
    
    // このあとにぶたんするのでtotalの比較関数作っておきます
    const TOTAL_COMPARE_FN = (a, b) => a.total - b.total;
    
    // posが1以上である人を先頭として1周するまで、
    // 「その人達が第一村人のとき高橋君が何人に出会うか」と
    // 「その人達が第一村人なiの数」を求めて掛け算すると良いと思います
    // posが1以上である最初の集団のA_compressedにおけるindex
    const headTargetIndex = A_compressed[A_compressed.length / 3].pos === 0
        ? A_compressed.length / 3 + 1
        : A_compressed.length / 3;
    // A_compressedのどこまで見ればいいか(index)
    const tailTargetIndex = headTargetIndex + (A_compressed.length / 3) - 1;
    // A_compressedの当該範囲をループしながら回答を足していきます
    let sum = 0;
    // console.log(headTargetIndex, tailTargetIndex); // 確認用
    for (let i = headTargetIndex; i <= tailTargetIndex; i++) {
        // 今回先頭とする集団
        const targetGroup = A_compressed[i];
        // 1個前の集団
        const latestGroup = A_compressed[i - 1];
        // totalが何**以上**になったら止まるか(CにlatestGroup.totalを足せばOK)
        const stopOnTotalIsOver = C + latestGroup.total;
        // totalがstopOnTotalIsOver以上な最初のA_compressedの要素のindex
        const stopperGroupsIndex = lower_bound(
            A_compressed,
            { "total": stopOnTotalIsOver },
            TOTAL_COMPARE_FN
        );
        // 高橋君を止めたグループに対応するA_compressedの要素
        const stopperGroup = A_compressed[stopperGroupsIndex];
        // stopperGroupまで(stopperGroup含む)のtotal
        const total_onStopperGroup = stopperGroup.total;
        // <!> targetGroupが第一村人のときの出会う人数
        const X_ifFirstIsTargetGroup = total_onStopperGroup - latestGroup.total;
        // 第一村人がtargetGroupであるiの下限 (= latestGroupのpos)
        const i_min = latestGroup.pos;
        // 第一村人がtargetGroupであるiの上限 (= targetGroupのpos - 1)
        const i_max = targetGroup.pos - 1;
        // 第一村人がtargetGroupであるiの数 (i_max - i_min + 1)
        const i_count = i_max - i_min + 1;
        // 足す
        sum += X_ifFirstIsTargetGroup * i_count;
        // console.log(sum, X_ifFirstIsTargetGroup, i_count); // 確認用
    }
    console.log(sum);
})();

Submission Info

Judge Result