【JavaScript】ABC405感想（A~E）

AtCoder Beginner Contest 405

こんにちは。
先日のABC405はプライベートな予定と重なり参加できなかったため、本日unratedでバーチャル参加しました。
結果、ABCDの4完（24分1ペナ）でした。predictorによると1036パフォだそうで（危ない…）
今回は「感想」バージョンの記事ということで解説要素の薄いゆるめの記事です。
A~Eまでの感想を述べていきます。

A - Is it rated?

$X$が1なのか2なのかによって場合分けして、参加可能なレーティング範囲であるかどうかを確かめるだけです。場合分けを書くのが地味に面倒でした。

B - Not All

解説通りにstackを利用して愚直に末尾から削除していき、都度$1〜M$の数字が全部存在するかどうかを見ても良いですが、別に左から数字を追加していって$1〜M$の数字が揃う寸前で止めても同じですよね。この手法ならどの数字が現在登場しているかをsetで管理できるようになるので、$O(N)$でこの問題を解くことができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  const A = input[1].split(" ").map(Number);
  const set = new Set();
  let ans = 0;
  for (let i = 0; i < N; i++) {
    set.add(A[i]);
    if (set.size == M) {
      ans = N - i;
      break;
    }
  }
  console.log(ans);
}

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

C - Sum of Product

累積和のチュートリアルにぴったりな問題ですね。既出じゃなかったんでしょうか。
適当に書いたらサンプルが通ったので出してみたら、数値上限のオーバーフローで1WAしたので、BigInt型に変えたらACしました。（悲しい）

D - Escape Route

Eからの多始点BFSでACしました。
矢印の方向は、訪れた向きとは逆になることに注意しなければなりません。
それ以外はやるだけなので特に書くことがありません。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [H, W] = input[0].split(" ").map(Number);
  const S = [];
  for (let i = 0; i < H; i++) S[i] = input[i + 1].split("");
  const di = [-1, 1, 0, 0];
  const dj = [0, 0, -1, 1];
  const dir = ["v", "^", ">", "<"];
  let escapes = [];
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (S[i][j] == "E") escapes.push([i, j]);
    }
  }

  const bfs = (startArr) => {
    const queue = new Set();
    const routeMap = new Array(H).fill(0).map(() => new Array(W).fill("#"));
    const visited = new Array(H).fill(0).map(() => new Array(W).fill(false));
    for (const start of startArr) {
      queue.add(start.join(","));
      routeMap[start[0]][start[1]] = "E";
      visited[start[0]][start[1]] = true;
    }
    for (const n of queue) {
      const [x, y] = n.split(",").map(Number);
      for (let i = 0; i < 4; i++) {
        const nx = x + di[i];
        const ny = y + dj[i];
        if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        if (S[nx][ny] == "#") continue;
        if (visited[nx][ny]) continue;
        visited[nx][ny] = true;
        routeMap[nx][ny] = dir[i];
        queue.add([nx, ny].join(","));
      }
    }
    return routeMap;
  };

  const routeMap = bfs(escapes);
  console.log(routeMap.map((row) => row.join("")).join("\n"));
}

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

E - Fruit Lineup

なんですか、これ。
これを2000人が解くのは人類頭良すぎませんかね。

問題を整理すると、

• A（＝リンゴ）もB（＝オレンジ）も両方全部置けていないとき、次はAとBが置ける
• Aを全部置いてBが全部置けていないとき、次はBとC（＝バナナ）が置ける
• Bを全部置いてAが全部置けていないとき、次はAしか置けない
• AもBも両方置けているとき、次はCとD（＝ブドウ）が置ける

のようにAとBの置いた状態で場合分けでき、combinationで数え上げできそうだというとっかかりはつかめました。

ここで、自前で作ったcombinationのライブラリが、in-placeに$N$の階乗を計算してすぐ捨てるという非効率極まりない作りになっているというトラブルが。
階乗を前計算して都度参照するというcombinationに書き直す必要があったのですが、さすがに時間的に厳しかったです。

まとめ

E問題はライブラリ未整備のためrated参加しても本番で解くことができていないでしょう。
出ていたらほぼ-10くらいレートが下がることが確定していたので、出られなかったのはむしろ幸運でした。
今日のABCはrated参加予定です。
出場される方は対戦よろしくお願いします。