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

AtCoder Beginner Contest 377

https://atcoder.jp/contests/abc377

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

# A - Rearranging ABC
https://atcoder.jp/contests/abc377/tasks/abc377_a

$S$を並び替えた時に`ABC`と一致させることが可能であることの必要十分条件は
- $S$に`A`,`B`,`C`が1回ずつ出現すること

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

```js
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
https://atcoder.jp/contests/abc377/tasks/abc377_b

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

```js
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
https://atcoder.jp/contests/abc377/tasks/abc377_c

愚直に考えるとコマを置けるマスが最大$10^{18}$箇所のため時間が足りませんが、
- ナイトが存在するマス（高々$2×10^{5}$箇所）
- ナイトが移動可能なマス（ナイトの個数×8箇所）

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

```js
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
https://atcoder.jp/contests/abc377/tasks/abc377_d

公式解説とは少し異なり`重複ありの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((N+M)logN)$で本制約下では十分高速に解くことができました。

```js
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クラスだが省略。
```