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

AtCoder Beginner Contest 399

ABCDの4完（90分3ペナ）でした。
1023perfでレートは1058->1054（-4）となりました。
一週間遅れての記事投稿になりまして申し訳ありません。
（引っ越しでてんやわんやでした。）
今回はABCDをまとめます。

A - Hamming Distance

$S$と$T$を一文字ずつ順番に確認し、文字が異なる個数を数え上げれば良いです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const S = input[1].split("");
  const T = input[2].split("");
  let ans = 0;
  for (let i = 0; i < N; i++) if (S[i] != T[i]) ans++;
  console.log(ans);
}

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

B - Ranking with Ties

問題文で言われた通りにプログラムを書けば良いです。
いまだに問題の意味については理解していません。笑

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const P = input[1].split(" ").map(Number);
  //変数 r を用意し、r=1 と初期化する。最初、N 人の順位はすべて未確定である。
  let r = 1;
  const ans = new Array(N).fill(0);

  //N 人全員の順位が確定するまで以下の操作を繰り返す。

  while (ans.includes(0)) {
    //順位が未確定である人の中での得点の最大値を x とし、
    let x = 0;
    for (let i = 0; i < N; i++) {
      if (ans[i] == 0) x = Math.max(x, P[i]);
    }

    //得点が x である人の数を k とおく。
    let k = 0;
    //得点が x である k 人すべての順位を r 位と確定させたのち、
    for (let i = 0; i < N; i++) {
      if (P[i] == x) {
        ans[i] = r;
        k++;
      }
    }
    //r に k を足す。
    r += k;
  }

  console.log(ans.join("\n"));
}

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

C - Make it Forest

単純無向グラフが森とは、閉路を含まないことを表します。
無向グラフの閉路検出といえばUnionFindです。
すなわち、$N$個のノードを初期化して、与えられた辺それぞれについて、

• 辺の両端が既に連結である：辺を追加すると閉路ができるので捨てる
• 辺の両端が連結でない：辺を追加する

の処理を行い、捨てた辺の本数を数え上げれば良いです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  const [u, v] = [[], []];
  for (let i = 0; i < M; i++) [u[i], v[i]] = input[i + 1].split(" ").map(Number);
  const uf = new UnionFind(N);

  let ans = 0;
  for (let i = 0; i < M; i++) {
    [u[i], v[i]] = [u[i] - 1, v[i] - 1];
    if (!uf.connected(u[i], v[i])) uf.union(u[i], v[i]);
    else ans++;
  }
  console.log(ans);
}
//以下、UnionFindライブラリなので割愛する

D - Switch Seats

バグのないよう丁寧に全探索を実装する問題なので解説らしい解説は割愛しますが、方針だけ記載します。
まず、$a,b$について組が成立するためには、$a$が$b$に少なくとも2回隣接している必要があります。

1 2 3 3 2 1 → 1は2に2回隣接しており、組が成立する

一方で、必ず2回で組が成立するかと言うとそうでもなく、以下のような例では組が成立しません。

1 2 1 3 3 2 → 1は2に2回隣接しているが、同じ2に対して2回隣接しているだけなので組が成立しない

上記のような例のときは、3回隣接している必要があります。3回であれば、以下のパターンに絞れるからです。

1 2 1 2 ...
... 2 1 2 1
これらのケースは組が成立する

以上の考え方をうまくコードに落とし込むことでこの問題に正解できます。
本番では以下のコードで無理やりACを獲得しました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const T = Number(input[0]);
  const cs = new Array(T).fill(0).map(() => []);
  for (let i = 0; i < T; i++) {
    cs[i][0] = Number(input[2 * i + 1]);
    cs[i][1] = input[2 * i + 2].split(" ").map(Number);
  }

  for (let i = 0; i < T; i++) {
    let n = cs[i][0];
    let a = cs[i][1];
    let where = new Array(n + 1).fill(0).map(() => []);
    let neighbor = new Array(n + 1).fill(0).map(() => new Map());
    for (let j = 0; j < 2 * n; j++) {
      where[a[j]].push(j);
      if (j > 0) neighbor[a[j]].set(a[j - 1], (neighbor[a[j]].get(a[j - 1]) || 0) + 1);
      if (j < 2 * n - 1) neighbor[a[j]].set(a[j + 1], (neighbor[a[j]].get(a[j + 1]) || 0) + 1);
    }

    for (let j = 1; j <= n; j++) {
      where[j].sort((a, b) => a - b);
    }

    let ans = 0;
    for (let j = 1; j <= n; j++) {
      if (where[j][1] - where[j][0] == 1) continue;
      for (const [key, value] of neighbor[j]) {
        if (key < j) continue;
        if (where[key][1] - where[key][0] == 1) continue;

        if (where[j][1] - where[j][0] == 2) {
          if (a[where[j][0] + 1] == key) {
            if (neighbor[key].get(j) >= 3 && value >= 3) ans++;
          }else {
            if (neighbor[key].get(j) >= 2 && value >= 2) ans++;
          }
        } else {
          if (where[key][1] - where[key][0] == 2) {
            if (a[where[key][0] + 1] == j) {
              if (neighbor[key].get(j) >= 3 && value >= 3) ans++;
            }else {
              if (neighbor[key].get(j) >= 2 && value >= 2) ans++;
            }
          }else {
            if (neighbor[key].get(j) >= 2 && value >= 2) ans++;
          }
        }
      }
    }
    console.log(ans);
  }
}

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

本当はもっと綺麗にしたかったのですが、時間が、、、、

まとめ

記事の更新がだいぶ遅くなり失礼しました。
引っ越しも仕事も山場は超えたので、そろそろ精進を再スタートしたいと思います。