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

AtCoder Beginner Contest 369
https://atcoder.jp/contests/abc369
A~Cの3完（40分）でした。
577perfでレートは728->714（-14）です。
D問題、まさかの添字ミスでバグりまくり大敗しました。
今回はA~Cとコンテスト後にACできたD問題についてまとめます。

A - 369

https://atcoder.jp/contests/abc369/tasks/abc369_a
解説は場合分けでしたが、場合分けする気力が湧かなかったのでSetでゴリ押しました。要は、

• $A$と$B$の中で小さい方に$|A-B|$を引いた数
• $A$と$B$の中で大きい方に$|A-B|$を足した数
• $A$と$B$のちょうど真ん中の数（ただし整数の場合に限る）
  の三種類の候補があり、同じ数字だった場合ダブルカウントしないというだけのことです。このような要件にはハッシュセットが便利です。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [A, B] = input[0].split(" ").map(Number);
  const ans = new Set();
  let diff = Math.abs(A - B);
  ans.add(Math.min(A, B) - diff);
  ans.add(Math.max(A, B) + diff);
  if ((A + B) % 2 == 0) ans.add((A + B) / 2);
  console.log(ans.size);
}
Main(require("fs").readFileSync(0, "utf8"));

B - Piano 3

https://atcoder.jp/contests/abc369/tasks/abc369_b
「最小の疲労度を求めよ」という問題文ですが、以下の考え方を持っておけば解けます。

• 左右の手どちらも最初の音の位置に置いておく
• 左右の手それぞれについて、今の音の位置と次の音の位置の差分を加算する

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = [],
    S = [],
    l = [],
    r = [];
  for (let i = 0; i < N; i++) {
    [A[i], S[i]] = input[i + 1].split(" ");
    A[i] = Number(A[i]);
  }
  for (let i = 0; i < N; i++) {
    if (S[i] === "L") l.push(A[i]);
    else r.push(A[i]);
  }
  let ans = 0;
  for (let i = 0; i < l.length - 1; i++) ans += Math.abs(l[i] - l[i + 1]);
  for (let i = 0; i < r.length - 1; i++) ans += Math.abs(r[i] - r[i + 1]);
  console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));

C - Count Arithmetic Subarrays

https://atcoder.jp/contests/abc369/tasks/abc369_c
ランレングス圧縮というやつです。
隣接する二項間の差分を管理する配列$d$を作り、$d$の要素で同じものが何回続くかを数え上げていきます。例えば、$d$で同じものが2回続く場合は$[3,6,9]$のように長さ3の等差数列があることを示します。長さ3の等差数列の中には、$[3,6]$や$[6,9]$のように長さ2の等差数列、そして$[3]$、$[6]$、$[9]$のように長さ1の等差数列が含まれます。
一般に、長さ$n$の等差数列の中には$1 + 2 + ... + n =$ $n(n+1)/2$個の等差数列が含まれます。ただし、長さ1の等差数列を数え上げてしまうとダブルカウントしてしまうことがあるため、長さ2までこの方法で数え上げて、長さ1の等差数列は明らかに$N$個なので別途$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 d = new Array(N - 1).fill(0);
  for (let i = 0; i < N - 1; i++) d[i] = A[i + 1] - A[i];
  let c = 0;
  let res = [];
  for (let i = 0; i < N - 1; i++) {
    if (d[i] === d[i + 1]) c++;
    else {
      res.push(c + 1);
      c = 0;
    }
  }
  let ans = N;
  for (let i = 0; i < res.length; i++) ans += (res[i] * (res[i] + 1)) / 2;
  console.log(ans);
}
Main(require("fs").readFileSync(0, "utf8"));

余談ですが、ABC362-Eで等差数列の問題が出ていて、こちらの問題は解いていたためコンテスト中に同じ方法で解けると思い込み時間を大幅にロスしました。$dp[i][j]:=初項がAi、第二項がAjの等差数列の個数$として$N$が小さければ計算できそうですが、$O(N^2)$なので$N$が大きいときは間に合いません。
自戒ですが、同じような問題を見たことがあったとしても、制約をきちんと読みましょう。
https://atcoder.jp/contests/abc362/tasks/abc362_e

D - Bonus EXP

https://atcoder.jp/contests/abc369/tasks/abc369_d
$dp[i][j]:= i番目までみて、j=0:偶数回倒した、j=1:奇数回倒したときに得られる経験値の最大値$として、貰うDPの要領で実装します。
行動の選択肢としては「逃げる」「倒す」の二択しかないので、逃げるときは前のモンスターまでの経験値と一緒。倒す場合はそれまでに奇数回倒している場合、次に倒すのは偶数番目になるため二倍の経験値を得、偶数回倒している場合は額面通りに経験値を得ます。
実装としては以下のようになります。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);
  const dp = new Array(N + 1).fill(0).map(() => new Array(2).fill(-Infinity));
  // dp[i][j]:= i番目までみて、j=0:偶数回倒した、j=1:奇数回倒したときの最大値
  dp[0][0] = 0;
  for (let i = 0; i < N; i++) {
    dp[i + 1][0] = Math.max(dp[i][0], dp[i][1] + 2 * A[i]);
    dp[i + 1][1] = Math.max(dp[i][1], dp[i][0] + A[i]);
  }
  console.log(Math.max(dp[N][0], dp[N][1]));
}
Main(require("fs").readFileSync(0, "utf8"));

本番で提出したコードは、dpの添字$k$を余計に入れていて、末尾に「逃げる」「倒す」どちらの選択肢を取ったかも管理してしまいました。結果、$dp[i + 1][0][0]$と$dp[i + 1][1][0]$の添字を逆に書いてしまい、コンテスト中にACできなかったので、無駄のないコードを書くことは本当に大事だと学びました。
$n-1$個の末尾情報は、「$n$回連続で同じ行動が制限される」などの条件がある場合に使えることも学びました。
以下、添字を正しく書き直したコードではACできたので、記念に記載しておきます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);
  const dp = new Array(N + 1).fill(0).map(() => new Array(2).fill(0).map(() => new Array(2).fill(-Infinity)));
  // dp[i][j][k] := i番目までの要素を見たときに、j=0なら奇数回倒していて、j=1なら偶数回倒している。k=0なら逃げ、k=1なら倒す。
  dp[0][1][0] = 0;
  for (let i = 0; i < N; i++) {
    dp[i + 1][0][0] = Math.max(dp[i][0][1], dp[i][0][0]);
    dp[i + 1][1][0] = Math.max(dp[i][1][1], dp[i][1][0]);
    dp[i + 1][0][1] = Math.max(dp[i][1][0] + A[i], dp[i][1][1] + A[i]);
    dp[i + 1][1][1] = Math.max(dp[i][0][0] + 2 * A[i], dp[i][0][1] + 2 * A[i]);
  }
  console.log(Math.max(dp[N][0][0], dp[N][0][1], dp[N][1][0], dp[N][1][1]));
}
Main(require("fs").readFileSync(0, "utf8"));