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

AtCoder Beginner Contest 378

https://atcoder.jp/contests/abc378

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

# A - Pairing
https://atcoder.jp/contests/abc378/tasks/abc378_a

公式解説とは異なるアプローチを解説します。
単一色のボールが$N$個あった場合、一般に$\lfloor N/2 \rfloor$（小数切り捨て）回まで同じ色のボールを選び両方捨てるという操作ができます。例えば、$N = 5$のとき$2$回操作することができます。
この操作は異なる色のボールがあっても互いに影響されませんので、$N$色のボールが $\text{fre}[1],\text{fre}[2],...,\text{fre}[N]$個ずつあった場合、色ごとに一つずつ見ていけばよいです。
したがって、あらかじめ各色の出現回数を$\text{fre}$配列に格納しておき、$\lfloor \text{fre}[i]/2 \rfloor$を足し上げていくことで簡潔にこの問題を解くことができました。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const A = input[0].split(" ").map(Number);
  const fre = new Array(5).fill(0);
  for (let i = 0; i < 5; i++) fre[A[i]]++;
  let ans = 0;
  for (let i = 0; i < 5; i++) ans += Math.floor(fre[i] / 2);
  console.log(ans);
}

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

# B - Garbage Collection
https://atcoder.jp/contests/abc378/tasks/abc378_b

[公式別解](https://atcoder.jp/contests/abc378/editorial/11303)の通りなので特に書くことがありませんが、例えば$[q, r]=[7, 3]$のとき、
- $0-3$日目は$3$
- $4-10$日目は$10$
- $11-17$日目は$17$
...

というように、どうやら$q=7$日周期で質問への回答が$q$ずつ増加するということに着目すれば、$\left\lceil (d[i] - r)/q \right\rceil \cdot q + r$でこの問題が解けることが見えやすくなるのではないかと思います。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const q = [],
    r = [];
  for (let i = 0; i < N; i++) [q[i], r[i]] = input[i + 1].split(" ").map(Number);
  const Q = Number(input[N + 1]);
  const t = [],
    d = [];
  for (let i = 0; i < Q; i++) [t[i], d[i]] = input[i + N + 2].split(" ").map(Number);
  const map = new Map();
  for (let i = 0; i < N; i++) map.set(i + 1, [q[i], r[i]]);

  for (let i = 0; i < Q; i++) {
    let [q, r] = map.get(t[i]);
    console.log(Math.ceil((d[i] - r) / q) * q + r);
  }
}

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

# C - Repeating
https://atcoder.jp/contests/abc378/tasks/abc378_c

$N$が非常に大きいので、各$i$について$\text B[i]$の探索を$O(1)$で済ます必要があります。
また、$\text A[i]≦10^9$なので、普通に$10^9$個の配列を作っていてはメモリや時間の制約が厳しいです。ただし、入力が$N≦2×10^5$個しかないため、登場する$N$個の配列だけ用意すれば十分です。
結論から言うと、このような問題は **連想配列（ハッシュマップ）** で高速に解けます。
$i=0,1,...,N-1$のとき、$\text A[i]$を左から順に見ていって、
- キー：$\text A[i]$の値が空の時、`-1`を出力して、キー：$\text A[i]$に`i+1`を登録する
- キー：$\text A[i]$の値があればそれを出力して、キー：$\text A[i]$に`i+1`を登録する

値の取得と登録はそれぞれ$O(1)$で行えるため、以上の操作を繰り返し行えば十分高速にこの問題を解くことができます。


```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 map = new Map();

  let ans =[];
  for (let i = 0; i < N; i++) {
    ans.push(map.get(A[i]) || -1);
    map.set(A[i], i + 1);
  }
  console.log(ans.join(" "));
}

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


# D - Count Simple Paths
https://atcoder.jp/contests/abc378/tasks/abc378_d

[公式解説](https://atcoder.jp/contests/abc378/editorial/11288)の通り、実はこの問題は`DFS全探索`で十分間に合わせることができます。
経路の条件は「同じ頂点を二度通ってはいけない」なので、一度訪れた頂点を$\text {visited}$配列にでも格納しておき、一度訪れた頂点を再度通らないような経路を$HW$通りのスタート地点について`DFS`で求めていきます。
また、$K$回の移動を検出するために移動回数$cnt$変数と現在地点$i,j$を引数に持つ`再帰DFS`での実装が簡潔です。終了条件$cnt =K$を満たしたとき、$ans$に$+1$することでこの問題を解くことができます。

```js
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [H, W, K] = input[0].split(" ").map(Number);
  const S = [];
  for (let i = 0; i < H; i++) S.push(input[i + 1].split(""));
  let dx = [-1, 0, 1, 0];
  let dy = [0, -1, 0, 1];

  let visited = new Array(H).fill().map(() => new Array(W).fill(false));
  let ans = 0;
  const dfs = (i, j, cnt) => {
    if(cnt === K) return ans++;

    visited[i][j] = true;
    for(let k = 0; k < 4; k++) {
      let x = i + dx[k];
      let y = j + dy[k];
      if(x < 0 || x >= H || y < 0 || y >= W || visited[x][y]) continue;
      if(S[x][y] === "#") continue;
      dfs(x, y, cnt + 1);
    }
    visited[i][j] = false;
  }

  for(let i = 0; i < H; i++) {
    for(let j = 0; j < W; j++) {
      if(S[i][j] === "#") continue;
      dfs(i, j, 0);
    }
  }

  console.log(ans);
}

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