AtCoder精選良問「D - Face Produces Unhappiness」Diff 1074

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

AtCoder 精選良問集 Diff 茶後半～水前半｜Qlitre｜note

問題リンク

D - Face Produces Unhappiness

問題概要

東西にN人の人が並んでおり、各人が向いている方向が、L、Rからなる文字列Sで与えられる。どの人も、目の前の人が自分と同じ方向を向いていれば幸福。ただし、目の前に人がいない場合は幸福ではない。
以下の操作をK回まで行う。

操作:
1≤l≤r≤N を満たす整数l,r を選ぶ。西からl,l+1,...,r 番目の人の列を180 度回転する。すなわち、i=0,1,...,r−l について、西からl+i 番目の人は操作後には西からr−i 番目に移動し、元々西を向いていれば東を、東を向いていれば西を向く。

このような操作を行ったときに幸福な人を最大何人にできるか、と言うことを出力する。

考え方

一見して操作の内容の意味が分からない。
こういう時は、まずは入力例と解説みてみる。

6 1
LRLRRL

(l,r)=(2,5) と選べば LLLRLL となり、西から 2,3,6 番目の人が幸福です。

相変わらず何が起きているか分からないが、恐らくこういう感じ。
2から5の間は以下の４文字。

RLRR

これのL,Rをとりあえず反転させる。

LRLL

となる。
これを180度回転させるとこうなる。

LLRL
後は元の文字列とくっつけて…

LLLRLL

こうなった。
とりあえず操作のことは理解できた。
ここで、「なんかこの操作、複雑すぎないか？」という直感を働かせてみる。

もうちょっと簡単になんとかならないか？ということを考える。

LR系の問題はランレングス圧縮をして解くことが多いので、とりあえずやってみる。ランレングス圧縮とは例えばaabbaみたいな文字列があったときに、[[a,2],[b,2],[a,1]]みたいに圧縮する方法。

元の文字列LRLRRLを圧縮するとこうなる。

[[L,1], [R,1], [L,1], [R,2], [L,1]]

もともとの文字列はLとRしかないので、ランレングス圧縮するとかならず、LRLRもしくはRLRLと続くことになる。

良い感じになってきた。
入力例の操作はLとRが混ざってたから複雑な感じがあった。
LもしくはRのみの区間を操作したらどうだろうか。

LRLRと続いていると幸福な人は一人もいない。ここで２番目のRをLにしてみる。

LLLR

なんと、幸福な人が２人増えた。

圧縮しないで、例えばLRRRLRみたいな配列だったらどうだろう。
もともとの幸福な人はRRRの部分の２人。

ここをLに反転させてみる。

LLLLLR
幸福な人が４人に増えた。
おお、また２人増えた。

LRRLRも一緒。もともと１人しかいないのが…
LLLLRで幸福な人が３人となって２人増える。

一般化して考えてみると、もともとRで幸福だった人たちは文字がLになっても幸福なので、増減はない。
それに加えて、こういう操作をすると、両端のLが必ず幸福になるので、２人、幸福な人が増えることになる。

逆に考えてみると、幸福な人が増える余地は両端のみ。
なので、一回の操作で３人以上は増やせない。

答えが見えてきた。
つまり、ランレングス圧縮された世界において、LRLもしくはRLRと違う文字に挟まれた真ん中を、貪欲に反転させていけば、必ず２人増やせる。
ということは、元々幸福だった人数から操作の回数 x 2だけ幸福な人を増やせる、ということになる。

なお間にはさまれた状態がない場合、例えばLRもしくはRLと続くとき。
これはどちらかを反転させれば、全員同じ方向を向けさせることができる。

その場合の幸福な人の人数はN-1で最大。
そのため、答えはmin(k*2+happy people, N-1)となる。

実装

せっかくなのでランレングスエンコードを使ってみた。

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

/**
 * 
 * @param s 文字列
 * @returns aabb => [['a',2],['b',2]]
 */
export const runLengthEncode = (s: string): Array<[string, number]> => {
    if (s.length == 0) return []
    const encoded: Array<[string, number]> = [];
    let currentChar = s[0];
    let count = 1;

    for (let i = 1; i < s.length; i++) {
        if (s[i] === currentChar) {
            count++;
        } else {
            encoded.push([currentChar, count]);
            currentChar = s[i];
            count = 1;
        }
    }
    encoded.push([currentChar, count]);

    return encoded;
}

function main() {
    const [n, k] = nextNums(2)
    const s = next()
    const rle = runLengthEncode(s)
    // 元々幸福な人たち
    let happyPeople = 0
    for (const elm of rle) {
        const [char, cnt] = elm
        // 続いている文字数マイナス1がもともと幸福ーな人の数
        happyPeople += cnt - 1
    }
    const ans = Math.min(happyPeople + k * 2, n - 1)
    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();
}

ランレングスエンコードを使わない場合は、単純にLLと続いている箇所と、RRと続いている箇所を数え上げればいい。

function main() {
    const [n, k] = nextNums(2)
    const s = next()

    // 元々幸福な人たち
    let happyPeople = 0
    // Lで幸福な人を数える
    for (let i = 1; i < n; i++) {
        if (s[i] == 'L' && s[i - 1] == 'L') happyPeople++
    }
    // Rで幸福な人を数える
    for (let i = n - 1; i > -1; i--) {
        if (s[i] == 'R' && s[i + 1] == 'R') happyPeople++
    }
    const ans = Math.min(happyPeople + k * 2, n - 1)
    log(ans)
}