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

AtCoder Beginner Contest 394

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

A - 22222

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

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

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

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

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

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

AWWWWWA
↓
AWWWWAC
↓
AWWWACC
↓
AWWACCC
↓
AWACCCC
↓
AACCCCC

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

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

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

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

まず、括弧の種類が三種類あるので、mapなどで各括弧を対応づけているとわかりやすいでしょう。
次に、左から次の規則に従って括弧を処理していきます。

• 左括弧(,[,<のとき、スタックにpushする
• 右括弧),],>のとき、かつスタックの末尾が対応する左括弧であれば括弧を消せるので、スタックからpopする
• 右括弧),],>のとき、かつスタックの末尾が対応する左括弧でないのであれば消せない括弧が存在することが確定するため、Noを出力する

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

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を全く思い浮かばずすみません笑
レート的には軽傷ですし、気持ちを切り替えて来週また頑張ります。