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

AtCoder Beginner Contest 378

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

A - Pairing

公式解説とは異なるアプローチを解説します。
単一色のボールが$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$を足し上げていくことで簡潔にこの問題を解くことができました。

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

公式別解の通りなので特に書くことがありませんが、例えば$[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$でこの問題が解けることが見えやすくなるのではないかと思います。

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

$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)$で行えるため、以上の操作を繰り返し行えば十分高速にこの問題を解くことができます。

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

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

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"));