【JavaScript】ABC380まとめ（A~D）

AtCoder Beginner Contest 380

ABCの3完（26分）でした。
731perfでレートは892->877（-15）で、久々に茶パフォを取りそこそこ冷えてしまいました。
敗因としては、D問題の嘘解法で30分ドブに捨てた後に正しい解法を思いついたものの、実装が面倒に感じたためE問題に行き、結局E問題も解けなかったことにあります。
仮にE問題が解けていたら配点傾斜的にも水perf出ていたと思うので、ハイリスクハイリターンな賭けで普通に負けてしまったなという感想です。
とはいえ、今回はA~Dまで満遍なく新たな学びが得られたため、良い問題セットだと感じました。
この記事では、A~Dをまとめます。

A - 123233

大きく二つに分けて、「各桁ごとに数値が登場する個数を数える」方法と、「Nを文字列としてみて、ソート後に122333と一致するかどうか調べる（122333をソート済み文字列と捉えることができるため）」方法があると思いますが、コンテスト中は素直に前者で解きました。

各桁ごとの個数については、標準メソッドのeveryメソッドを使うと簡潔に書くことができます。
everyメソッドは第一引数にelement、第二引数にてindexを受け取るため、「$i$が$i$回ずつ出現する」はevery((v, i) => v == i)のように書けます。以下のソースコードでは、数値$i$をインデックス$i-1$に対応させているため、$1$だけズレが生じていますが同じことです。

なお、$N$は$1〜3$の文字だけを含むとは限らないため範囲外アクセスを含みますが、本問題では$1〜3$以外の数字は言及されていないため問題ありません。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = input[0].split("");
  let arr = new Array(3).fill(0);
  for (let i = 0; i < N.length; i++) arr[N[i] - 1]++;

  arr.every((v, i) => v == i + 1) ? console.log("Yes") : console.log("No");
}

Main(require("fs").readFileSync(0, "utf8"));

B - Hurdle Parsing

split("|")で-の塊ごとに分割し、要素の個数を出力すればよいです。
先頭・末尾に|があるため、split("|")後にfilter((v) => v)で空文字列を削除する必要があります。（vが空文字列のときfalse評価され除去されます）

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("|").filter((v) => v);
  let ans = [];
  for (let i = 0; i < S.length; i++) ans.push(S[i].length);
  console.log(ans.join(" "));
}

Main(require("fs").readFileSync(0, "utf8"));

C - Move Segment

01文字列について、0の塊と1の塊ごとに分割し、1の塊の$K$番目を手前の0の塊と入れ替えればよいです。
まず、0の塊と1の塊ごとに分割するランレングス圧縮のパートは、while文などで実装することができますが、JavaScriptのmatchメソッドを使った正規表現で書くのが最も簡潔だと思います。S.match(/(.)\1*/g)$^*$で、簡単に同じ要素の塊ごとに分割された配列$T$を生成することができます。（例：0001110010→[000,111,00,1,0]）
あとは、1の塊がこの配列$T$の何番目かを特定すれば、その一つ前の要素と入れ替えた上で文字列に変換して出力することでこの問題をACすることができます。

$^*$正規表現については本記事では深くは触れませんが、ソースコードに対しての文法は以下を参考にしていただき、不明点があればMDNリファレンス等を参照してください。

• / / : 正規表現の開始と終了
• (.) : 任意の1文字をキャプチャ（括弧で囲むことでグループ化）
• \1 : 1番目のキャプチャグループ（つまり直前でキャプチャした文字）を参照
• * : 直前のパターンを0回以上繰り返し
• g : グローバルフラグ（文字列全体でマッチを探す）

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, K] = input[0].split(" ").map(Number);
  const S = input[1];
  const T = S.match(/(.)\1*/g);
  let idx = 2 * (K - 1) - (S[0] == 0 ? 0 : 1);
  [T[idx], T[idx + 1]] = [T[idx + 1], T[idx]];
  console.log(T.join(""));
}

Main(require("fs").readFileSync(0, "utf8"));

D - Strange Mirroring

本問題は01文字列の規則性に着目して解く必要があるのですが、公式解説のpopcountを利用した解法は一定の事前知識やひらめきが必要なため思いつくのが難しいです。
したがって、より直感的な解法として再帰的に解く方法を紹介します。

まず、問題を観察することによって、01文字列の規則性を考えてみましょう、
はじめに、$S$に対し$k$回操作してできた文字列を$S^k$、文字列$S^k$の大文字小文字を反転させた文字列を$flipS^k$とおきます。すると、今ある文字列の大文字と小文字を反転させたものをくっつけるという操作の定義より、$S^k$は一般に$S^{k-1}+flipS^{k-1}$と書くことができます。ここで、$S^{k-1}$と$flipS^{k-1}$の長さは等しいため、$S^k$のちょうど前半は$S^{k-1}$であり、後半は$flipS^{k-1}$に当たることがわかります。

例えば、サンプルケース1の文字列$S=$aBに対し3回操作を加えた文字列$S^3=$aBAbAbaBAbaBaBAbをじーっと観察してみます。この場合、$S^2=$aBAbAbaB、$flipS^2=$AbaBaBAbであるため、$S^3=S^2+flipS^2$がきちんと成り立っています。

次に、この規則性を使って、任意の$K_i$が与えられた時に$S^{10000000...}$の$K_i$番目が$S$に含まれる文字なのか、それとも$flipS$に含まれる文字なのかを判別することを目指しましょう。これは、二分探索をイメージするとわかりやすいです。
（なお、操作は$10^{100}$回行うとありますが、実際には60回程度で$10^{18}$を突破するため、操作の上限は60回と考えればよいです。もっと言うと、$2^{k-1}<\max_{i \in Q} K_i$を満たす最大の$k$を考えれば十分です）

例えば、$S^3=$aBAbAbaBAbaBaBAbの$13$番目の文字について考えてみます。
まず、$S^3$を$S^2$と$flipS^2$に分解した時、$2^3=8<13$なので後半にあたります。したがって、反転ビットフラグを1にセットしておきます（ここで、反転ビットフラグが1のとき$flipS^k$に属することを示す）。

• ここまでで、$13$番目の文字は$flipS^2$に属することがわかった

次に、$flipS^2=$AbaBaBAbをさらに二つに分解することを考えます。$S^3$のときと同様に考えると、$flipS^2=flipS^1$+$flipflipS^1$ですが、すでに反転されたものを再度反転させると元に戻るので、結局$flipS^2=flipS^1$+$S^1$のように書けます。すなわち、$flipS^2$の前半部分が$flipS^1$であり、後半部分は$S^1$にあたります。元の例に戻ると、$8+2^2=12<13$のため$13$番目の文字はここでも後半部分にあたるため、反転ビットフラグを0に戻しておきます。

• ここまでで、$13$番目の文字は$S^1$に属することがわかった

さらに、$S^1=$aBAbを再度二つに分解します。$S^1=S + flipS$で、やっと最初の文字列が見えてきました。ここで、$13$番目が$S^1$の前半にあるのか、後半にあるのかを判定することによって、$13$番目の文字が$S$に含まれる文字なのか、それとも$flipS$に含まれる文字なのかが明らかになります。実際に計算してみると、$12+2^1=14>13$のため$13$番目の文字はここでは前半部分にあたる、すなわち$S$に含まれることが一連の作業でわかりました。

• 最終的に、$13$番目の文字は$S$に属することがわかった

以上の作業で着目すべきことは、以下の二点です。

• 二分探索の要領で調べることで、$K_i$番目の文字が$S$に属するのか、$flipS$に属するのかが対数時間($O(logK)$)でわかる
• 反転ビットフラグを利用することで、探索中に自分が今反転されているのかいないのかがわかる

ここまでくれば、$S$ないし$flipS$の中で何番目の文字なのかは$K_i \bmod len (:=Sの文字列長)$で瞬時に特定することができます。
また、JavaScript特有の問題ではありますが、$10^{18}$のような大きな数値を利用する場合BigInt型を利用する必要があり、かつBigInt型の数値計算が非常に重いので、$2^k$や$len \times 2^k$は前計算しておかないとTLが非常に厳しいです。

最後に、余談ですが文字を大文字、小文字に反転させるのには標準メソッドのtoLowerCase()やtoUpperCase()を使っても良いのですが、実は文字をasciiコードに変換して32とのxorを取るだけで実装できてしまいます。筆者も今回初めて知ったので今後ぜひ使っていきたいと思いました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("");
  const Q = Number(input[1]);
  const K = input[2].split(" ").map(BigInt);
  let len = S.length;
  let max = 60;

  let pow2 = Array(max + 1).fill(1n);
  for (let i = 1; i <= max; i++) pow2[i] = pow2[i - 1] * 2n;
  let prod = Array(max + 1).fill(0n);
  for (let i = 0; i <= max; i++) prod[i] = BigInt(len) * pow2[i];
  const flipS = [];
  for (let i = 0; i < S.length; i++) flipS.push(String.fromCharCode(S[i].charCodeAt(0) ^ 32));

  let ans = [];
  for (let i = 0; i < Q; i++) {
    let cur = 0;
    let tmp = max;
    let q = K[i];
    while (q > BigInt(len)) {
      if (prod[tmp] >= q) {
        tmp--;
        continue;
      }

      q -= prod[tmp];
      if (prod[tmp] >= q) cur ^= 1;
    }
    ans.push(cur == 0 ? S[Number(q) - 1] : flipS[Number(q) - 1]);
  }
  console.log(ans.join(" "));
}

Main(require("fs").readFileSync(0, "utf8"));

E問題はぱっと見UnionFindの典型ですが、ルートで左端と右端を持てるように構造体の中身を変更しなければならず、その具体的なやり方がわからなかったので解けませんでした。。。
DPやグラフ系の水色diff問題が解けないのが最近の悩みです。