【JavaScript】ABC410まとめ（A~C,E）

AtCoder Beginner Contest 410

ABCEの4完（79分0ペナ）でした。
1132perfでレートは1138->1138（+0）となりました。
今回はA〜C,Eをまとめます。

A - G1

$K$歳の馬は、$A_i ≧ K$であるようなレース$i$に出馬できます。
$A$を全探索して、$A_i ≧ K$となるレースの個数を数え上げましょう。

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

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

B - Reverse Proxy

箱に入っているボールの個数を記録した配列$\text{freq}$を用意しておきシミュレーションをします。

まず一つ目の処理は、$X_i>0$のとき箱$X_i$にボールを入れろと書いてあるので$\text{freq}_i$に+1します。
二つ目の処理は、$X_i=0$のとき$\text{freq}_j$が最小かつ$j$が最小となるような$j$にボールを入れろと書いてあるので、$\text{freq}$を全探索して最小値$min$を特定し、再度$\text{freq}$を全探索して$\text{freq}_j=min$となるような$j$の最小値を求めて$\text{freq}_j$に+1すればよいです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, Q] = input[0].split(" ").map(Number);
  const X = input[1].split(" ").map(Number);
  const ans = [];
  const freq = new Array(N + 1).fill(0);
  for (let i = 0; i < Q; i++) {
    if (X[i] > 0) {
      freq[X[i]]++;
      ans.push(X[i]);
      continue;
    }

    let min = Infinity;
    for (let j = 0; j < N; j++) min = Math.min(min, freq[j + 1]);
    for (let j = 0; j < N; j++) {
      if (freq[j + 1] === min) {
        freq[j + 1]++;
        ans.push(j + 1);
        break;
      }
    }
  }
  console.log(ans.join(" "));
}

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

C - Rotatable Array

長さ$N$の配列全体に対して$Q$回の巡回シフトを愚直に適用すると$NQ$回の計算が必要なのでTLEしてしまいます。
ここで、仮に$k$回巡回シフトしたとき、インデックス$i$は$i-k+N\pmod{N}$のように表せることに着目します。
裏返して考えると、$k$回巡回シフトしたときのインデックスを$j$とすると、もとのインデックスは$j+k\pmod{N}$です。

つまり、

• 処理1：入力$p$と巡回シフト回数$cnt$から元のインデックス$idx$を逆算し$A_{idx}=x$とする
• 処理2：入力$p$と巡回シフト回数$cnt$から元のインデックス$idx$を逆算し$A_{idx}$を出力する
• 処理3：巡回シフト回数$cnt$に+1する

というコードを書くことでこの問題に答えられそうです。
以上、$O(N+Q)$でこの問題に正解することができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, Q] = input[0].split(" ").map(Number);
  let cnt = 0;
  const A = new Array(N).fill(0).map((_, i) => i + 1);
  const ans = [];
  for (let i = 0; i < Q; i++) {
    let query = input[i + 1].split(" ").map(Number);
    if (query[0] === 1) {
      let idx = query[1] - 1 + cnt;
      idx %= N;
      A[idx] = query[2];
    } else if (query[0] === 2) {
      let idx = query[1] - 1 + cnt;
      idx %= N;
      ans.push(A[idx]);
    } else if (query[0] === 3) cnt += query[1];
  }
  console.log(ans.join("\n"));
}

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

E - Battles in a Row

最も基本的なナップザックDPを考えると、
$$dp_{i,j,k}:=残りの体力j、魔力kでi番目の魔物を倒せるなら1、倒せないなら0$$
として解くことはできそうですが、これは$NHM$回の計算が必要で今回の制約下ではTLEとなります。

そこで、今$dp$が$0$または$1$の2値しか情報を持っていないので、$i,j,k$のどれかを右に持ってこれないかを考えます。
例えば、
$$dp_{i,j}:=残りの体力jでi番目の魔物を倒せる場合は最大でどれだけ魔力を残せるか、倒せない場合は-\text{Infinity}$$

このように定義して$dp$を計算すれば、全体の計算量は$O(NH)$となり、$dp_{i,j}$が正となるような最大の$i$が答えとなります。

余談ですが、この解法が許されるのは「魔物を倒さない」という選択肢がないからです。もしその選択があるなら、体力が尽きた後も「魔物を倒さない」選択をとり続けることによって魔力を減らさずに保つことができ、$dp_{i,j}$の値は常に$M$で満タンのままです。

さて、詳細の遷移を見てみましょう。今回は渡すDPで問題を解いています。
$dp_{i,j}$からの遷移としては次の二通りがあり得ます。

• $dp_{i+1, j-A_i}:=i番目の魔物をA_iの体力を消費して倒した場合$
• $dp_{i+1, j}:=i番目の魔物をB_iの魔力を消費して倒した場合$

注意点として、一つ目の遷移は$j-A_i≧0$、二つ目の遷移は$dp_{i,j}-B_i ≧0$の制約が必要です。この制約を満たせない限り、$i$番目の魔物は倒せないため遷移しないことにします。

以上で$dp$テーブルの構築は終了です。
あとは、テーブルの値を一つ一つみていって$dp_{i,j}≧0$となるような$i$の最大値$ans$を求めて$\text{max}(0,ans)$を出力すればOKです。
以上、$O(NH)$でこの問題を解くことができました。

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

  // dp[i][j]:= i番目の魔物までみて、体力がjのときの最大MP
  const dp = new Array(N + 1).fill(0).map(() => new Array(H + 1).fill(-Infinity));
  dp[0][H] = M;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j <= H; j++) {
      if (dp[i][j] === -Infinity) continue;
      if (j - A[i] >= 0) dp[i + 1][j - A[i]] = Math.max(dp[i + 1][j - A[i]], dp[i][j]);
      if (dp[i][j] >= B[i]) dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j] - B[i]);
    }
  }

  // dp[i][j]が-1でなければ、i番目の魔物まで倒せていることがわかる
  let max = 0;
  for (let i = 1; i <= N; i++) {
    let f = false;
    for (let j = 0; j <= H; j++) {
      if (dp[i][j] >= 0) {
        f = true;
        max = Math.max(max, i);
        break;
      }
    }
    if (!f) break;
  }
  console.log(max);
}

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

まとめ

D問題は、「頂点1から頂点$i$までのwalkで辺の総xorが$k$となるようなものは存在するか？」という問題に帰着することができず、ずっと「頂点1から頂点$N$までのパスの途中で、ループできるところがあれば1回だけループを経由するかを選ぶ」という全探索の方針を考えていました。
しかし、多重辺やループを考慮したパスの数が爆発的に増加するといった問題を解決することができず、50分程度悩んだ結果諦めてE問題に取り組みましたが、ナップザックDPはF - Knapsack with Diminishing ValuesやEDPC、鉄則などで散々やってきたのですんなり解くことができました。
結果としてレートはプラマイゼロで、D問題解けなかったですがなんとか助かりました。
今日もコンテストがありますが、水パフォを出すことを目標にがんばります。