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

AtCoder Beginner Contest 370

A~Cの3完（32分、2ペナ）でした。
605perfでレートは714->703（-11）です。
今回は標準の順序付き集合（C++のstd::set）が用意されていないJavaScripterにとって辛い回になったのではないでしょうか。
この記事ではA~Cの詳細とDの概要について簡単にまとめます。

A - Raise Both Hands

以下の通りに出力すればよいです。

L	R	出力
0	0	Invalid
0	1	No
1	0	Yes
1	1	Invalid

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [L, R] = input[0].split(" ").map(Number);
  if ((L && R) || (!L && !R)) console.log("Invalid");
  // よりスマートに書くなら: if (!L ^ R) console.log("Invalid");
  else if (L) console.log("Yes");
  else console.log("No");
}
Main(require("fs").readFileSync(0, "utf8"));

B - Binary Alchemy

$i≧j$を満たす元素$i$と元素$j$を合成させた場合、元素$A_{i,j}$が生成されると定義されているため、元素$1$を元素$1,2,...,N$の順に合成するシミュレーションをすることでこの問題は解けます。
ただし、$A_{i,j}$について$i≧j$である必要があるため、各イテレーションで大小関係の確認が必要な点だけ気をつけましょう。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = new Array(N);
  for (let i = 0; i < N; i++) A[i] = input[i + 1].split(" ").map(Number);
  let ans = 0;
  for (let i = 0; i < N; i++) {
    let max = Math.max(ans, i);
    let min = Math.min(ans, i);
    ans = A[max][min] - 1;
  }
  console.log(ans + 1);
}

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

C - Word Ladder

問題文がややこしいですが、以下のイメージで操作して$S$を$T$に一致するまで変化させます。

S	T	操作回数	X	次にSが変化する候補
adbe	bcbc	0	[ ]	[bdbe, acbe, adbc]
acbe	bcbc	1	[acbe]	[bcbe, acbc]
acbc	bcbc	2	[acbe, acbc]	[bcbc]
bcbc	bcbc	3	[acbe, acbc, bcbc]	[ ]

制約が$1≦|S|,|T|≦100$で、最大100回のイテレーションとなり、各イテレーションにつき次の$S$の変化先の候補が高々100通りしかないので、愚直にシミュレーションしても$O(|S|^2)$で解けます。
各イテレーションにおいて「次に$S$が変化する候補」を配列にpushして、毎回ソートして辞書順最小のものをフェッチするやり方でも$O(|S|^2log|S|)$なので問題ないのですが、JavaScriptの比較演算子 $<,>$ は文字列の辞書順の比較に利用できます。
したがって、以下のような書き方でこの問題はACできます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0].split("");
  const T = input[1].split("");
  const X = [];
  let str = S.join("");
  while (str !== T.join("")) {
    let res = "";
    for (let i = 0; i < S.length; i++) {
      if (str[i] !== T[i]) {
        let str2 = str.split("");
        str2[i] = T[i];
        str2 = str2.join("");
        if(!res || res > str2) res = str2;
      }
    }
    X.push(res);
    str = res;
  }
  console.log(X.length);
  if (X.length) console.log(X.join("\n"));
}

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

D - Cross Explosion

本問題の想定解は、C++のstd::setやstd::lower_boundを利用する解法ですが、残念ながらJavaScriptでは順序付き集合が標準ライブラリにないためかなり工夫する必要があります。
私が確認できたのは、以下の3つの解法です。

• セグメントツリー（Range Minimum TreeやRange Maximum Tree）
• Union-Find
• 赤黒木（std::setをJavaScriptで実装）

私はコンテスト後に他人の提出から赤黒木のライブラリを拝借し、無事にACできました（ありがとうございます！）。
丸パクリなのでここに書くのは自重しておきますが、興味がある方は私のAtCoderアカウントとD問題の提出を確認してみてください。
最近3完続きで、遅解きタイプなのでレートの伸びが鈍化どころか減っていますが、気にせず頑張っていきます。