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

AtCoder Beginner Contest 376

A~Cの3完（46分）でした。
750perfでレートは856->846（-10）です。
今回はコンテスト中に解けたA~Cとコンテスト後に解いたDをまとめます。

A - Candy Button

制約が小さいので、愚直に1番目から$\text{T}[i]$を順にシミュレーションしていけばよいです。
より具体的には、前回飴をもらった時間を$prev$に記録しておき、$\text{T}[i]-prev≧C$のときだけ飴をもらって$prev$を更新し、$\text{T}[i]-prev<C$ならば何もしないでよいです。
なお、$prev$の初期値を負の非常に小さい値に設定しておけば、for文の中で場合分けしなくて済みます。

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

  let ans = 0;
  let prev = -Number.MAX_SAFE_INTEGER;
  for (let i = 0; i < N; i++) {
    if (T[i] - prev >= C) {
      ans++;
      prev = T[i];
    }
  }
  console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));

B - Hands on Ring (Easy)

これもAと同じくシミュレーションですが、円環上を動くため若干実装が面倒です。
発想ですが、各指示について$\text{H}[i]$（$L$または$R$の動かす方の手）がターゲット$\text{T}[i]$に向かうためのルートとしては時計回りまたは反時計回りの2パターンしかないです。
しかし、動かさない方の手にぶつかってしまうことは禁止されているので、うまく動かさない方の手と途中でぶつからないルートを選択する必要があります。ただ円環のためこの選択をするのが面倒です。
今回は制約が小さいので愚直に1マスずつ進んで、もし途中で動かさない方の手があったら別のルートを試す、というシミュレーションでも全く問題ありませんが、今回はより高速に$O(N)$で解く方法を紹介します。

さて、$\text{H}[i]$の動かすべきルートの決定方法ですが、仮に円環ではなく直線だったとして「数字の大きい方に進んでいったときに動かさない方の手にぶつかるか？」という問題であれば簡単でしょう。
動かす方の手の座標を$move$、動かさない方の手の座標を$stay$とすれば、$move<stay<\text{T}[i]$のときぶつかります。
この議論を円環に発展させます。実は、$stay,\text{T}[i]$が$move$よりも小さいとき、$N$を加算する処理を加えるだけで時計回りのコースに動かさない方の手があるかどうかが判定できます。ここで具体例を見ていきましょう。以下の例では$N=6$とします。

• ケース１： $move=2$,$stay=4$,$\text{T}[i]=5$のとき
  →$move<stay<\text{T}[i]$が成立し、実際に時計回りのコースでは動かさない方の手にぶつかります。
• ケース２：$move=2$,$stay=4$,$\text{T}[i]=1$のとき
  →$\text{T}[i]+N=7$のため、$move<stay<\text{T}[i]+N$が成立し、実際に時計回りのコースでは動かさない方の手にぶつかります。
• ケース３：$move=4$,$stay=1$,$\text{T}[i]=3$のとき
  →$stay+N=7$,$\text{T}[i]+N=9$のため、$move<stay<\text{T}[i]$が成立し、実際に時計回りのコースでは動かさない方の手にぶつかります。
• ケース４：$move=4$,$stay=3$,$\text{T}[i]=1$のとき
  →$stay+N=9$,$\text{T}[i]+N=7$のため、$move<\text{T}[i]<stay$となり、時計回りのコースでは動かさない方の手にぶつかりません。

厳密な証明は省きますが、このように時計回りのコースに動かさない方の手が存在するかを判定することができます。それさえわかれば、時計回りのコースの距離と反時計回りのコースの距離は一意に決まるため、動かさない方の手が存在しない方のコースの距離を足し上げていく、という方法でこの問題を高速に解くことができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, Q] = input[0].split(" ").map(Number);
  let H = [],
    T = [];
  for (let i = 0; i < Q; i++) [H[i], T[i]] = input[i + 1].split(" ");
  T = T.map(Number);

  const calc = (L, R, H, T) => {
    let [move, stay] = H === "L" ? [L, R] : [R, L];
    if (stay < move) stay += N;
    if (T < move) T += N;
    let res = stay > T ? T - move: N - (T - move);
    return res;
  };

  let ans = 0,
    L = 1,
    R = 2;
  for (let i = 0; i < Q; i++) {
    ans += calc(L, R, H[i], T[i]);
    H[i] === "L" ? (L = T[i]) : (R = T[i]);
  }

  console.log(ans);
}

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

C - Prepare Another Box

この問題は解説によると二分探索でも解けるようですが、私は貪欲法で解きました。
解説は公式サイトで丁寧にされているので、ここではどうやって貪欲法を思いついたのかを記載します（ふんわりとでも理解いただけると嬉しいです）。

着目すべきポイントとしては、

• 大きいおもちゃと小さいおもちゃでは大きいおもちゃの方が収納するのが難しい（＝入れる箱が限定される）
• 新しい箱を調達しておもちゃと箱が同数となったときに、すべての$i$について$\text{A}[i]≦\text{B}[i]$となる必要がある

でしょうか。
1つ目のポイントで、どうやら配列$\text{A}$をソートして、大きい方から順に入れるべき箱を解決していけば良さそうだと言うのがわかります。
次に、2つ目のポイントで$\text{B}$もソートして$\text{A}$と同じ順序関係にしてあげることで条件を満たしやすくなることがわかります。

すなわち、$\text{A}=[2,3,5,7]$,$\text{B}=[2,6,8]$の例だと, 新しく追加する箱のサイズ$x$とすると、全てのおもちゃを収納できるような$x$が存在すると仮定したとき、答えの状況としては以下の4パターンに絞り込むことができます。

$i$	1	2	3	4
$\text{A}[i]$	2	3	5	7
$\text{B}[i]$（P1）	2	6	8	$x=7$
$\text{B}[i]$（P2）	2	6	$x=5$	8
$\text{B}[i]$（P3）	2	$x=3$	6	8
$\text{B}[i]$（P4）	$x=2$	2(<$\text{A}[2]$=3のためNG)	6	8

まさに、上図のようなイメージで$i$をどこまで小さくできるか？また、最小となる$i$が定まれば$\text{A}[i]$より厳密に大きい必要はないので、最小の$x$は$\text{A}[i]$であることがわかります。
また、$i$をどんどん小さくしていくと、$\text{B}[2]$（P4）のように$\text{A}[i]≦\text{B}[i]$の条件を満たせなくなる箱が出てくることがあるので、そこが$i$を小さくできる限界であることがわかります。
このようにして$x$の最小値の候補を導けば、あとはそれが実現可能か？を考える問題に帰着します。$x$よりも小さい箱について、$\text{A}[i]>\text{B}[i]$となるような$i$があれば実現不可能です。
以上の考え方をコードに落とし込めば、ソートがボトルネックとなりこの問題を$O(NlogN)$で解くことができました。

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

  A.sort((a, b) => a - b);
  B.sort((a, b) => a - b);

  let lim = N - 1;
  for (let i = N - 1; i >= 1; i--) {
    if (A[i] <= B[i - 1]) lim = i - 1;
    else break;
  }

  for (let i = 0; i < lim; i++) {
    if (A[i] > B[i]) return console.log(-1);
  }

  console.log(A[lim]);
}

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

D - Cycle

閉路検出とくればDFSなのですが、今回に関しては最短距離を求める必要があるのでBFSを利用する必要があります。
例えば、[1→2→3→1,1→3→1]のようなエッジのあるグラフ構造を考えたときに、DFSだと1→2→3→1を先に探索して3を探索済みにマークしてしまい、
最小閉路の1→3→1が漏れる可能性があります（筆者もこの反例がコンテスト中に思い浮かびませんでした）。
よって、まずはBFSにより頂点1から他の各頂点$i$までの最短経路$\text{dist}[i]$を求め、その頂点$i$から頂点1へのエッジがある場合のみ最小閉路の可能性があるので、その中の最小値$\min_{i \in N} (\text{dist}[i] + 1)$が答えになります。
頂点$i$から途中の頂点を経由して頂点1にたどり着くようなケース（$\text{dist}[i] + x$）を考えなくて良いのかと疑問に思われるかもしれませんが、頂点$i$→頂点$i'$→頂点1のような例で言うとこの閉路は$\text{dist}[i'] + 1$以上のサイズであることが保証されているため考慮を除外して構いません。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  const a = [],
    b = [];
  for (let i = 0; i < M; i++) [a[i], b[i]] = input[i + 1].split(" ").map(Number);
  const G = new Array(N + 1).fill().map(() => []);
  for (let i = 0; i < M; i++) G[a[i]].push(b[i]);
  let dist = new Array(N + 1).fill(-1);

  const bfs = (pos) => {
    const que = [pos];
    for (let i = 0; i < que.length; i++) {
      const pos = que[i];
      for (let j = 0; j < G[pos].length; j++) {
        let nex = G[pos][j];
        if (dist[nex] == -1) {
          dist[nex] = dist[pos] + 1;
          que.push(nex);
        }
      }
    }
    return;
  };

  dist[1] = 0;
  bfs(1);

  let ans = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i < M; i++) {
    if (b[i] === 1 && dist[a[i]] !== -1) ans = Math.min(ans, dist[a[i]] + 1);
  }
  console.log(ans === Number.MAX_SAFE_INTEGER ? -1 : ans);
}

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