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

AtCoder Beginner Contest 377

A~Dの4完（81分）でした。
1041perfでレートは846->867（+21）です。
今回はコンテスト中に解けたA~Dをまとめます。

A - Rearranging ABC

$S$を並び替えた時にABCと一致させることが可能であることの必要十分条件は

• $S$にA,B,Cが1回ずつ出現すること

ですので、ハッシュマップでA,B,Cの出現回数を管理しておいて全部が1であることを確認すれば良いです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("");
  const arr = new Map([
    ["A", 0],
    ["B", 0],
    ["C", 0],
  ]);
  for (let i = 0; i < S.length; i++) arr.set(S[i], arr.get(S[i]) + 1);
  if (arr.get("A") === 1 && arr.get("B") === 1 && arr.get("C") === 1) console.log("Yes");
  else console.log("No");
}

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

B - Avoid Rook Attack

本問題は$8×8$とかなり制約が緩いですが、$O(N^2)$で解く方法を紹介します。
同じ行と列にルークが存在するマスにコマを置くとそのコマは取られてしまいます。
よって、各行各列に一つでもルークが存在するかどうかの結果を$\text{row,col}$配列に前もって格納しておき、全てのマス$[i, j] (0≦i,j<8)$についてコマが置けるかどうかを$\text{row}[i]$,$\text{col}[j]$を見ながら判定すればよいです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = [];
  for (let i = 0; i < 8; i++) S.push(input[i].split(""));
  
  let row = new Array(8).fill(false);
  let col = new Array(8).fill(false);
  for(let i = 0; i < 8; i++) {
    for(let j = 0; j < 8; j++) {
      if(S[i][j] === "#") {
        row[i] = true;
        col[j] = true;
      }
    }
  }

  let ans = 0;
  for(let i = 0; i < 8; i++) {
    for(let j = 0; j < 8; j++) {
      if(!(row[i] || col[j])) ans++;
    }
  }
  console.log(ans);
}

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

C - Avoid Knight Attack

愚直に考えるとコマを置けるマスが最大$10^{18}$箇所のため時間が足りませんが、

• ナイトが存在するマス（高々$2×10^{5}$箇所）
• ナイトが移動可能なマス（ナイトの個数×8箇所）

の置けないマスの個数さえわかればそれ以外のマスにはコマを置ける訳ですから、$全てのマスの個数-置けないマスの個数$を求めることにすれば十分間に合います。
なお、ナイトの移動先には重複がありえるので、置けないマスの管理にはSetを使います。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(BigInt);
  const a = [],
    b = [];
  for (let i = 0; i < M; i++) [a[i], b[i]] = input[i + 1].split(" ").map(BigInt);

  let ans = N * N;
  let dx = [1n, 2n, 2n, 1n, -1n, -2n, -2n, -1n];
  let dy = [-2n, -1n, 1n, 2n, 2n, 1n, -1n, -2n];
  let set = new Set();
  for (let i = 0; i < M; i++) set.add(a[i] * N + b[i]);
  for (let i = 0; i < M; i++) {
    let x = a[i],
      y = b[i];
    for (let j = 0; j < 8; j++) {
      let nx = x + dx[j];
      let ny = y + dy[j];
      if (nx < 1n || nx > N || ny < 1n || ny > N) continue;
      if (set.has(nx * N + ny)) continue;
      set.add(nx * N + ny);
    }
  }
  ans -= BigInt(set.size);
  console.log(ans.toString());
}

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

D - Many Segments 2

公式解説とは少し異なり重複ありのSortedSet+尺取り法のアプローチを解説します。
まず、全ての$i$について$l≦\text{L}[i]$が成り立つ状況を考えます。このとき、「区間$[l,r]$が全ての$i$について$[\text{L}[i],\text{R}[i]]$を完全に含まない」ための必要条件は、「$r$が$\max_{i \in N} \text{R}[i]$よりも厳密に小さいこと」となります。したがって、この条件を満たす区間$[l,r]$の個数は$\max_{i \in N} \text{R}[i] - l$です。

次に、$l$をどんどん右にずらしていくことを考えます。すると、$l>\text{L}[i]$を満たすような$i$が現れることもありますが、そのような$i$については$r$がどんな値をとっても、「区間$[l,r]$が$[\text{L}[i],\text{R}[i]]$を完全に含む」ことはありえません。したがって、このような$i$の集合を$S$とすれば、この条件を満たす区間$[l,r]$の個数は$\max_{i \in N, i \notin S} \text{R}[i] - l$となります。$l>\text{L}[i]$を満たす$i$を順次$S$に追加することにしておけば、$0<l≦M$の全ての$l$について同じ計算式が使えます。
なお、$\text{R}[i]$が$M+1$以上である場合もあるため上限を$M$に設定する必要があります。

以上の方針がわかればあとは実装するだけですが、概要だけお伝えすると$\max_{i \in N, i \notin S} \text{R}[i]$はSortedSet、$l$を左からどんどん右にずらしていくのは尺取り法で高速に実装できます。また、$\text{R}[i]$が重複することもあるのでMultisetの要領で$\text{times}$配列にて考慮が必要な$R[i]$の個数を管理しておき、$\text{times}[\text{R}[i]]=0$となった場合にのみ考慮から除外するようにします。
したがって、上記の解法では$O(NlogN+M)$で本制約下では十分高速に解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  const L = [],
    R = [];
  let pair = [];
  for (let i = 0; i < N; i++) {
    [L[i], R[i]] = input[i + 1].split(" ").map(Number);
    pair.push([L[i], R[i]]);
  }
  pair.sort((a, b) => a[0] - b[0]);
  const times = Array.from({ length: M + 1 }, () => 0);

  const set = new SortedSet();
  for (let i = 0; i < N; i++) {
    set.add(R[i]);
    times[R[i]]++;
  }

  let ans = 0;
  let pointer = 0;
  for (let i = 1; i <= M; i++) {
    while (pointer < N && pair[pointer][0] < i) {
      times[pair[pointer][1]]--;
      if (times[pair[pointer][1]] === 0) set.delete(pair[pointer][1]);
      pointer++;
    }
    let minR = set.getSize() === 0 ? M + 1 : set.tree[set.first].value;
    ans += Math.max(Math.min(M + 1, minR) - i, 0);
  }
  console.log(ans);
}

//  以下、自前のSortedSetクラスだが省略。