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

AtCoder Beginner Contest 380

https://atcoder.jp/contests/abc380

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

# A - 123233
https://atcoder.jp/contests/abc380/tasks/abc380_a

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

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

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

```js
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
https://atcoder.jp/contests/abc380/tasks/abc380_b

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

```js
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
https://atcoder.jp/contests/abc380/tasks/abc380_c

`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リファレンス](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/String/match)等を参照してください。
- `/   /` : 正規表現の開始と終了
- `(.)`   : 任意の1文字をキャプチャ（括弧で囲むことでグループ化）
- `\1`    : 1番目のキャプチャグループ（つまり直前でキャプチャした文字）を参照
- `*`     : 直前のパターンを0回以上繰り返し
- `g`     : グローバルフラグ（文字列全体でマッチを探す）

```js
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
https://atcoder.jp/contests/abc380/tasks/abc380_d

本問題は`01`文字列の規則性に着目して解く必要があるのですが、[公式解説](https://atcoder.jp/contests/abc380/editorial/11362)の`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$がきちんと成り立っています。

<br>

次に、この規則性を使って、任意の$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$に属することがわかった

<br>

以上の作業で着目すべきことは、以下の二点です。
- 二分探索の要領で調べることで、$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`を取るだけで実装できてしまいます。筆者も今回初めて知ったので今後ぜひ使っていきたいと思いました。

```js
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問題が解けないのが最近の悩みです。