【JavaScript】ABC385まとめ（A~C）

AtCoder Beginner Contest 385

ABCの3完（17分0ペナ）でした。
1042perfでレートは926->938（+12）となりました。
CをACした時点で順位表を見るとac-predictorが青perfを示しており勝ちを確信しましたが、D問題はまさかのJavaScriptの標準メソッドにないsortedsetの問題が来てしまい、持っていた自前のmultisetライブラリで必死の抵抗をしましたがあえなく敗退しました。（sortedsetやmultisetの問題は、JavaScriptではライブラリを配布してる人もおらず自分で準備する必要があるため、JavaScript勢にとっては本気で2色くらい上だと思っています）
Dは結局C++でコンテスト後にupsolveしましたが本記事ではJavaScriptのみに絞るため、今回はA~Cをまとめます。

A - Equally

二つ以上のグループに分ける方法は、([A], [B], [C])、([A, B], [C])、([B, C], [A])、([C, A], [B])の4通りしかないため、if文で全通りについて条件を満たすかどうか調べましょう。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [A, B, C] = input[0].split(" ").map(Number);
  // 三つのグループに分ける場合、[A], [B], [C]の分け方しかない
  if(A === B && B === C) return console.log("Yes");
  // 二つのグループに分ける場合、[A, B], [C]と[B, C], [A]と[C, A], [B]の分け方がある
  if(A + B === C || B + C === A || C + A === B) return console.log("Yes");

  console.log("No");
}

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

B - Santa Claus 1

問題文の通りにシミュレーションして、サンタの通ったマスを$\text{seen}$配列にメモしておきます。
サンタが行動を終えた後にすべてのマスを全探索し、seen[i][j] == trueかつs[i][j]=="@"のとき、「サンタが訪れた家」であるため一つカウントします。
最後に、サンタの最終的な座標とカウントの合計値を出力することで、この問題に正解することができます。

実装上の注意点としては、まず$(i,j)$は$i$行$j$列のマスを表すため、サンタが上に行く場合$(i-1,j)$、下に行く場合$(i+1,j)$、右に行く場合$(i,j+1)$、左に行く場合$(i,j-1)$となるため紛らわしいですが気をつけてください。また、移動先が#で壁の時や、グリッドの範囲外となる場合はその場にとどまることにも注意が必要です。

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

  // mapのvalueには移動方向を表す数値を格納する
  // 例えば、map.get("L")で0を取得したとき、di[0] = 0, dj[0] = -1となり、左に移動することを表す
  const di = [0, 0, -1, 1];
  const dj = [-1, 1, 0, 0];
  const map = new Map([["L", 0], ["R", 1], ["U", 2], ["D", 3]]);
  const seen = new Array(H).fill(0).map(() => new Array(W).fill(false));

  let cur = [R - 1, C - 1];
  seen[cur[0]][cur[1]] = true;
  for (let i = 0; i < t.length; i++) {
    // dir := 移動方向を表す
    const dir = map.get(t[i]);
    let ni = cur[0] + di[dir];
    let nj = cur[1] + dj[dir];
    // 移動先が壁か、範囲外の場合はその場にとどまる
    if (ni < 0 || ni >= H || nj < 0 || nj >= W || s[ni][nj] === "#") continue;
    cur = [ni, nj];
    seen[ni][nj] = true;
  }

  let ans = 0;
  // seen[i][j]がtrueかつs[i][j]が"@"である場合、一度訪れた家であることを表す
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (seen[i][j] && s[i][j] === "@") ans++;
    }
  }
  console.log(cur[0] + 1, cur[1] + 1, ans);
}

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

C - Illuminate Buildings

この問題について、私は今のところ三通りの解法を発見しています。

1. 調和級数の性質を利用した方法。$O(N^2logN$）
2. ランレングス圧縮を利用した方法。$O(N^2)$
3. 二次元DPを利用した方法。$O(N^2)$

コンテスト中は一つ目の解法で解いたのでこれを解説します。また、二つ目と三つ目のACコードも記載しておきます。

解法1 - 調和級数（166ms）

まず考え方から説明します。
最初に左から順に全探索して、左端となるビルを固定します。次に、二つ目となるビルを再度左から順に全探索します。このビルの選び方は左端のビルと同じ高さならなんでもいいです。

ここまでの手順で、「ビルの高さ」と「ビルの間隔」が一意に固定されました。左端のビルの位置を$i$、二つ目のビルの位置を$j$とすると、「ビルの高さ」は$H_i$、「ビルの間隔」は$j-i$です。

これらの情報が決まったら、あとはその間隔でビルの列を伸ばして行って、どこまで同じ高さのビルが存在するか？というのを求めてやるだけです。図にすると以下の通りです。

ビルの高さ　3 … 6 … 6 …
番号　　　　1 … i … j …

i番目のビルを左端、j番目のビルを二番目に固定する。
ビルの高さは6、間隔はj-iなので、次のj+(j-i)番目のビルの高さが6なら答えを3に更新する。
このように間隔ごとに次のビルを調べる操作を、同じ高さのビルが続くまで永遠に続ける。

この解法の最悪計算量のケースは、下図のように同じ高さのビルが連続する場合です。

ビルの高さ　1 1 … 1（1がN個連続する）
番号　　　　1 2 … N

この場合の計算量の見積もりは以下のようになります。

• 左端を固定して全探索するのに$O(N)$
• 二つ目のビルを探索するのに$O(N)$
• 三つ目以降のビルを探索するのに$O(logN)$

三重ループになっているので一見$O(N^3)$なのですが、三回目のループにおいて各要素に着目すると$1/1 + 1/2 + … + 1/N$回アクセスされるため、調和級数の和の計算量が$O(logN)$となることを利用することにより、全体としては$O(N^2logN)$となります。この問題は$N<=3000$と制約が小さいため十分に間に合います。

以下、余談。少し高度な話となります。

各要素のアクセス回数の合計が$1/1 + 1/2 + … + 1/N$であることの理由は、エラストテネスの篩をイメージするとわかりやすいです。

素数$p$だけで$N$以下の$p$の倍数の消し込みを行なっていく篩は$O(NloglogN)$ですが、素数ではない数を含めた合成数$z$の倍数での篩は$O(NlogN)$です。この篩において、任意の$N$が消し込みをされる回数の期待値は$1/1+1/2+…+1/N$回である故に、計算量を$O(NlogN)$で表すことができます。

この消し込みをアクセス回数と捉えると、この問題でも同様の議論ができます。

調和級数が$O(logN)$で抑えられるという事実は競プロでたまに出てくるので覚えておくと良いです。私は、$1/N$の原始関数が$logN$であるということに紐づけて覚えています。

参考記事 - エラトステネスの篩の活用法を総特集！ 〜 高速素因数分解・メビウスの反転公式 〜
参考記事 - 調和級数が log(n) で押さえられることの証明

// 調和級数の計算量がlogNで抑えられることを利用した解法。O(N^2logN)
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const H = input[1].split(" ").map(Number);

  let ans = 1;
  // 左端となるビルを全探索。O(N)
  for (let i = 0; i < N; i++) {
    // 高さが左端と同じ、二つ目のビルを全探索。O(N)
    for (let j = i + 1; j < N; j++) {
      if (H[i] !== H[j]) continue;
      // d := 隣り合うビルの間隔、k := 三つ目以降のビルの位置
      let d = j - i;
      let k = j + d;
      let cnt = 2;
      // 三つ目以降のビルは間隔dおきに確認する。調和級数なので、O(logN)
      while (H[i] === H[k] && k < N) {
        cnt++;
        k += d;
      }

      ans = Math.max(ans, cnt);
    }
  }
  console.log(ans);
}

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

解法2 - ランレングス圧縮（117ms）

これは公式解説の通りです。
まずビル同士の間隔$d$を決め打つと、

• $1$,$1+d$,$1+2d$,...
• $2$,$2+d$,$2+2d$,...
  ...
• $d-1$,$d-1+d$,$d-1+2d$,...

の$d-1$個のグループに分けることができます。
あとは各グループに対しランレングス圧縮をして最大のランレングスを求めれば良いだけです。
全体として、計算量は$O(N×d×(N/d))=O(N^2)$となります。

// 公式解説通りにランレングス圧縮を使う解法。O(N^2)
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const H = input[1].split(" ").map(Number);

  let ans = 1;
  // 隣り合うビルの間隔を決め打つ。1からN-1まであるのでO(N)
  for (let d = 1; d < N; d++) {
    // 間隔はdのため、左端は0からd-1までだけ調べれば十分。O(d)
    for (let j = 0; j < d; j++) {
      // cur := 現在のビルの位置、cnt := 現在更新中のランレングス、res := 現在の最大ランレングス
      let [cur, cnt, res] = [j, 0, 0];

      // 間隔dおきにランレングス圧縮の要領で同じ高さのビルの最大を調べる。O(N/d)
      while (cur + d < N) {
        if (H[cur] === H[cur + d]) cnt++;
        else cnt = 0;

        // 現在の最大ランレングスを更新
        if (cnt > res) res = cnt;
        cur += d;
      }

      ans = Math.max(ans, res + 1);
    }
  }
  console.log(ans);
}

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

解法3 - 二次元DP（206ms）

DPでも解くことができます。
$dp_{i,j}:=i番目のビルまで見たとき、間隔jで同じ高さのビルが何個続いているか$
とすれば、$(i+j,j)$のビルを調べ、同じ高さなら$+1$、異なれば$0$にすることで、$dp_{i + j,j}$を順次求めていくことができます。
なお、dpの構築で$O(N^2)$、遷移でも$O(N^2)$かかっているので他の解法よりは少しだけ遅くなると思います。

// 二次元dp解法。O(N^2)
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const H = input[1].split(" ").map(Number);
  // dp[i][j] := i番目のビルまで見たとき、間隔jで同じ高さのビルが何個続いているか
  const dp = new Array(N + 1).fill(0).map(() => new Array(N + 1).fill(0));

  let ans = 1;
  for (let i = 0; i < N; i++) {
    for (let j = 1; j <= N - i; j++) {
      // 渡すDPの要領で、jだけ先のビルと高さが同じか確認して同じなら+1
      if (H[i] === H[i + j]) dp[i + j][j] = dp[i][j] + 1;
      // 違う場合は0で初期化
      else dp[i + j][j] = 0;
      ans = Math.max(ans, dp[i + j][j] + 1);
    }
  }

  console.log(ans);
}

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

Cまで爆速で解くことができましたが、D問題は言語の特性上厳しかったです。
この競技で上を目指すならC++の習得は必須かもしれません。実はこっそりとpythonの学習もしているので当分は時間的に難しいとは思いますが、、、