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

AtCoder Beginner Contest 381

ABCDの4完（84分6ペナ）でした。
983perfでレートは877->888（+11）となりました。全然どうでもいいですがゾロ目ですね(？)
感想としては、B問題で"同じ文字を使えない"ということに気づけず3ペナしたことと、C問題で少しグダってしまったことが原因で1000perfには届きませんでしたが、なんとかD問題を通して緑perfを出せたのでよかったです。
この記事では、A~Dをまとめます。

A - 11/22 String

まず、文字列$S$を「真ん中より左」「真ん中」「真ん中より右」のグループに分けます。
以下の条件を全て満たす時、文字列$S$は11/22文字列といえます。

• 「真ん中より左」のグループにある文字が全て1
• 「真ん中」の文字が/
• 「真ん中より右」のグループにある文字が全て2
• 「真ん中より左」と「真ん中より右」の文字数が一致する

文字列$S$の長さが偶数の時、四番目の条件は必ず落ちるので、「真ん中」のインデックスは$\lfloor N/2 \rfloor$として問題ありません。
なお、以下のコードはsliceメソッドを使用していますが、若干添字の扱い方に癖があるのでそこだけ注意しましょう。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const S = input[1].split("");

  // idx := 文字列Sの真ん中の位置
  let idx = Math.floor(N / 2);
  // [one, two] := [文字列Sの半開区間[0, idx), 文字列Sの閉区間[idx + 1, S.length - 1]]
  let one = S.slice(0, idx);
  let two = S.slice(idx + 1);
  
  for (let i = 0; i < one.length; i++) if (one[i] != "1") return console.log("No");
  for (let i = 0; i < two.length; i++) if (two[i] != "2") return console.log("No");

  if (S[idx] == "/" && one.length == two.length) console.log("Yes");
  else console.log("No");
}

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

B - 1122 String

まず文字列$S$をランレングス圧縮して、同じ文字が連続するブロックごとに分割した配列$T$を作成します。
（例：$S=$aabbcdddのとき、$T=[$ aa,bb,c,ddd $] $)
このとき、以下の条件を満たす時、文字列$S$は1122文字列といえます。

• 文字列$T$の各要素の長さが全て2
• 文字列$T$の中で、同じ文字で構成されるブロックが他に一つも存在しない

2番目の条件は、英小文字[a-z]を番号[0-25]に紐づけることで、26個の要素からなる配列で既に出現したかどうかを管理すればよいです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("");
  // T := ランレングス圧縮
  const T = S.join("").match(/(.)\1*/g);
  // used := 英小文字[a-z]が出現したかどうかを管理
  const used = Array(26).fill(false);

  for (let i = 0; i < T.length; i++) {
    if (T[i].length !== 2) return console.log("No");
    let c = T[i].charCodeAt(0) - "a".charCodeAt(0);
    if (used[c]) return console.log("No");
    used[c] = true;
  }
  console.log("Yes");
}

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

C - 11/22 Substring

公式解説がとてもわかりやすく書かれているので詳細は省略しますが、文字列$S$中の全ての/について/,1/2,11/22,111/222...のように/から見て左が1、右が2としてどこまで広げられるかを全探索します。
計算量については、例えば11/221/2を例にとると、3番目の/は1-5番目、7番目の/は6-8番目までしか見なくて済むように、互いに異なる/については見るべき位置が重複することはないので全体として$O(N)$におさまります。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const S = input[1].split("");

  let ans = 0;
  for (let i = 0; i < N; i++) {
    if (S[i] !== "/") continue;
    // pl := iのpl個前とpl個後を見て、それぞれ"1"と"2"になっている分だけ伸ばす
    let pl = 1;
    while (i - pl >= 0 && i + pl < N) {
      if (S[i - pl] == "1" && S[i + pl] == "2") pl++;
      else break;
    }
    ans = Math.max(ans, pl - 1);
  }
  console.log(ans * 2 + 1);
}

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

D - 1122 Substring

最初に断っておくと、やや一般的ではない角度からの解法です。
まず、配列$A$はそのままだと少し扱いづらいので、以下の規則で長さ$N-1$の配列$B$を生成します。

• $A_i ≠ A_{i+1}$のとき、$B_i =$0
• $A_i = A_{i+1}$のとき、$B_i =$1

こうすることで何が嬉しいかと言うと、配列$B$の連続部分列が101...101のように、1と0が交互に出現し、かつ両端が1となっているとき、それは1122文字列といえます（厳密には、同じ数字のペアが重複してはいけませんが、それは一旦脇においておきます）。
例えば、$A=[2,1,1,2,2,3,3,3,4,4]$のとき、$B=[0,1,0,1,0,1,1,0,1]$です。配列$A$のままだと、偶数始点カットと奇数始点カットの2パターンを考えながら実装しなければなりませんが、配列$B$であれば単純に01が交互に出現し、かつ両端が1で挟まれた領域＊を考えるだけで済みます。これであれば、左から右へ愚直に線形探索すれば最長の領域＊を求めることができるため$O(N)$となります。また、配列$B$において「$A_i = A_{i+1}$のとき、$B_i =$1」という定義より、配列$A$における1122文字列の長さは領域＊のうち「1が立っている個数×2」です。
上記の例の場合、最長の領域＊は$[1,0,1,0,1]$、1122文字列の長さは6となります。

次に、「1122文字列は同じ数字のペアが重複してはいけない」という条件の実装方針を考えます。
（例：$A=[1,1,2,2,1,1]$のとき$B=[1,0,1,0,1]$ですが、$[A_1,A_2]$と$[A_5,A_6]$はいずれも1からなるペアのため領域を分割する必要があります）
これは、ハッシュマップで$A_i$が以前にいつ出現したか、そして今更新している領域＊に含まれているかどうかを確認し、含まれているとき領域＊を分割するようにすれば正しく実装できます。
上記の例だと、$i=5$に到達した時$A_5=1$が既に領域＊で利用されているため、$i=1$から始まる$[1,0,1,0]$の領域＊をここでぶっちぎって、以前1が利用されたインデックスの直後で$B_i=1$となっている$i=3$から始まる$[1,0,1]$の領域＊を新たに作成します。そうすることで、実質的に領域＊は$[1,0,1]$と$[1,0,1]$の二つに分割することができます。その上で1122文字列の最長の長さを計算すると4なので辻褄が合います。

以上、お気持ち程度の解説でしたが、具体的な実装方法については以下のコードを参考にしてほしいです。コメントにも簡単に解説を入れておきますので、気持ちだけでも理解いただけると幸いです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);
  const B = Array(N - 1).fill(0);
  for (let i = 0; i < N - 1; i++) if (A[i] == A[i + 1]) B[i] = 1;
  // Aの要素が以前どのインデックスで出現したかを管理
  const map = new Map();

  // ans := 最長の1122文字列の長さ
  // res := 今更新している領域＊の1122文字列の長さ
  // left := 今更新している領域＊の左端
  let [ans, res, left] = [0, 0, 0];
  for (let i = 0; i < N - 1; i++) {
    if (B[i] == 1) {
      // 領域＊にA[i]がまだ出現していない
      if (!map.has(A[i]) || map.get(A[i]) < left) {
        res++;
        ans = Math.max(ans, res);
      // 領域＊にA[i]が出現している
      } else {
        ans = Math.max(ans, res);
        left = map.get(A[i]) + 1;
        // 1が2個以上連続する場合に対応できるようにしている
        res = Math.ceil((i - map.get(A[i]))/ 2);
      }
      map.set(A[i], i);
    } else {
      // 0が連続する場合はリセットする
      if (res > 0 && B[i - 1] == 0) {
        res = 0;
        map.clear();
      }
    }
  }
  console.log(ans * 2);
}

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