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

AtCoder Beginner Contest 408

https://atcoder.jp/contests/abc408

ABCDの4完（87分0ペナ）でした。
965perfでレートは1156->1138（-18）となりました。
今回はA〜Dをまとめます。

# A - Timeout
https://atcoder.jp/contests/abc408/tasks/abc408_a

簡単のため、$T_0=0$とします。
このとき、全ての$i=1,\cdots,N$について$T_i-T_{i-1}≦0$が成り立つならば、長老は$T_N$秒後まで連続的に起きているといえます。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, S] = input[0].split(" ").map(Number);
  const T = input[1].split(" ").map(Number);
  let f = true;
  T.unshift(0);
  for (let i = 1; i <= N; i++) {
    if (T[i] - T[i - 1] > S) {
      f = false;
      break;
    }
  }
  if (f) console.log("Yes");
  else console.log("No");
}

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

# B - Compression
https://atcoder.jp/contests/abc408/tasks/abc408_b

まず、配列$A$の要素を展開してハッシュセットに格納することで、重複が削除されます。
次に、ハッシュセットの要素を再度配列として取り出し、昇順にソートすることで、求めるべき配列を得ることができます。
この配列の長さと要素を2行にわたって出力しましょう。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);
  const set = new Set([...A]);
  let C = Array.from(set).sort((a, b) => a - b);
  console.log(C.length);
  console.log(C.join(" "));
}

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

# C - Not All Covered
https://atcoder.jp/contests/abc408/tasks/abc408_c

最も守りの手薄な城壁を狙えばよいです。
イメージを掴むために、下の図を見てください。
なお、星は砲台、線は砲台が守っている範囲を示します。
![Frame 10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3866035/f5663180-8997-43c5-9af0-eaef60ad557a.png)

上の図の例では、
- 城壁１を守っているのは緑の砲台１つ
- 城壁２を守っているのは緑、水色、青の砲台３つ
- 城壁３を守っているのは緑、青、紫の砲台３つ
- 城壁４を守っているのは緑、青、紫、赤の砲台４つ
- 城壁５を守っているのは緑、紫、赤の砲台３つ

のため、明らかに緑の砲台を１つだけ破壊して城壁１を攻めるのが得策だとわかります。したがって、この場合は`1`を出力します。

このように、各城壁がそれぞれ何個の砲台に守られているかを求め、その中で最も少ない砲台数を求めれば十分です。

本問題では砲台$i$の守備範囲が$L_i$以上$R_i$以下の区間と定められています。このようなケースでは、`imos法`という累積和を利用したアルゴリズムにより各城壁がそれぞれ何個の砲台に守られているかを$O(N)$で求めることができます。

具体的な実装については、以下のACコードを見てください。
`imos`配列で各城壁ごとに守っている砲台数が保存されているので、その最小値を出力することでこの問題に正解することができます。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  const [L, R] = [[], []];
  for (let i = 1; i <= M; i++) {
    let [l, r] = input[i].split(" ").map(Number);
    l--;
    r--;
    L.push(l);
    R.push(r);
  }

  let imos = new Array(N + 1).fill(0);
  for (let i = 0; i < M; i++) {
    imos[L[i]]++;
    imos[R[i] + 1]--;
  }

  for (let i = 1; i <= N; i++) {
    imos[i] += imos[i - 1];
  }

  let min = Math.min(...imos.slice(0, N));
  console.log(min);
}

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

# D - Flip to Gather
https://atcoder.jp/contests/abc408/tasks/abc408_d

`耳DP`をやったことがなく、どうしても`DP`解法を思いつけなかったので`優先度付きキュー`を利用した探索的解法でACしました。

まず、文字列中の`1`が立っている任意の位置を$l$とします。
このとき、区間$[l,r]$内だけを`1`にするために必要な操作回数が最小となるような$r$およびその操作回数が$O(logN)$で探索できるのであれば、その探索を`1`が立っている全ての位置について繰り返し、それぞれの最小操作回数の最小値を求めることで答えを得ることができます。これは、全体計算量$O(NlogN)$となります。

まず、$r$の性質について考えます。
$r$が大きくなればなるほど、区間$[l,r]$における`0`を`1`にする回数$p$は単調増加、区間(r,N]における`1`を`0`にする回数$q$は単調減少となります。
求めたいのは$\min(p+q)$ですが、$p+q$には単調性がないため困りました。

ここで、$l$を大きくしても、$r$を大きくした時の$p,q$の**階差数列、および階差数列の累積和における相対的な大小関係は変化しない**ことに着目してください。
例えば、$N=12, T=111100010011$を例に取って考えます。
| $i$番目~$i+1$番目の`1` | $i=1$ | $i=2$ | $i=3$ | $i=4$ | $i=5$ | $i=6$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|  $p$ | 0  |  0 | 0  | 3  | 2  | 0  |
|  $q$ | -1  | -1  |  -1 | -1  | -1  | -1  |
| $p+q$  | -1  | -1  | -1  | 2  | 1  | -1  |
| $p+q$の累積和  | -1  | -2  | -3  | -1  | 0  | -1  |

この例では、1番目の`1`の位置を$l=0$としたとき、$p+q$の累積和が$i=3$で最小となっています。このときの$i$こそ、区間$[l,r]$だけが`1`となるように操作した場合に操作回数が最小となるような$r$です。

![Frame 11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3866035/be70d1d6-d205-4c2d-b3a5-d41c8b61b2db.png)

したがって、$p+q$の累積和と位置の組を最小ヒープに入れておき、$r≧l$となるような$r$を各$l$に対して高速に取り出せるようにすることで、各$l$についての最小操作回数が$O(logN)$で求められます。あとは、全ての$l$における最小操作回数の最小値を求めればこの問題に正解できます。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const T = Number(input[0]);
  const ans = new Array(T).fill(0);

  for (let i = 0; i < T; i++) {
    const N = Number(input[2 * i + 1]);
    const S = input[2 * i + 2];
    const pq = new PriorityQueue((a, b) => a[0] - b[0]);

    // 1の個数をO(1)で取得できるようにする
    const cntArray = new Array(N + 1).fill(0);
    const one_idx = [];
    for (let j = 0; j < N; j++) {
      if (S[j] === "1") {
        cntArray[j + 1] = cntArray[j] + 1;
        one_idx.push(j);
      } else cntArray[j + 1] = cntArray[j];
    }

    // 1の個数と0の個数を取得するためのメソッド（可読性のため）
    const getValCount = (cntArray, idx, val) => {
      if (val === 1) return cntArray[idx];
      else return idx - cntArray[idx];
    };

    // 区間[l, r]の0の個数と区間(r, N)の1の個数の階差数列を取り出し、累積和として最小ヒープに入れる
    let cur = 0;
    pq.add([0, one_idx[0]]);
    for (let j = 0; j < one_idx.length - 1; j++) {
      let kaisa = getValCount(cntArray, one_idx[j + 1] + 1, 0) - getValCount(cntArray, one_idx[j] + 1, 0) - 1;
      pq.add([kaisa + cur, one_idx[j + 1]]);
      cur += kaisa;
    }

    // 求めるべきは、「区間[0, l)の1の個数 + 区間[l, r]の0の個数 + 区間(r, N)の1の個数」の最小値
    // ヒープに入れた階差の累積和の合計が最小であるようなrを選ぶことによって求めることができる
    let min = Infinity;
    for (let j = 0; j < one_idx.length; j++) {
      while (!pq.isEmpty() && pq.peek()[1] < one_idx[j]) pq.remove();
      if (pq.isEmpty()) break;

      const [val, idx] = pq.peek();
      let to_zero_cost = getValCount(cntArray, N, 1) - getValCount(cntArray, idx + 1, 1);
      let to_one_cost = getValCount(cntArray, idx + 1, 0) - getValCount(cntArray, one_idx[j] + 1, 0);
      min = Math.min(min, j + to_zero_cost + to_one_cost);
    }

    if (min === Infinity) min = 0;
    ans[i] = min;
  }
  console.log(ans.join("\n"));
}
// 以下、PriorityQueueクラスのため割愛
```


# まとめ
D問題ですが、言われてみれば簡単な`DP`だったので見抜けなくて残念です。
この解説通りの解法以外解けないなら結構難しいなと思っていたのですが、`DP`なら緑中位diffで妥当だなと思いました。
レートが結構下がってしまって苦しいです、、、笑