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

AtCoder Beginner Contest 368

A~Dの4完（70分）でした。
894perfでレートは708->728（+20）になりました。
今回A~Dまでそんなに難易度が高くなく、Eが非常に難しかったため4完早解き回でした。C,Dの実装でもたついたのが悔やまれます。

A - Cut

問題文に書かれている通りにカードの山を入れ替えます。
下から$K$枚選ぶと言うのは、上から$N-K+1$番目〜$N$番目のカードを選ぶことと同義です。
先にこれらのカードを答えのスタックに入れておき、次に余ったカードを順番に入れていけば良いです。配列が0-indexedなので注意しましょう。

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

  console.log(ans.join(" "));
}

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

B - Decrease 2 max elements

問題文の通りに愚直にシミュレーションします。
もっと美しいやり方はあると思いますが、$N$が小さいので十分間に合います。
今回は、$A$に含まれる正整数を数え上げるcheck関数と、$A$の正整数が1以下になるまでシミュレーションを繰り返すrun関数を利用して解きました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);
  let ans = 0;
  const run = (arr) => {
    if(check(arr)) return;
    arr.sort((a, b) => b - a);
    arr[0]--;
    arr[1]--;
    ans++;
    run(arr);
  }
  run(A);
  console.log(ans);
}
const check = (arr) => {
  let ct = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0) ct++;
  }
  if (ct > 1) return false;
  return true;
};

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

C - Triple Attack

$1〜N$番目までシミュレーションすれば解が求まりますが、$H[i]$が大きいので愚直に1ターンずつシミュレーションしても間に合いません。
そこで、$H[i]$を0にするために必要なターン数を$O(1)$で数え上げる方法を考えます。
まず、$T$が3の倍数のとき3、それ以外ならば1ダメージを与えられるという条件に着目します。すると、$T$が何であろうと次の3ターンで与えられるダメージの合計は必ず5ダメージとなることがわかります。
したがって、$H[i]$が5以上である時、$H[i]$を5未満にするために必要なターン数は、5ダメージを与える周期を何回繰り返せばよいかがわかれば、それに3を掛けて求まります。
次に、上の操作で余った$H[i]$をあと何ターンあれば0以下にできるかを考えます。これは、現在の$T$が3の倍数であれば3減らし、それ以外なら1減らすという操作を愚直にやればよく、高々3回の操作で求まります。
以上の数え上げを、$1≦i≦N$について行うことでこの問題を解くことが出来ました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const H = input[1].split(" ").map(Number);
  let T = 0;
  const damage = [3, 1, 1];
  // Tが3の倍数なら3減り、それ以外は1減る
  let i = 0;
  while (i < H.length) {
    let round = Math.floor(H[i] / 5);
    T += round * 3;
    let rest = H[i] % 5;
    while (rest > 0) {
      T++;
      let s = T % 3;
      rest -= damage[s];
    }
    i++;
  }
  console.log(T);
}

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

D - Minimum Steiner Tree

タイトルに最小シュタイナー木を使えと書いてあるのでネットに転がってあるものをコピペして提出を色々と試してみましたが、結局ACできず別角度から自力で考えACしました。A~D早解き回だったので時間が本当にもったいなかったです。。。（5ペナしました）

考え方の一例ですが、まず$V[1]$を根とみなします（根は$V[1],... ,V[N]$に含まれる点であればなんでも良いです）。
ここで、木の任意の頂点$v$について次のことが言えます。
・$v$を親とする部分木の中で、$V[1],... ,V[N]$に含まれる頂点が一つ以上存在する場合、$v$は削除できない頂点である。
これは、$v$が$V[1],... ,V[N]$に含まれている場合は明らかであり、そうでなくても$v$の部分木の中の頂点$u$が$V[1],... ,V[N]$に含まれている場合、根$V[1]$から頂点$u$への経路は頂点$v$を経由するただ一通りしかないので、$v$を削除してしまうと$u$へ辿り着くことができなくなることから明らかです。
したがって、$v$を親とする部分木の中で$V[1],... ,V[N]$に含まれる頂点の数$sub[i]$を再帰で求めてやり、最後に各頂点について$sub[i]≧1$となる頂点の数を集計すればこの問題を解くことができます（$sub[i]$はbool値でも特に問題ないと思います）。
ただし、自分自身（頂点）が$V[1],... ,V[N]$に含まれているかどうか確認する際に、Setなどを使い計算量を削減する必要があります。
以上で、この問題を$O(N)$で解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, K] = input[0].split(" ").map(Number);
  const A = [],
    B = [];
  for (let i = 0; i < N - 1; i++) [A[i], B[i]] = input[i + 1].split(" ").map(Number);
  const V = input[N].split(" ").map(Number);
  const G = new Array(N + 1).fill(0).map(() => []);
  for (let i = 0; i < N - 1; i++) {
    G[A[i]].push(B[i]);
    G[B[i]].push(A[i]);
  }
  const set = new Set();
  for (let i = 0; i < N; i++) set.add(V[i]);
  const sub = new Array(N + 1).fill(0);
  const dfs = (pos, pre) => {
    if (set.has(pos)) sub[pos] = 1;
    for (let i = 0; i < G[pos].length; i++) {
      if (G[pos][i] === pre) continue;
      sub[pos] += dfs(G[pos][i], pos);
    }
    return sub[pos];
  };
  dfs(V[0], -1);
  let ans = 0;
  for(let i = 0; i < sub.length; i++) if(sub[i] >= 1) ans++;
  console.log(ans);
}

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