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

AtCoder Beginner Contest 392

ABCDの4完（31分0ペナ）でした。
1037perfでレートは1015->1017（+2）となりました。
E問題は、コンテスト後にDequeのライブラリを準備したらすんなり実装できました。
というわけで今回はA~Dをまとめます。

A - Shuffled Equation

$B_1×B_2=B_3$を満たす正整数の配列$B$については、$B_1≦B_2≦B_3$または$B_2≦B_1≦B_3$が成り立ちます。なお、正整数同士の掛け算には交換法則が成り立つので、$B_1≦B_2≦B_3$とみなしてよいです。
したがって、与えられた$A$をソートした上で$A_1×A_2=A_3$かどうかを確かめることでこの問題を解くことができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const A = input[0].split(" ").map(Number);
  A.sort((a, b) => a - b);
  if (A[0] * A[1] === A[2]) console.log("Yes");
  else console.log("No");
}

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

B - Who is Missing?

$N≦1000$なので、$O(N^2)$の愚直解法が間に合います。
私は練習のため尺取法でこの問題を解きました。
これはソートがボトルネックとなり、$O(MlogM+N)$で解くことができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  const A = input[1].split(" ").map(Number);
  A.sort((a, b) => a - b);
  let ans = [];

  // 尺取り法で効率的に解答の配列を作成する
  let pointer = 0;
  for (let i = 0; i < N; i++) {
    while (pointer < M && A[pointer] < i + 1) pointer++;
    if (A[pointer] !== i + 1) ans.push(i + 1);
  }
  console.log(ans.length);
  console.log(ans.join(" "));
}

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

C - Bib

「$i$が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数」とのことですが、一つずつ分解していきます。

1. 数$i$が書かれたゼッケンをつけている人$x$
2. 人$x$が見つめている人$y$
3. 人$y$のつけているゼッケンに書かれている数$j$

1は問題文に定義されていません。
2は与えられた配列$P$を使って、$y=P_x$と書けます。
3は与えられた配列$Q$を使って、$j=Q_y$と書けます。

ここで、1について考えます。
「数$i$が書かれたゼッケンをつけている人$x$」はわかっていませんが、その逆の「人$x$のつけているゼッケンに書かれている数$i$」は$i=Q_x$と書けます。
そこで、「数$i$が書かれたゼッケンをつけている人$x$」を表す逆配列$x=invQ_i$を定義します。

以上で、1~3はそれぞれ以下のように書けます。

1. $x=invQ_i$
2. $y=P_x$
3. $j=Q_y$

まとめると、$j=Q[P[invQ_i]]$と書くことができます。
あとはこの合成関数を使い、全探索で一人一人の答えを求めていけばよいです。

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

  // invQ[i]:= 数iが書かれた人が誰か
  const invQ = Array(N).fill(0);
  for (let i = 0; i < N; i++) invQ[Q[i] - 1] = i;

  const S = [];
  for (let i = 0; i < N; i++) S.push(Q[P[invQ[i]] - 1]);
  console.log(S.join(" "));
}

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

D - Doubles

愚直に二つのサイコロを選び、出目$1$から$10^5$まで一致する確率を求める場合、計算量は$O(N^2A_i)$となり最大で約$10^9$回の計算が必要になり間に合いません。

そこで、問題文をよく見ると$\sum_{i} K_i
$なので、一つのサイコロの出目の出現回数は限られています。

よって、前準備として個々のサイコロの出現する出目と、出目ごとの出現回数をハッシュマップ等で記録しておきます。

その上で、愚直に二つのサイコロを選び、片方のサイコロの出うる出目のみ一致する確率を求めさえすれば、この問題の計算量は$O(N\sum_{i} K_i)$で抑えることができ、十分高速にこの問題を解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const K = [];
  const A = [];
  for (let i = 0; i < N; i++) {
    line = input[i + 1].split(" ").map(Number);
    K.push(line[0]);
    A.push(line.slice(1));
  }

  // p[i]:= i番目のサイコロの目の出現回数についてのMapを格納
  const p = Array(N)
    .fill(0)
    .map(() => new Map());
  for (let i = 0; i < N; i++) {
    let map = new Map();
    for (let j = 0; j < K[i]; j++) map.set(A[i][j], (map.get(A[i][j]) || 0) + 1);
    for (let [key, value] of map) p[i].set(key, value);
  }
  
  // 愚直に2つのサイコロの目が一致する確率(pi/K[i])*pj/K[j]の総和を求め、最大値を更新する
  let ans = 0;
  for (let i = 0; i < N; i++) {
    for (let j = i + 1; j < N; j++) {
      let res = 0;
      for (let [key, value] of p[i]) {
        if (!p[j].has(key)) continue;
        let divident = p[i].get(key) * p[j].get(key);
        let divisor = K[i] * K[j];
        res += divident / divisor;
      }
      ans = Math.max(ans, res);
    }
  }
  console.log(ans);
}

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

E問題は方針自体はすぐに立ったのですが、二つの配列をいい感じにマージしていく処理の経験があまりなく、かつUnionFindの自作ライブラリも品質が微妙だったため実装できず諦めてしまいました。今回は少し薄めですがこの辺で失礼します。