【JavaScript】ABC384まとめ（A~E）

AtCoder Beginner Contest 384

ABCDの4完（92分0ペナ）でした。
763perfでレートは942->926（-16）となりました。
ABCEDの順に解きましたが、残り30分でEをあきらめ20分くらいでDを通したのでこんなもんです。
Eはぱっと見で解けると思ったのですが、計算の見積もりが甘く愚直を投げ続けてしまっていました。
早く本番で5完したいです！（まだしたことないので）
今回はA~Eをまとめます。

A - aaaadaa

最もシンプルな解法は、for文で1文字ずつ$c_1$であるか確認し、$c_1$であればそのままにしておき、$c_1$でなければ$c_2$に変更するだけです。
ただ、これで終わってしまうと面白くないので正規表現を利用した解法を紹介します。replace関数で$c_1$ではない文字を正規表現で取得し、$c_2$に置換するというやり方です。

ここで、通常であれば/^a/などで「a以外の文字」を検索することができるのですが、実はこのような正規表現リテラル記法では$c_1$のような動的に値が変わる変数を埋め込むことができません。

そこで、代わりにRegExpクラスを利用して、new RegExp(`[^${c1}]`, “g”)のように書くことで正規表現に変数を埋め込むことが可能となります。
次に、取得した正規表現オブジェクトをreplace関数によって別の変数に置換します。replace関数は正規表現に対応しているので、単純にreplace([置換したい正規表現オブジェクト], [置換後の文字列または変数])と書くだけで良いです。
以下、正規表現でACできたコードを示します。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, c1, c2] = input[0].split(" ");
  // RegExpは正規表現のコンストラクタで、リテラル記法とは異なり変数を受け取ることができる
  // `[^${c1}]`はc1以外の文字を表す。replase関数により、c1以外の文字をc2に置換する
  console.log(input[1].replace(new RegExp(`[^${c1}]`, "g"), c2));
}

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

B - ARC Division

一つずつコンテストを順番に受けて、レーティング変化適用範囲内のDivならば$A_i$だけレーティングを更新するシミュレーションを書くことでACすることができます。

実装の前準備として配列$\text{arr}$にDiv.1とDiv.2のレーティング更新下限・上限（下限は境界を含み、上限は境界を含まない）をメモしておきます。$\text{arr}$の1番目にDiv.1の範囲、2番目にDiv.2の範囲を記載しておくことで、インデックスを使って簡単にDivの判定が可能になります。

これでコンテストごとのレーティング変化適用範囲を動的に取得できるようになったので、あとはシミュレーション中に今のレートと比較し、適用範囲内であれば$A_i$だけレートを更新し、適用範囲外であれば更新しないという処理を書けば良いだけです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  let [N, R] = input[0].split(" ").map(Number);
  const [D, A] = [[], []];
  for (let i = 0; i < N; i++) [D[i], A[i]] = input[i + 1].split(" ").map(Number);
  // Divごとのレーティング変化適用範囲を表す
  // [1600, 2800]ならば、1600以上2800未満でレーティング変化が適用される
  const arr = [
    [1600, 2800],
    [1200, 2400],
  ];

  // コンテストを順番に受けて、レーティング変化適用範囲内であればレーティングを更新する
  for (let i = 0; i < N; i++) {
    let [l, r] = [arr[D[i] - 1][0], arr[D[i] - 1][1]];
    if (R >= l && R < r) R += A[i];
  }
  console.log(R);
}

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

C - Perfect Standings

解く問題の組み合わせは、各問題につき「解く」「解かない」の二通りしかないので、一つも問題を解けない場合を除いた$2^5-1=31$通りしかありません。この制約なら時間計算量は気にしなくて良さそうです。

「解く」「解かない」のように二通りの状態を表す場合、bit全探索を使うのが典型です。例えば、11001であれば右から見て1,4,5番目に1が立っているのでADE問題を解いていることとみなすことができます。bit列からどの問題を解いているのかがわかるようになれば、配列やmapを利用して得点や名前も復元できるようになります。これで、00001から11111までのbit列で、全ての組み合わせの得点と名前を網羅できるようになりました。（bit全探索は別記事でも解説してるので良ければご確認ください）

最後に、得点の降順（得点が同じ場合名前の昇順）に並び替える必要があります。JavaScriptの場合、標準のsort関数は安定ソート（同じキーを持つ要素の順序が、ソート後も維持される）のため、先に名前の昇順で並び替えした上で、得点の降順で並び替えすればこれを実装することができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  // score := A, B, C, D, E問題の配点。例えば、score[2]はC問題の配点を表す
  const score = input[0].split(" ").map(Number);

  let ans = [];
  // bit := 解いた問題の組み合わせを表す。bit = 11001ならば、右から見てA, D, E問題を解いたことを表す
  for (let bit = 1; bit < 1 << 5; bit++) {
    // sum := 解いた問題の合計得点, str := 解いた問題の組み合わせを表す文字列
    let sum = 0;
    let str = "";

    for (let i = 0; i < 5; i++) {
      // bitのi桁目が1ならば、i番目の問題を解いたことを表す
      if (bit & (1 << i)) {
        // 解いた問題は得点をsumに加算し、strに問題名を追加する。
        // 問題名は"A"の文字コードとの差分を使って求めるのが安全
        sum += score[i];
        str += String.fromCharCode("A".charCodeAt(0) + i);
      }
    }
    
    ans.push([sum, str]);
  }

  // 名前の昇順、得点の降順でソートして、順番に出力する
  // JSのsortは安定ソートなので、名前の昇順でソートした後に得点の降順でソートするとよい
  ans.sort((a, b) => (a[1] < b[1] ? -1 : 1));
  ans.sort((a, b) => b[0] - a[0]);
  for (let i = 0; i < ans.length; i++) console.log(ans[i][1]);
}

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

D - Repeated Sequence

累積和＋二分探索で解いたのでその解法を紹介します。
まず、無限数列$A$の連続部分列の和$S$は$A_i$を用いて以下のような一般式で表すことができます。
$$S =\sum_{i=n-l+1}^n A_i + k\sum_{i=1}^n A_i + \sum_{i=1}^r A_i, \quad 0 \leq l,r \leq n-1, \quad k \geq 0$$
第一項は右から$l$番目までの$A_i$の累積和、第二項は$A$を$k$回繰り返したときの総和、第三項は左から$r$番目までの$A_i$の累積和を表します。なお、$\sum$の上側が下側よりも小さい時は$0$として扱います。

具体例を示します。例えば、$N=3$、$A=[3,1,4,...]$のとき以下のような連続部分列がありえます。

第一項|第二項|第三項 の形式で連続部分列の具体例を示す

1,4|3,1,4,3,1,4|3,1　→繰り返し部分は何回あってもよい
4|3,1,4|　→第一項や第三項のいずれか、または両方が欠けていても良い
1,4||3　→第二項の繰り返し部分が欠けていても良い

ここで、繰り返し部分は$\sum_{i=1}^n A_i$の倍数のため$O(N)$で高速に求めることができることに着目します。すると、この問題を「$A$の右から何番目かまでの累積和（第一項）と$A$の左から何番目かまでの累積和（第三項）が、$S$から何回か繰り返し部分を取り除いた値と等しいか」という問題に帰着することができます。この問題は、二分探索で$O(NlogN)$で解くことができるため、累積和の構築も含めて全体として$O(N+NlogN)$となり十分に高速に解くことができます！

文字だとどうしてもわかりにくくなってしまうので具体例を示します。

S = 25 を満たす連続部分列は存在するか？

1,4|3,1,4,3,1,4|3,1　繰り返し部分を排除する
↓
1,4||3,1　繰り返し部分を2回取り除いたので、S=25-2×8=9と一致するかという問題に帰着した

左の累積和は5,右の累積和は4で、総和が9なのでSと一致する！

※実際の実装では、以下のように累積和で考える。
5,4||3,4
このように考えると、左の配列の要素と右の配列の要素の和がSになるような組み合わせは存在するか？
という非常に典型的な問題になる。

なお、一つだけ大きな落とし穴があり、繰り返し部分の除去は単純に$S$から$A_i$の総和の剰余を取るだけではNGな場合があります。例えば、1,4|3,1,4,3,1,4|3,1の場合に剰余を取ると$1$となりますが、左の累積和と右の累積和のどちらも$1$になりえないので答えは「存在しない」になります。しかし、これは先ほどの例を見ての通り偽です。

実は、繰り返し部分の除去の方法は 「単純に$S$から$A_i$の総和の剰余を取る」と、「$S$から$A_i$の総和の剰余を取ったものに一回だけ$A_i$の総和を足す」の二パターンがありえます 。これは繰り返しのない最大の連続部分列$A_2+\cdots+A_N+A_1+\cdots+A_{N-1}$は必ず$\sum_{i=1}^n A_i$を超えるから、という説明の方が少しわかりやすいかもしれません。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, S] = input[0].split(" ").map((x, i) => (i ? BigInt(x) : Number(x)));
  const A = input[1].split(" ").map(BigInt);
  let total = A.reduce((a, b) => a + b);

  // pre_sum := Aを左から見た累積和
  let pre_sum = new Array(N + 1).fill(0n);
  for (let i = 0; i < N; i++) pre_sum[i + 1] = pre_sum[i] + A[i];

  // rev_sum := Aを右から見た累積和
  let rev_sum = new Array(N + 1).fill(0n);
  for (let i = N; i > 0; i--) rev_sum[i - 1] = rev_sum[i] + A[i - 1];
  rev_sum.reverse();

  // rest := Aの繰り返し部分を排除した連続文字列の和
  let rest = [S % total, total + (S % total)];
  for (let i = 0; i < 2; i++) {
    for (let j = 0; j < pre_sum.length; j++) {
      // pre_sumを一つずつ順に見て、rev_sumの中に足すとrest[i]になるものがあるかを二分探索で探す
      // idx := rev_sumの中でrest[i] - pre_sum[j]以上の値が初めて現れるindex
      let idx = lower_bound(rev_sum, rest[i] - pre_sum[j]);
      if (idx == rev_sum.length) continue;
      if (rev_sum[idx] + pre_sum[j] == rest[i]) return console.log("Yes");
    }
  }
  // 全通り試しても見つからない場合はNoを出力
  console.log("No");
}
const isOK = (arr, mid, key) => arr[mid] >= key;
const lower_bound = (arr, key) => {
  let ng = -1;
  let ok = arr.length;

  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 - Takahashi is Slime 2

優先度付きキュー（最小ヒープ）でスライムの高橋くんに隣接するスライムを管理することにすれば、最弱のスライムは$O(logN)$で取得することができます。愚直に毎ターン隣接するスライムをすべて確認する場合$O(N)$なので、これはかなりの高速化になります。

最弱のスライムを吸収できない場合、当然ですが他のスライムも吸収できないので高橋くんは行動を終了します。なお、どの順番でスライムを吸収しても、高橋くんが行動できなくなった時点で高橋くんは強さの最大値を達成します。これは、一度吸収できるようになったスライムが後から吸収できなくなることはないためです。

1 6 8
9 2 ⑤　←　高橋くん（5ポイント）。X=2なので、5/2未満の隣接マスは吸収できる
6 3 1

↓

1 6 8
9 ② ⑤　←　高橋くん（7ポイント）。7/2未満の隣接マスは吸収できる
6 3 1

初期状態は5ポイントでX=2なので、左隣の2も下の1もどちらも吸収できる。
ここで先に2を吸収しようが、下の1が吸収できるのは変わらないため、吸収の順番はどうでもよい。

あとはこれを実装するだけですが、一つだけ注意点として割り算は誤差が出てしまうので掛け算に直す必要があります。最終的に全体計算量$O(NlogN)$でこの問題を解くことができました。

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

  let ans = 0n;
  let seen = new Array(H).fill(0).map(() => new Array(W).fill(false));
  // que := スライムを弱い順に取り出すための優先度付きキュー
  let que = new PriorityQueue((a, b) => a[2] - b[2]);
  // 現在の得点を引数に持つ深さ優先探索を行う関数
  const dfs = (cur) => {
    // 現在の得点が最大得点より大きい場合、最大得点を更新する
    if (cur > ans) ans = cur;
    
    // キューが空の場合や、隣接している最弱のスライムの強さが高橋くんの強さの1/X以上の場合は終了
    if (que.peek() === null) return;
    let [x, y, p] = que.peek();
    if (cur !== 0n && p * X >= cur) return;

    // 最弱のスライムを取り出し、隣接するスライムをキューに追加する
    que.remove();
    for (let j = 0; j < 4; j++) {
      let nx = x + dx[j];
      let ny = y + dy[j];
      if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
      if (seen[nx][ny]) continue;
      que.add([nx, ny, S[nx][ny]]);
      seen[nx][ny] = true;
    }

    // 現在の得点を更新して、再帰的に探索を行う
    dfs(cur + p);
  };

  // スタート地点をキューに追加して探索を開始する
  que.add([P - 1, Q - 1, S[P - 1][Q - 1]]);
  seen[P - 1][Q - 1] = true;
  dfs(0n);
  
  console.log(ans.toString());
}
// 以下、自前のPriority Queクラス。本記事では省略とする。

今回の記事はTTPC（東京工業大学プログラミングコンテスト2024）やServiceNowアドベントカレンダーの記事執筆、飲み会の日程が重なり投稿が遅くなってしまいました。TTPCはB問題に5時間かけてカタラン数に気づくところまではいきましたが、末尾に2が連続する場合の一般式が導出できず解けませんでした。結局自分は0完で味方（水色×2）に3完半してもらっていました(´•̥ ω •̥` )ただ、チーム戦でかつここまで長時間アルゴリズムを考えることはなかなかない経験なのでとても楽しむことができました！
次はもっと味方に貢献できるようになりたいです。