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

AtCoder Beginner Contest 383

ABCDの4完（79分0ペナ）でした。
1144perfでレートは918->942（+24）となりました。
比較的難しい問題セットだったようで、遅解きにも関わらず高いパフォが出ました。
20分余ったのでE,Fを眺めていたのですが、問題文の意味すらよくわからず、、、
ということで、今回はA~Dをまとめます。

A - Humidifier 1

解法としては、「①1時間ごとに時計の針を進めて、水を追加する時刻になったら随時追加する」方針と、「②時刻と追加水量のセットを1つのイベントと捉え、時刻の早い順にイベントを処理する」方針の二つが思い浮かびやすいと思います。今回は$N$の制約がとても小さいので①の方針でも問題ありません。ただし、$N$が非常に大きい場合（$N>10^9$など）、①の方針だとループの回数が多すぎて間に合わなくなることがあります。そのような場合で、かつ水量追加の回数が十分に小さいとき（高々$10^6$回程度)、②の方針を使うことがあります。この問題においても、②の方針での解法を紹介します。

解法はシンプルで、時刻の早い順にイベントを処理します。ただし、入力の時点で時刻の早い順になっているため、時刻の昇順にソート（イベントソート）する必要はありません。各イベントでの処理内容は、「前回のイベントからの経過時間分（$T_i - T_{i-1}$）だけ水量を減らす」と「$V_i$だけ水量を追加する」です。なお、水量を減らす際に水量がマイナスにならないようにだけ注意してください。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const [T, V] = [[], []];
  for (let i = 0; i < N; i++) [T[i], V[i]] = input[i + 1].split(" ").map(Number);

  let ans = 0;
  // 時刻0のとき0リットル追加することにしておくと、ループで場合分けしなくて済む
  T.unshift(0);
  V.unshift(0);
  // 水量追加のイベントごとにループする
  for (let i = 1; i <= N; i++) {
    // 時刻の経過分水量を減らす。ただし、下限が0であることに注意。
    ans = Math.max(0, ans - (T[i] - T[i - 1]));
    ans += V[i];
  }
  console.log(ans);
}

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

B - Humidifier 2

加湿器が一つの場合を考えると、加湿器の座標$(i,j)$を$1 \leq i \leq H$と$1 \leq j \leq W$のもとで二重ループすれば置き場所の全列挙ができます。今回は加湿器が二つありますが、一つ目の加湿器のループ中に入れ子で二つ目の加湿器の座標$(k,l)$を同様に全探索することで、二つの加湿器の置き場所を全列挙することが可能です。ただし、加湿器は壁に置けないことと、両方同じ座標に置いてはいけないことに気を付ける必要があります。

加湿器を置き場所を決めたら、加湿器ごとに$x$座標の差と$y$座標の差の合計が$D$以内の床を加湿する処理を加えます。
まず、現在の加湿状況を表す$H×W$の$\text{table}$配列を用意しておきます。$\text{table}_{i,j}$がtrueのとき加湿されていて、falseのとき加湿されていないことを表します。
次に、座標$(x,y)$にある加湿器について、$x$座標の差と$y$座標の差の合計が$d$以内の床を加湿する関数$\text{humidify}(x,y,d)$を準備します。関数$\text{humidify}$の処理内容は、座標を左上から右下まで一つずつ順番に見ていき、$x$座標の差と$y$座標の差の合計が$d$以内かどうかの確認と、今いる座標が壁でないか、別の加湿器によってすでに加湿されていないかの確認をして、問題なければ加湿します。このように、共通的に利用できる関数を作成しておくと実装が楽になります。
あとは、二つの加湿器に対して$\text{humidify}$関数を利用して、最後に$\text{table}$配列でtrueがマークされた場所の個数を確認し、最大値をどんどん更新しておけばOKです。
計算量は、二つの加湿器の座標を列挙するパートで四重ループしているため$O((HW)^2)$と、 関数$\text{humidify}$の中でも二重ループが含まれているので全体としては$O((HW)^3)$となりますが、$0 < H,W \leq 10$と制約が小さいので十分間に合います。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [H, W, D] = input[0].split(" ").map(Number);
  const S = Array(H).fill(0);
  for (let i = 0; i < H; i++) S[i] = input[i + 1].split("");

  // 加湿器を(x,y)に置いた時、マンハッタン距離がd以内の場所を加湿する関数
  const humidify = (table, x, y, d) => {
    for (let i = 0; i < H; i++) {
      for (let j = 0; j < W; j++) {
        // 壁ではない、かつまだ加湿されていないことを確認する（後者はなくてもよい）
        if (S[i][j] === "#" || table[i][j]) continue;
        // マンハッタン距離がd以内であれば加湿する
        if (Math.abs(x - i) + Math.abs(y - j) <= d) table[i][j] = true;
      }
    }
    return;
  };

  let ans = 0;
  // 一つ目の加湿器の座標
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      // 二つ目の加湿器の座標
      for (let k = 0; k < H; k++) {
        for (let l = 0; l < W; l++) {
          const table = Array(H).fill(0).map(() => Array(W).fill(false));
          // 加湿器のどちらかが壁に置かれる場合はスキップ
          if (S[i][j] === "#" || S[k][l] === "#") continue;
          // 加湿器が同じ場所に置かれる場合はスキップ
          if (i === k && j === l) continue;
          // (i, j) と (k, l) に置かれた加湿器でマンハッタン距離がD以内の場所を加湿する
          humidify(table, i, j, D);
          humidify(table, k, l, D);
          // 加湿された場所の数の最大値を更新する
          ans = Math.max(ans, table.flat().filter((v) => v).length);
        }
      }
    }
  }
  console.log(ans);
}

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

C - Humidifier 3

bfs（幅優先探索）の少し応用的な問題です。
加湿器ごとに一個ずつbfsして範囲内のマスを加湿しようとしても、次のケースで正しい答えを得られません。

WA例（加湿したところを@で表す）

#H##
#.##
..H#
####
↓
#H##
#@##
.@H# <左に進めないよ〜(><)
####

H=W=4,D=2のとき、上の加湿器からbfsしてしまうと(2,2),(3,2)のマスが先に加湿されてしまう。
そのため、次に右下の加湿器でbfsしても(3,2)が加湿済みで通せんぼしているため(3,1)を加湿できない！
※加湿器の順序によっては上記のエラーを避けることができるが、サンプルが強いとWAとなるおそれがある

かといって、加湿されたマスを気にせずマンハッタン距離が$D$以内のマスをナイーブに数え上げようとしても、座標の個数が最大$H×W≦10^6$であり、それぞれ$D<10^6$マスも動くことができるので、全体で$O(HWD)$となり到底間に合いません。

ではどうするのかというと、多点bfsというテクニックを使います。
これは、最初に全ての加湿器の座標をキューに入れておいて、カウントダウンの要領で1マスずつ周囲に染み出していくイメージです。　上の例だと、以下のように進みます。

d=2（あと2マス進めるよ！）
#H##
#.##
..H#
####
↓
d=1（あと1マス進めるよ！）
#H##
#@##
.@H#
####
↓
d=0（0になったのでbfs終了！）
#H##
#@##
@@H#
####

Hと@の合計は5なので、答えは5！

bfs終了時の、加湿された@の個数と、元々加湿器があったHの個数の合計が加湿された座標の個数のため、これを出力すれば完了です。
この方法であれば一度探索した座標を二度探索しなくて済むため、全体計算量が$O(HW)$となり十分に間に合います。

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

  // 全ての加湿器の初期位置をキューにセットする
  const table = Array(H).fill(0).map(() => Array(W).fill(false));
  const q = [];
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (S[i][j] === "H") {
        q.push([i, j]);
        table[i][j] = true;
      }
    }
  }

  const bfs = (q) => {
    let d = D;
    // JavaScriptは先入先出が高速にできないため、二つの用途のキューを用意しておく必要がある
    // que := 保存用のキュー。次のループで取り出す。
    // cur := 取り出し用のキュー。前回のループで保存しておいたキューの要素を高速に取り出す。 
    let que = q;
    let nex = [];
    while(d > 0) {
      cur = [...que];
      que = [];
      while(cur.length > 0) {
        // shift()の計算量はO(N)のため、先入後出のpop()で代用せざるを得ない
        let [x, y] = cur.pop();
        for (let i = 0; i < 4; i++) {
          let nx = x + dx[i];
          let ny = y + dy[i];
          if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
          if (S[nx][ny] === "#" || table[nx][ny]) continue;
          table[nx][ny] = true;
          que.push([nx, ny]);
        }
      }
      d--;
    }
  };

  bfs(q);
  console.log(table.flat().filter((v) => v).length);
}

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

D - 9 Divisors

これについては公式解説がとても厚いため他に解説するところがありません。
JavaScriptのACコードと申し訳程度のコメントを書いて終了としておきます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  let cnt = 0;

  // エラトステネスの篩。誤差があるため適当に10を足しておいた（本当はダメ）。
  let max = Math.floor(Math.sqrt(N)) + 10;
  let isPrime = new Array(max + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i <= max; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= max; j += i) isPrime[j] = false;
    }
  }
  // isPrimeがtrue、つまり素数であるものをprimes配列に入れていく
  let primes = isPrime.map((val, idx) => (val ? idx : -1)).filter((val) => val >= 0);

  // x^8の形で表せるものを数え上げ
  for (let i = 0; i < primes.length; i++) {
    if (primes[i] ** 8 > N) break;
    cnt++;
  }

  // x^2 * y^2の形で表せるものを数え上げ
  for (let i = 0; i < primes.length; i++) {
    let x = primes[i] ** 2;
    for (let j = i + 1; j < primes.length; j++) {
      if (primes[j] === primes[i]) continue;
      let y = primes[j] ** 2;
      if (x * y > N) break;
      cnt++;
    }
  }
  console.log(cnt);
}

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

振り返ると、A,B問題が比較的重実装で、C,D問題は多点bfsや素因数列挙、約数の個数数え上げといったマイナー寄りの問題だったので、やはり普段より難しい問題セットだったのだと思います。早解き4完で1500perf近く取っている方もいるので、改めて早解きが自分の課題であると感じました。