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

AtCoder Beginner Contest 390

ABCの3完（20分0ペナ）でした。
1085perfでレートは977->989（+12）となりました。
少し温まりましたが、DEどちらも解けなかったのでそれほど嬉しくはないです。
今回はA~C問題をまとめます。

A - 12435

公式解答は思いついたものの、考慮漏れが怖いので$O(N^2)$の転倒数を求めるコードを書きました。なぜ$O(N^2)$なのかというと、$O(NlogN)$の転倒数のライブラリがなかったのと、A問題でBITやセグ木を使う気になれなかったからです。
以下、ほぼネタ解説です。

まず有名な事実として、「配列を昇順にするために必要な、隣り合う2つの項を入れ替える操作回数」は転倒数と一致します。
転倒数とは、ざっくりいうと「昇順になっていない2つのペアの個数」のことです。（詳細はこちらの記事など参考にしてください）

つまり、この問題は「$A$の転倒数がちょうど$1$であるときYes、それ以外の時Noを出力せよ」と言い換えられます。今回は転倒数を求めるのにBITやセグ木を使わず、forループを使います。そのせいで$O(NlogN)$ではなく$O(N^2)$となりますが、$A$の要素数がたったの5のため問題ありません。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const A = input[0].split(" ").map(Number);
  // arr:= 番号1-5から見た転倒数を数えたかどうか、where:= 番号1-5が配列Aのどこにあるか
  const arr = Array(A.length).fill(false);
  const where = Array(A.length).fill(0);
  for (let i = 0; i < A.length; i++) where[A[i] - 1] = i;

  // ans:= 転倒数
  let ans = 0;
  for (let i = 0; i < A.length; i++) {
    arr[i] = true;
    // 配列Aの中のiより左にiより大きい数（arr[・]=false）があれば転倒数+1
    for (let j = 0; j < where[i]; j++) {
      if (!arr[A[j] - 1]) ans++;
    }
  }

  if (ans == 1) console.log("Yes");
  else console.log("No");
}

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

B - Geometric Sequence

問題に公比が必ず整数であるとは書いていないため、プログラミングでは丸め誤差の出うる小数となる場合を考慮して解答を作成する必要があります。
例えば、公比$r$を$r=A_2/A_1$のように割り算で求め、$r=A_{i}/A_{i-1}$が常に成り立つかどうかを確認するといったコードは次のようなケースで不正解となります（本番ではサンプルが弱くACとなるようですが、after contestでこれを撃墜するケースが追加されました）。

割り算誤差が生じる解答を撃墜するテストケースの例

N = 4
243 7857 254043 8214057
公比 97/3 = 32.3333333...（無限小数）

では小数を避けるための方策として、割り算を掛け算の形に変換する必要があります。
すなわち、等比数列が成り立つ時$i=1,2,...,N-2$について$A_{i+1}/A_{i}=A_{i+2}/A_{i+1}$が成り立ちますが、両辺の分母を払って$A_{i+1}^2=A_{i}A_{i+2}$となるかを確認すれば良いのです。

なお、$N=2$のときはこの式変形ができないのですが、落ち着いて考えるとこの場合は必ず等比数列であることがわかります。

また、この問題の制約を見ると$A_i≦10^{9}$のため、$A_{i}^2$が$10^{18}$近く大きくなる可能性があります。JavaScriptの場合$N=10^{14}$程度でNumber型はオーバーフローするため、BigIntに変換してから計算する必要があることがわかります（JavaScriptは基本的にNumber型を利用するので、面倒ですが常にオーバーフローの危険があるか気をつける必要があります）。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(BigInt);
  // N=2のときは比を定義できない、かつ必ず等比数列になるためYes
  if(N == 2) return console.log("Yes");
  // N>2のとき、連続する3項が常に等比数列になっているならばYes
  for (let i = 0; i < N - 2; i++) {
    if(A[i + 1] * A[i + 1] !== A[i] * A[i + 2]) return console.log("No");
  }
  console.log("Yes");
}

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

C - Paint to make a rectangle

この問題は、#を含む最小の長方形領域を把握して、その長方形領域内のマスがすべて#（最初から黒で塗られている）か、?（黒で塗り替え可能である）のいずれかであることを確認できればYesを出力し、逆に一つでも.（最初から白で塗られている）があればNoを出力します。

わからない場合は理屈よりも具体例を見て理解した方が早いです。

例1
.#?#.
.?#?. → 左上が(1,2)、右下が(2,4)の長方形領域に.がないためYes
?...?
最小の長方形領域内のマスに?があっても、それらの?を#に塗ることにすれば条件を満たします

例2
.#?#?
.?#?. → 左上が(1,2)、右下が(2,4)の長方形領域に.がないためYes
?....
最小の長方形領域外のマスが.や?に変わっても、それらの?を.に塗ることにすれば例1と同じです

例3
.#.#?
.?#?. → 左上が(1,2)、右下が(2,4)の長方形領域に.が「ある」ためNo
?....
最小の長方形領域内のマスに.があった場合、その時点で#を全て含む長方形がないことが確定します 

以上の理屈をコードで書くために、最小の長方形領域の四隅の座標を求めましょう。
$[\text{imin, imax, jmin, jmax}]:=$[最も上に位置する#は何行目か、最も下に位置する#は何行目か、最も左に位置する#は何列目か、最も右に位置する#は何列目か]と定義すると、最小の長方形領域の四隅は左上から時計回りに$(\text{imin, jmin})$、$(\text{imin, jmax})$、$(\text{imax, jmax})$、$(\text{imax, jmin})$と表すことができます。

あとは、二重ループでこの長方形領域内に.があるかどうかを確認すればよいため、全体で$O(N^2)$でこの問題を解くことができました。

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.push(input[i + 1].split(""));

  // imin:= 最も上に位置する#は何行目か imax:= 最も下に位置する#は何行目か
  // jmin:= 最も左に位置する#は何列目か jmax:= 最も右に位置する#は何列目か
  let [imin, jmin] = [1001, 1001];
  let [imax, jmax] = [-1, -1];
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
      if (S[i][j] === "#") {
        imin = Math.min(imin, i);
        jmin = Math.min(jmin, j);
        imax = Math.max(imax, i);
        jmax = Math.max(jmax, j);
      }
    }
  }
  
  // 最低でも左上[imin, jmin]、右下[imax, jmax]の長方形領域は最初から#か、#に塗り替え可能である必要がある
  for (let i = imin; i <= imax; i++) {
    for (let j = jmin; j <= jmax; j++) {
      // ?のときは#に塗り替え可能だが、.のときは塗り替え不可能
      if (S[i][j] === ".") return console.log("No");
    }
  }
  console.log("Yes");
}

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

D問題以降はまだ解けていないため解説を割愛します。本番はDをPythonで書いてTLEを取る方法が5分考えてわからなかったためE問題に行きましたが、どうしてもDPで解く方法がわからずタイムオーバーとなりました。4完して水パフォの某星人は結構すごいです。
あと、D問題はBigIntのxor演算が必要なため多分JavaScriptで3sec内に解くことは難しいです。（xor演算で最大桁が増えないことに着目して、分割統治法っぽく$10^9$以上と未満で分けてxorをNumberでやればできなくもないけど面倒臭いです）
今回は以上です。