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

AtCoder Beginner Contest 394

https://atcoder.jp/contests/abc394

ABCDの4完（22分0ペナ）でした。
1004perfでレートは1057->1051（-6）となりました。
C問題は過去に水上位の類題（[abc329E-Stamp](https://atcoder.jp/contests/abc329/tasks/abc329_e)）を解いたことがあり、難しく考えすぎてしまい13分もかけてしまいました。
E問題は78分考えても考察で手も足も出ず、、、（真ん中から考えるのはどうか、というアイデアは浮かびましたが、自己ループについての処理を解決できませんでした）
F問題は正答者が少なかったので全くみませんでしたが、E問題解けずに椅子を温め続けるくらいなら、今後は5分くらいはF問題に時間を割きたいと思います。
今回はA~Dをまとめます。

# A - 22222
https://atcoder.jp/contests/abc394/tasks/abc394_a

`JavaScript`の`filter`メソッドを使って、"2"だけを抜粋して出力します。
注意点として、文字列そのままに適用することはできないため、配列に変換してから適用する必要があります。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("");
  const T = S.filter((v) => v == "2");
  console.log(T.join(""));
}

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

# B - cat
https://atcoder.jp/contests/abc394/tasks/abc394_b

**文字列の長さ**でソートします。なお、異なる行$i,j$の$S_i,S_j$について、$|S_i|≠|S_j|$が保証されています。
`JavaScript`では他の多くのプログラミング言語と同様に`sort`関数が用意されています。
何も引数に渡さず`sort()`と書くと、デフォルトでは**文字列の昇順**にソートされてしまうため、自分で**文字列の長さ**で評価する関数を書く必要があります。
書き方は以下の`AC`コードを参照してください。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const S = [];
  for (let i = 0; i < N; i++) S[i] = input[i + 1];
  S.sort((a, b) => a.length - b.length);
  console.log(S.join(""));
}

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

# C - Debug
https://atcoder.jp/contests/abc394/tasks/abc394_c

[公式解法(解法1. 直前の操作を行った場所から1つ戻って検索を再開する解法)]([https://atcoder.jp/contests/abc394/editorial/12280)で解きました。
ぱっと見でわからない場合はとりあえず実験してみるのが定石です。
例えば、`AWWWWWA`という文字列の場合どうなるかを考えてみましょう。

```tex
例)AWWWWWAという文字列について、WAという文字列を可能な限りACに置換する

AWWWWWA
↓
AWWWWAC
↓
AWWWACC
↓
AWWACCC
↓
AWACCCC
↓
AACCCCC
```

なるほど、`WA`を`AC`に変更した時に、その直前に`W`があると`WAC`となり、新たに`WA`という文字列が出現する仕組みのようです。
したがって、`WW...A`を`ACC...`のような文字列に変えた答えが、本問題で出力すべき文字列となります。

そのアルゴリズムの実装について考えます。
まず、`WW...A`の場所を探して、その場所を同時に`ACC...`に変えればよいですから、これは問題なく$O(N)$の全探索で探索できます。
以下、参考の`AC`コードを記載します。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("");
  for (let i = 1; i < S.length; i++) {
    if (S[i] == "A") {
      // "WWWWWA"の最初の"W"まで戻る
      let j = i - 1;
      while (j >= 0 && S[j] == "W") j--;
      // "WWWWWA"の最初の"W"は"A"に、それ以降は"C"に変更して"ACCCCC"にする
      S[j + 1] = "A";
      for (let k = j + 2; k <= i; k++) S[k] = "C";
    }
  }
  console.log(S.join(""));
}

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

# D - Colorful Bracket Sequence
https://atcoder.jp/contests/abc394/tasks/abc394_d

**括弧列**は`stack`と`dp`が典型ですが、今回は「連続文字列となる部分を可能な限り消去することができるか？」が問われていることなので、`stack`で解くことが可能です。

まず、括弧の種類が三種類あるので、`map`などで各括弧を対応づけているとわかりやすいでしょう。
次に、左から次の規則に従って括弧を処理していきます。
- 左括弧`(,[,<`のとき、スタックに`push`する
- 右括弧`),],>`のとき、かつスタックの末尾が対応する左括弧であれば括弧を消せるので、スタックから`pop`する
- 右括弧`),],>`のとき、かつスタックの末尾が対応する左括弧で**ない**のであれば消せない括弧が存在することが確定するため、`No`を出力する

このようにすることで、「連続する括弧を全て消去することができるか？」を$O(N)$の走査で確認することができます。
なお、`No`を出力すべきケースとしては、他にも「文字列全て左括弧である場合」のように、左括弧が消えずに余ってしまうケースがありますので、**最終的にスタックの中身がなくなっている**ことも判定項目として考慮する必要があります。
以上を踏まえて、この問題を解くことができました。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("");
  const map = new Map([
    [")", "("],
    ["]", "["],
    [">", "<"],
  ]);

  const st = [];
  for (let i = 0; i < S.length; i++) {
    // 左括弧なら必ずスタックに入れる
    if (S[i] == "(" || S[i] == "[" || S[i] == "<") st.push(S[i]);
    else {
      // 右括弧なら、スタックの最後を見て対応する左括弧かどうか確認する。対応しない場合その時点でNG
      if (st[st.length - 1] == map.get(S[i])) st.pop();
      else return console.log("No");
    }
  }
  console.log(st.length == 0 ? "Yes" : "No");
}

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

E問題は`DFS`で全ての単純パスを列挙するという嘘解法しか思い浮かびませんでしたが、`BFS`で解くようです。bfsというユザネなのに`BFS`を全く思い浮かばずすみません笑
レート的には軽傷ですし、気持ちを切り替えて来週また頑張ります。