【JavaScript】ABC393まとめ（A~F）

AtCoder Beginner Contest 393

https://atcoder.jp/contests/abc393

ABCDFの5完（68分0ペナ）でした。
1362perfでレートは1017->1057（+40）となりました。
E問題はGCDや約数列挙に苦手意識があり問題文を読んで1分で飛ばしF問題に取り組みました。
F問題はクエリの問題で、`セグ木`や`イベントソート`については自信があったので考えていった結果、以前鉄則本でやったことのある`二分探索でのLIS`をクエリ先読みした上でやるだけだと気づくことができ、なんと`AC`してしまいました。レート盛り盛りで嬉しいです。
というわけで今回はA~Fをまとめます。

# A - Poisonous Oyster
https://atcoder.jp/contests/abc393/tasks/abc393_a

以下の表に従って場合分けをして出力しましょう。

| $S1 \backslash S2$ |`sick` | `fine` |
|:-:|:-:|:-:|
| `sick`  | $1$  |  $2$ |
| `fine`  | $3$  | $4$  |

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const s = input[0].split(" ");
  if (s[0] === s[1] && s[0] == "sick") console.log("1");
  else if (s[0] === s[1] && s[0] == "fine") console.log("4");
  else if (s[0] === "sick") console.log("2");
  else if (s[1] === "sick") console.log("3");
}

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

# B - A..B..C
https://atcoder.jp/contests/abc393/tasks/abc393_b

`A`,`B`,`C`が等間隔に並んだ箇所のパターンは、**初項の位置**と**隣接項の距離**によって一意に決まります。これを全探索すると$O(|S|^2)$となりますが、本問題では$|S|≦100$であるため十分に間に合います。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0];
  let ans = 0;
  // Aの位置と、A-B, B-Cの間隔によって組み合わせは一意に決まる
  for (let i = 0; i < S.length; i++) {
    if (S[i] !== "A") continue;
    for (let len = 1; len <= S.length - i; len++) {
      if (S[i + len] == "B" && S[i + len * 2] == "C") ans++;
    }
  }
  console.log(ans);
}

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

# C - Make it Simple
https://atcoder.jp/contests/abc393/tasks/abc393_c

辺を最初から順番に見ていき、**同一の辺**または**自己ループ**を除いた辺の個数を調べましょう。
具体的には、`unordered_set`などを利用して、**自己ループではない互いに異なる辺のみ**を数えるようにします。
例えば、$[1,3]$という辺があったとすると、$[1,1]$（自己ループ）や$[3,1]$、$[1,3]$（同一の辺）は追加しないようにします。

その上で、最後に元々あった辺全体から、自己ループではないユニークな辺の個数を引くことにより、求められた答えが導出できました。

```js
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);

  let ans = new Set();
  for (let i = 0; i < M; i++) {
    [u[i], v[i]] = [u[i] - 1, v[i] - 1];
    if (u[i] > v[i]) [u[i], v[i]] = [v[i], u[i]];
    // 自己ループ、またはすでにカウント済みの辺は無効としてスキップ
    if (u[i] == v[i] || ans.has(`${u[i]} ${v[i]}`)) continue;
    ans.add(`${u[i]} ${v[i]}`);
  }

  // 辺全体から有効な辺の数を引く
  console.log(M - ans.size);
}

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

# D - Swap to Gather
https://atcoder.jp/contests/abc393/tasks/abc393_d

「マンハッタン距離の総和を最小化するときは中央値を利用する」方法、「`Slope Trick`というデータ構造を利用する」方法もありますが、本記事では累積和を利用した解法を説明します。

配列$lcost$を「今いる場所より**左の**`1`を全て、今いる場所に寄せた時のコスト」、配列$rcost$を「今いる場所より**右の**`1`を全て、今いる場所に寄せた時のコスト」のように定義します。
もしこの配列を定義できれば、あとは$lcost+rcost$が最小となる場所を探せば良いだけです。

|  | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $S$  | `0`  | `1`  |  `0` |  `1` | `0`  | `0`  | `1`  |
| $lcost$  | -  |  `0` |  - | `1`  |  - | -  | `5`  |
| $rcost$  | -  | `4`  |  - | `2`  |  - | -  | `0`  |
| $lcost+rcost$  | -  | `5`  |  - | `3`  |  - | -  | `5`  |

では、$lcost$と$rcost$の構築方法を考えましょう。
上の図をしっかりと観察してみましょう。
例えば、4→5に進んだ時、$S_2$と$S_4$の`1`はどちらも相対的に$1$ずつ遠くなるため、$lcost$は$2$だけ増加します。
ここで、**次に移動する位置の文字が`0`のとき、蓄積するコストはこれまで見て来た`1`の個数**だという予想が立ちます。証明は省略しますが、実際にこれに論理的な矛盾はなく、正しいことがわかります。

そして、**次に移動する位置の文字が`1`のとき、これまで見て来た`1`を動かすコストは変わりません。**
したがって、この場合は蓄積したコストを$lcost$に足すだけで問題ありません。

あとは、以上の考察を実装に落とし込むだけで良いのですが、累積コスト変数や両側から走査するのを正確に実装するのは少し厄介です。

左側から走査しても、右側から走査してもやることは基本的には変わらないので、このような場合は処理を共通化したメソッドを作るのが良いです。
`AC`コードの例では、第二変数に左側からの走査なのか、右側からの走査なのかを`bool`で受け取れるようにしています。添字管理に注意してください。

以上で、この問題を$O(N)$で解くことができました。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const S = input[1].split("").map(Number);
  // sum: 1の個数の累積和
  const sum = Array(N + 1).fill(0);
  for (let i = 0; i < N; i++) sum[i + 1] = sum[i] + (S[i] === 1 ? 1 : 0);

  // getCostArray: 1が書かれた点ごとに、そこに左の1を寄せた時のコストを求める。
  // 右側の1を寄せる場合は、rev = trueを指定すると取り出せるようにする
  const getCostArray = (S, rev) => {
    let new_S = rev ? [...S].reverse() : [...S];
    let res = [];
    for (let i = 0; i < N; i++) {
      if (new_S[i] === 1) {
        // 寄せるコストの差分更新。前回1があった場所からの距離 * 1の数のぶんだけ増加する
        let [prev_cost, prev_i] = res.at(-1) || [0, i - 1];
        let ones = rev ? sum[N] - sum[N - i] : sum[i];
        res.push([prev_cost + ones * (i - prev_i - 1), i]);
      }
    }
    // インデックスはコスト計算のみに用いるため、除去してコストだけを返す
    res = res.map((v, i) => v[0]);
    return rev ? res.reverse() : res;
  };

  // ある位置について、左側の1を寄せるコスト(lcost)と右側の1を寄せるコスト(rcost)の和の最小を求める
  let lcost = getCostArray(S, false);
  let rcost = getCostArray(S, true);
  console.log(Math.min(...lcost.map((v, i) => v + rcost[i])));
}

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

# E - GCD of Subset
https://atcoder.jp/contests/abc393/tasks/abc393_e

この問題は`約数ゼータ変換`という典型で処理することができます。

$f(d)$を「配列$A$の中で$d$を約数にもつ要素の個数」と定義します。
$\text{max}(A)$までの$f(d)$がわかっている場合、任意の$i$について **$f(d)≧K$を満たす、$A_i$の約数$d$のうち最大の値$F(A_i)$は簡単に求めることができます。**

![Group 6 (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3866035/9efc156b-b29f-43e7-aa78-d89689e7086b.png)

これだけでは何を言っているかわからないと思うので、上の図をみてください。
例えば、$K=2,A=[1,3,4,6]$とします。このとき、$f(1)=4,f(2)=2,f(3)=2,f(4)=1,f(6)=1$です。 ここで$4$番目の解$F(6)$について考えてみましょう。$6$の約数は$1,2,3,6$ですが、前述の$f(d)$の計算結果により、$f(d)≧2$を満たす最大の$6$の約数$d$は$3$であることがわかります。よって、$F(6)=3$です。
このように、$x$の全ての約数$d$についての基底関数$f(d)$を利用して、何らかの規則に従って累積関数$F(x)$を求める処理を`約数ゼータ変換`といいます。

これを、全ての$A_i$について行います。
愚直に約数全列挙で行うことができれば簡単なのですが、$N,K≦1.2×10^6$と大きいので高速化の方法を考えないとこの問題に正解することはできません。
（`C++`の場合は限界まで定数倍高速化することにより通るらしいのですが、`JavaScript`や`Python`だと厳しいと思います。）

したがって、「1. $f(d)$の導出」と「2. $F(x)$の導出」の2ステップに分けて、具体的な高速化手法を考えていきます。

### 1. f(d)の導出

まず最も愚直な方法として、$A_i$が与えられた時に都度試し割り法で約数を列挙する方法が考えられます。しかし、$M =\text{max}(A)$とすると、計算量は$O(N\sqrt{M})$となり、$N≦1.2×10^6$かつ$M≦10^6$より容易に`TLE`することが予想されます。

そこで、第二の方法としては`エラトステネスの篩`を利用する方法が考えられます。
| $d$ | 1 | 2 | 3 | 4 | 5 | 6 | $f(d)$ | $A$のうち$d$を約数にもつ要素 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 1  | ⚪︎  | ⚪︎  | ⚪︎  | ⚪︎  | ⚪︎  |  ⚪︎ | 4  | $1,3,4,6$  |
| 2  |   | ⚪︎  |   | ⚪︎  |   | ⚪︎  | 2  |  $4,6$ |
| 3  |   |   | ⚪︎  |   |   | ⚪︎  | 2  | $3,6$  |
| 4  |   |   |   | ⚪︎  |   |   | 1  | $4$  |
| 5  |   |   |   |   | ⚪︎  |   | 0  |   |
| 6  |   |   |   |   |   | ⚪︎  | 1  | $6$  |

上の具体例（$A=[1,3,4,6]$のケース）を見てください。$d=1,...,M$について、$d, 2d,3d,...,kd(k≦M/d)$と表せる要素がいくつあるかを調べています。
仮に$A$に重複があったとしても、事前に$N$回のループで、ある数$d$が何回現れたかを表す配列$\text{freq}[d]$が求められていれば、$f(d) = \sum_{k=1}^{\lfloor M/d \rfloor} \text{freq}[kd]$として$f(d)$を求めることができます。

各$d$のループ回数は$M/d$であるため、全体のループ回数は$M/1+M/2+…+M/M$であり、これは調和級数であるため計算量を$O(MlogM)$で上から抑えることができます。
以上で、$1$から$M$までの$f(d)$をくまなく高速に求めることができました。

### 2. F(x)の導出
$1$から$M$までの$d$について$f(d)$が求められたので、次に$N$行に渡り$F(A_i)$を高速に求めることを考えます。

任意の$A_i$が与えられた時に、即座に昇順ソートされた約数配列にアクセスできれば良いのですが、あいにく$f(d)$の導出時にそれを構築していないため叶いません。（ステップ1で$O(MlogM)$で約数全列挙しておくことは可能ではありますが、配列に要素を格納する処理が遅いので`TLE`する可能性が高いです。なお、`C++`のような高速な言語だとこれでも`AC`できるようです）

そこで、ここでも`エラトステネスの篩`を使って$d$の$1$から$M$まで順に$f(d)$を問い合わせ、$f(d)≧K$であれば$F(x)$を更新します。
これも図を見た方がわかりやすいでしょう。$K=2,A=[1,3,4,6]$のケースでは$F(6)$は以下のように遷移します。

| $d$ | 1 | 2 | 3 | 4 | 5 | 6 | $f(d)$ | $F(6)$ |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 1  | ⚪︎  | ⚪︎  | ⚪︎  | ⚪︎  | ⚪︎  |  ⚪︎ | 4  | 1  |
| 2  |   | ⚪︎  |   | ⚪︎  |   | ⚪︎  | 2  |  2 |
| 3  |   |   | ⚪︎  |   |   | ⚪︎  | 2  | 3  |
| 4  |   |   |   | ⚪︎  |   |   | 1  | 3  |
| 5  |   |   |   |   | ⚪︎  |   | 0  | 3  |
| 6  |   |   |   |   |   | ⚪︎  | 1  | 3  |

- $d=1$について、$6d=6$かつ$f(1)=4≧2$より、$F(6)=1$
- $d=2$について、$3d=6$かつ$f(2)=2≧2$より、$F(6)=2$
- $d=3$について、$2d=6$かつ$f(3)=2≧2$より、$F(6)=3$
- $d=4,5$については$kd=6$となるような整数$k$が存在しないのでスキップ
- $d=6$について、$1d=6$であるが、$f(6)=1<2$のためスキップ

以上より、$F(6)=3$であるとわかりました。
このようにすることで、$1$から$M$までの任意の$x$について、**$F(x)$を$O(MlogM)$で求めることができます**。

<br>

$1$から$M$までの任意の$x$について、$F(x)$がわかったので、あとは$N$行にわたって$F(A_i)$を出力すれば良いのですが、実はここにも大きな落とし穴があり、$N$が非常に大きいため、$N$回`console.log`をしてしまうと標準入出力のI/O操作がボトルネックとなり、なんとそれまでのアルゴリズムが正しくても`TLE`していまいます。
これを回避するためには、解答を配列に格納し`console(ans.join(“\n”))`のように`join`関数で文字列結合するなどして`console.log`の回数を$1$回に抑える必要があります。

ここまで非常に長い道のりでしたが、以上で全体計算量が$O(MlogM+N)$となり、この制約下で十分高速にこの問題を解くことができました。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, K] = input[0].split(" ").map(Number);
  const A = input[1].split(" ").map(Number);
  const max = Math.max(...A) + 1;

  // freq[i]:= iの出現頻度
  const freq = new Array(max).fill(0);
  for (let i = 0; i < N; i++) freq[A[i]]++;

  // f[i]:= 配列Aのうち、iを約数に持つ数の個数を表す基底関数
  const f = new Array(max).fill(0);
  for (let i = 1; i < max; i++) {
    for (let j = i; j < max; j += i) f[i] += freq[j];
  }

  // g[i]:= f[j]≧Kを満たす、iの約数jのうち最大のものを表す累積関数
  const g = Array(max).fill(1);
  for (let i = 2; i < max; i++) {
    if (f[i] < K) continue;
    for (let j = i; j < max; j += i) g[j] = i;
  }

  // N行console.logするとN回I/O操作が発生するため非常に遅くなるので注意
  const ans = [];
  for (let i = 0; i < N; i++) ans.push(g[A[i]]);
  console.log(ans.join("\n"));
}


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

余談ですが、これは本当に1200 diffなのでしょうか？数学的にも、実装的にも難しいポイントがかなり多いと感じました。
問題としては、`約数ゼータ変換`を納得いくまで理解することができたので、非常に素晴らしい問題だと思いました。
この典型を使えば、$M$を上限とする任意の整数$n$について、色々な[約数関数](https://mathlandscape.com/divisor-func/)$\sigma_k(n)$を$O(MlogM)$で評価できます。興味がある方は、約数の二乗の和や、逆数和などを自分で計算してみると面白いかもしれません。


# F - Prefix LIS Query
https://atcoder.jp/contests/abc393/tasks/abc393_f

F問題は`LIS`を知っているか知らないかで難易度が大きく変わってくるため、`LIS`を知らない人はまず`LIS`を学習してください。[参考](https://qiita.com/drken/items/68b8503ad4ffb469624c#3-lis-%E3%81%AE%E8%A7%A3%E6%B3%951-%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2-ver)

最初に種明かしをすると、クエリ先読みをすることによって、$R$の小さい順にイベントソートして、$R_1≦R_2≦…≦R_Q$のような順番にクエリを入れ替えておきます。
このようにすると、$1$から$R_i$までのプレフィックスで`LIS`を構築した後に、構築した`LIS`を$1$から$R_{i+1}$までの`LIS`を求める際に使いまわすことができるようになります。

`LIS`の構築方法は、私は`二分探索`で構築しましたが、多分`セグ木`でも構わないと思います。
以上で、$O((N+Q)logN)$でこの問題を解くことができました。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, Q] = input[0].split(" ").map(Number);
  const A = input[1].split(" ").map(Number);
  const [R, X] = [[], []];
  const query = [];
  for (let i = 0; i < Q; i++) {
    [R[i], X[i]] = input[i + 2].split(" ").map(Number);
    query.push([R[i], X[i], i]);
  }
  // クエリをRでソートしておくことで、Rを進めながら都度都度クエリに答えることができるようにする
  query.sort((a, b) => a[0] - b[0]);
  const ans = Array(Q).fill(0);

  // L[i]:= 長さi+1の増加部分列の最後の要素の最小値
  const L = [];
  let pos = 0;
  for (let i = 0; i < N; i++) {
    // Lが空の場合は、A[i]が長さ1の増加部分列の最後の要素となるのでそのまま追加
    if (L.length === 0) L.push(A[i]);
    else {
      // A[i]の挿入（置換）位置を二分探索で求める
      let pos = lower_bound(L, A[i]);
      if (pos === L.length) L.push(A[i]);
      else L[pos] = A[i];
    }

    // 次のRまで、尺取法の要領でクエリを進め、都度都度クエリに答える
    while (pos < Q && query[pos][0] <= i + 1) {
      const [r, x, idx] = query[pos];
      let res = lower_bound(L, x + 1);
      ans[idx] = res;
      pos++;
    }
  }
  console.log(ans.join("\n"));
}
const isOK = (arr, mid, key) => arr[mid] >= key;
const lower_bound = (arr, key) => {
  let ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
  let ok = arr.length; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

  while (ok - ng > 1) {
    let mid = Math.floor((ok + ng) / 2);
    if (isOK(arr, mid, key)) ok = mid;
    else ng = mid;
  }
  return ok;
};
Main(require("fs").readFileSync(0, "utf8"));
```

記事執筆までかなり時間が空いてしまいすみません。
E問題が難しすぎて、約数まわりやゼータ・メビウス変換の内容理解、ライブラリ整理を納得いくまで行っていました。

さて、レートの方は躍進中で、もしかしたら5月くらいには入水できるかもしれない程度の期待感が持てるようになりました。
引き続き、コンテストの参加と記事の執筆を頑張ってまいりますので、皆様も是非一緒に頑張りましょう。
![スクリーンショット 2025-02-21 0.06.29.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3866035/8d5fbcf4-12de-4c87-9e90-b9649f26bad2.png)