Submission #66349064

---

Source Code Expand

// (S: string) => number
const solve = (S) => {
    // 一旦無条件でランレングス圧縮 偶数番目が1の数 最初と最後の0は無視 長さが奇数か0になる
    const comp = [];
    if (S[0] === "1") comp[0] = 1; 
    for (let i = 1; i < S.length; i++) {
        if (S[i] === S[i - 1]) {
            comp[comp.length - 1] += 1;
        } else {
            comp[comp.length] = 1;
        }
    }
    if (comp.length % 2 === 0) comp.pop();
    //// console.log("comp", comp);
    // 長さが0か1のときは操作0回ですでに条件を満たしているのでearly return
    if (comp.length <= 1) return 0;
    // 左から「1の区間-0の区間-1の区間」を取ってきて、
    // 「つなげて両方残す」「左を0にして右を残す」の2択ならどっちがここで消す数が少なく済むかを計算
    // 少なく済む方を選択していく 同格なら右を残すを選択
    let flip_count = 0;
    let seg_L = comp[0];
    let seg_C = comp[1];
    let seg_R = comp[2];
    for (let i = 2; i <= comp.length - 1; i += 2) {
        if (seg_C < seg_L) {
            // 0の区間が左1の区間より短いならつなげたほうがいい
            flip_count += seg_C;
            // つなげたのを左区間、1個右を中区間、2個右を右区間とする
            seg_L += seg_C + seg_R;
        } else {
            // そうでなければ右だけ残すほうがいい
            flip_count += seg_L;
            // 今の右区間を左区間、1個右を中区間、2個右を右区間とする
            seg_L = seg_R;
        }
        seg_C = comp[i + 1];
        seg_R = comp[i + 2];
    }
    return flip_count;
};

function Main(inputText) {
    /** @type {String[][]} - スペース区切りと改行区切りをそのまま2次元配列に変えた状態 */
    const input = inputText.trim().split("\n").map(row => row.split(" "));
    /* ==== 本体 ==== */
    const T = +input[0][0];
    const cases = [];
    for (let i = 1; i <= T; i++) {
        cases.push(input[2 * i][0]);
    }
    cases.forEach(case_i => {
        // リバースして両方向から確かめる 右を0にして左を残すのが最善の可能性があるので
        console.log(Math.min(
            solve(case_i),
            solve( Array.from(case_i).reverse().join("") )
        ));
    })
}
/* ==== これを書かないといけないらしい ==== */
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Submission Info

Judge Result