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

AtCoder Beginner Contest 371

A~Eの5完（97分）でした。
1155perfでレートは703->758（+55）です。
この記事ではA~E問題についてまとめます。

A - Jiro

コンテスト中のACコードを少し改良した解法を記載します。
まず、$i={0,1,2}$をそれぞれ${A,B,C}$と対応させます。次に、他の兄弟と比較した結果年上であった回数を記録する$\text{win}=[0,0,0]$を用意します。
例えば、1つ目の比較$S_{AB}$が「<」であれば、$\text{win}=[0,1,0]$となり、「>」であれば$\text{win}=[1,0,0]$となります。
これを全ての比較に対して実行すると、本問では必ず年齢の異なる長男、次男、三男であることが保証されているため、$\text{win}$配列は必ず$0,1,2$をそれぞれ一つずつ持ちます。次男はこのうち$1$に対応するため、${A,B,C}$のうち$\text{win}=1$となる人を出力します。
なお、入力は$S_{AB}$, $S_{AC}$, $S_{BC}$の比較結果となっているため、あらかじめ連環の順$S_{AB}$, $S_{BC}$, $S_{CA}$として処理しやすくしておくとよいです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const s = input[0].split(" ");
  [s[1], s[2]] = [s[2], s[1]];
  s[2] == "<" ? (s[2] = ">") : (s[2] = "<");
  let win = new Array(3).fill(0);
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "<") {
      if (i < s.length - 1) win[i + 1]++;
      else win[0]++;
    } else win[i]++;
  }
  let map = new Map([
    [0, "A"],
    [1, "B"],
    [2, "C"],
  ]);
  for (let i = 0; i < s.length; i++) if (win[i] == 1) console.log(map.get(i));
}

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

B - Taro

$N$家で長男が生まれたかどうかを配列$\text{born}$で管理して、以下の分岐に沿って出力すればよいです。

条件	出力
$\text{born}[k]$== false かつ$k$家で男子が生まれた場合	Yes
otherwise	No

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  let A = [],
    B = [];
  for (let i = 0; i < M; i++) [A[i], B[i]] = input[i + 1].split(" ");
  A = A.map(Number);
  const born = new Array(N).fill(false);
  for (let i = 0; i < M; i++) {
    if (B[i] === "F" || born[A[i] - 1]) console.log("No");
    else {
      console.log("Yes");
      born[A[i] - 1] = true;
    }
  }
}

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

C - Make Isomorphic

まず、グラフ$H$の辺を足し引きして、頂点の番号も全く同じのグラフ$G$を再現することを考えましょう。
これは、$G$に存在して$H$に存在しない辺があれば$H$にその辺を足し、$G$に存在せず$H$に存在する辺があれば$H$からその辺を引けば良く、その辺の足し引きに対応する費用を合計すればよいだけです。

しかし、本問でのミソは頂点の番号を区別しなくて良いということです！！！例えば、グラフ2-1-3も3-2-1もすべて1-2-3と同じとみなすということであり、これが同型ということです。
頂点数が$N$個のとき同型のグラフは全部で$N!$個ありますが、今回の制約は$N≦8$のため問題なく間に合います。元のグラフ$H$を、グラフ$G$と同型の全てのグラフについて各費用を全探索で試し、その中の最小値を出力すればこの問題を解くことができます。

なお、下記コードのnextPermutationは標準ライブラリがないので自前のライブラリです。必要な方がいれば好きに使っていただいて構いません。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const Mg = Number(input[1]);
  const u = [],
    v = [];
  for (let i = 0; i < Mg; i++) [u[i], v[i]] = input[i + 2].split(" ").map(Number);
  const Mh = Number(input[Mg + 2]);
  const a = [],
    b = [];
  for (let i = 0; i < Mh; i++) [a[i], b[i]] = input[i + Mg + 3].split(" ").map(Number);
  const A = [];
  for (let i = 0; i < N; i++) A[i] = input[i + Mg + Mh + 3].split(" ").map(Number);
  let G = new Array(N + 1).fill(0).map(() => new Set());
  for (let i = 0; i < Mg; i++) G[u[i]].add(v[i]);
  let H = new Array(N + 1).fill(0).map(() => new Set());
  for (let i = 0; i < Mh; i++) H[a[i]].add(b[i]);
  const nodes = new Array(N).fill(0).map((_, i) => i + 1);
  const perms = generatePermutations(nodes);
  nodes.sort((a, b) => a - b);
  let ans = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i < perms.length; i++) {
    const perm = perms[i];
    let res = 0;
    for (let s = 0; s < N; s++) {
      for (let t = s + 1; t < N; t++) {
        let min = Math.min(perm[s], perm[t]);
        let max = Math.max(perm[s], perm[t]);
        if (G[s + 1].has(t + 1)) {
          if (H[min].has(max)) continue;
          res += A[min - 1][max - min - 1];
        } else {
          if (!H[min].has(max)) continue;
          res += A[min - 1][max - min - 1];
        }
      }
    }
    ans = Math.min(ans, res);
  }
  console.log(ans);
}
function nextPermutation(arr) {
  for (let i = arr.length - 2; i >= 0; i--) {
    if (arr[i] < arr[i + 1]) {
      for (let j = arr.length - 1; j > i; j--) {
        if (arr[j] > arr[i]) {
          [arr[i], arr[j]] = [arr[j], arr[i]];
          const len = (arr.length - (i + 1)) >> 1;
          for (let k = 0; k < len; k++) {
            [arr[i + 1 + k], arr[arr.length - 1 - k]] = [arr[arr.length - 1 - k], arr[i + 1 + k]];
          }
          return true;
        }
      }
    }
  }
  return false;
}
// 順列生成器。配列を配列として返すため、文字列が欲しい場合はjoin("")で結合する必要がある
// 配列用にスプレッド構文を使用しているが、遅いので文字列を出力する場合はjoin("")に書き換える
const generatePermutations = (arr) => {
  let sorted = arr.sort();
  const res = [[...sorted]];
  while (nextPermutation(sorted)) res.push([...sorted]);
  return res;
};

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

D - 1D Country

$N$個の村が一直線上に並んでおり、座標$L〜R$の範囲に存在する村の人口の総和を計算します。このクエリは$Q≦2×10^5$個あるため、各クエリをある程度高速に計算する必要があります。
まず、座標$L$以上で最も座標の小さい村はlowerboundを用いて$O(\text{log}N)$で取得できます。また、座標$R$以下で最も座標の小さい村もupperboundを用いて$O(\text{log}N)$で取得できます。
前者の村と、後者の村の一つ右にある村の番号をそれぞれ$l,r$とおくと、あらかじめ村$0〜i$までの人口の総和を累積和$\text{sum}[i+1]$で計算しておけば、$L〜R$の範囲内の人口は$\text{sum}[r]-\text{sum}[l]$として$O(1)$で計算できます。よって$O(Q\text{log}N)$でこの問題を解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const X = input[1].split(" ").map(Number);
  const P = input[2].split(" ").map(Number);
  const Q = Number(input[3]);
  const L = [],
    R = [];
  for (let i = 0; i < Q; i++) [L[i], R[i]] = input[i + 4].split(" ").map(Number);
  const sum = new Array(N + 1).fill(0);
  for (let i = 0; i < N; i++) sum[i + 1] = sum[i] + P[i];
  for (let i = 0; i < Q; i++) {
    let l = lower_bound(X, L[i]);
    let r = upper_bound(X, R[i]);
    console.log(sum[r] - sum[l]);
  }
}
const isOK = (arr, mid, key) => arr[mid] >= key;
const lower_bound = (arr, key) => {
  let ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
  let ok = arr.length; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

  while (ok - ng > 1) {
    let mid = Math.floor((ok + ng) / 2);
    if (isOK(arr, mid, key)) ok = mid;
    else ng = mid;
  }
  /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
  return ok;
};
const isOK2 = (arr, mid, key) => arr[mid] > key;
const upper_bound = (arr, key) => {
  let ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
  let ok = arr.length; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

  while (ok - ng > 1) {
    let mid = Math.floor((ok + ng) / 2);
    if (isOK2(arr, mid, key)) ok = mid;
    else ng = mid;
  }
  /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
  return ok;
};

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

E - I Hate Sigma Problems

この問題は配列を左から1つずつ見ていくDPで解くことができます。$\text{dp}[i+1]$を以下のように定義します。
$$\text{dp}[i+1]:=区間 [s \mid 0 \leq s \leq i, i]における種類数の総和$$
$\text{dp}[i]$までわかっているとして、$\text{dp}[i+1]$の値を高速に計算することを考えましょう。
まず、$\text{A}[i]$が最後に登場したタイミングを$\text{last}[\text{A}[i]]$として、区間 $[s \mid 0 \leq s \leq \text{last}[\text{A}[i]], i]$と区間 $[s \mid \text{last}[A[i]]+1 \leq s \leq i, i]$を分けて考えるとよいです。
前者については、$\text{A}[i]$が重複するため区間 $[s \mid 0 \leq s \leq \text{last}[A[i]], i-1]$と全く同じ値になります。一方で、後者については$\text{A}[i]$の重複がないため、区間 $[s \mid \text{last}[\text{A}[i]]+1 \leq s \leq i, i-1]$から$i-\text{last}[\text{A}[i]]$だけ純増していることがわかります。この差分を$delta$とおくと、区間全体としては$\text{dp}[i+1]=\text{dp}[i]+delta$となり、$\text{dp}[i+1]$を$O(1)$で求めることができました。
あとはこれを$N$まで行って総和を取れば題意をみたすので、結局$O(N)$でこの問題を解くことができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);

  const last = new Array(N + 1).fill(-1);
  const dp = new Array(N + 1).fill(0);

  dp[0] = 0;
  for (let i = 0; i < N; i++) {
    let delta = i - last[A[i]];
    dp[i + 1] = dp[i] + delta;
    last[A[i]] = i;
  }

  let ans = dp.reduce((acc, cur) => acc + cur, 0);
  console.log(ans);
}

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

次週は入緑記事を書けるようにがんばります！