【JavaScript】ABC367まとめ（A〜D）

AtCoder Beginner Contest 367
https://atcoder.jp/contests/abc367

A~Dの4完（96分）でした。
1017perfでレートは666->708（+42）に。
最近1000前後のパフォが安定してきてるので、さくっと入緑できそうです。
本記事ではコンテスト期間中に提出したA~DのACコードを貼っておきます。

A - Shout Everyday

起床時間と就寝時間の間にたこ焼きへの愛を叫ぶことができるか判定する。
ただし、起床時間よりも就寝時間とたこ焼きへの愛を叫ぶ時間が早い場合は24時間をあらかじめ足しておく。
（例：18時起床、4時就寝、9時叫ぶ→18時起床、28時就寝、33時叫ぶ。18時から28時までの間にたこ焼きへの愛を叫ぶことができないので"No"を出力する）

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  let [a, b, c] = input[0].split(" ").map(Number);
  if (b <= c) b += 24;
  if (a <= c) a += 24;
  if (a >= c && a <= b) console.log("Yes");
  else console.log("No");
}

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

B - Cut .0

コンテスト中に提出したコードでは、入力を文字列の配列として受け取り、
後ろから順に見ていき"0"が続く限り除去、または"."があれば除去して終了という処理を実行した。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const X = input[0].split("");
  for (let i = X.length - 1; i >= 0; i--) {
    if (X[i] == "0") X.pop();
    else if (X[i] == ".") {X.pop(); break;}
    else break;
  }
  console.log(X.join(""));
}

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

なお、JavaScriptではNumber型で受け取ってそのまま出力してもACできる（え？）。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const X = Number(input[0]);
  console.log(X)
}

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

C - Enumerate Sequences

方針としては、大まかに下記の①、②で説明できる。
①全ての要素が1以上5以下の組み合わせのうち総和がKの倍数の配列だけをスタックに入れておく。
②各組み合わせの全ての順列を列挙して任意の$i$について$Pi$以下であればOK。
ただし辞書順に出力する必要があるため答えをスタックに入れてソートする必要がある。

①は、最小添字規則の考え方に則り、常に左隣の要素≦右隣の要素となるように配列を組めば問題ない。
②は、①で列挙した組み合わせ全てに対して自作のnext_permutationのライブラリを適用して全順列列挙し、その上で各要素ごとに$Pi$と比較すればよい。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, K] = input[0].split(" ").map(Number);
  const R = input[1].split(" ").map(Number);
  const comb = generateCombinations(N);
  let combinations = [];
  for (let i = 0; i < comb.length; i++) {
    let s = comb[i].reduce((acc, cur) => acc + cur, 0);
    if (s % K === 0) combinations.push(comb[i]);
  }
  let ans = [];
  for (let i = 0; i < combinations.length; i++) {
    const perm = generatePermutations(combinations[i]);
    for (let j = 0; j < perm.length; j++) {
      let f = true;
      for (let k = 0; k < perm[j].length; k++) {
        if (perm[j][k] > R[k]) {
          f = false;
          break;
        }
      }
      if (f) ans.push(perm[j]);
    }
  }
  ans.sort();
  console.log(ans.join("\n").replace(/,/g, " "));
}
function generateCombinations(N) {
  const result = [];

  function backtrack(currentCombination, start) {
    if (currentCombination.length === N) {
      result.push([...currentCombination]);
      return;
    }

    for (let i = start; i <= 5; i++) {
      currentCombination.push(i);
      backtrack(currentCombination, i); // 次の要素は同じかそれより大きい値
      currentCombination.pop();
    }
  }

  backtrack([], 1); // 1からスタート
  return result;
}

function nextPermutation(arr) {
  for (let i = arr.length - 2; i >= 0; i--) {
    if (arr[i] < arr[i + 1]) {
      for (let j = arr.length - 1; j > i; j--) {
        if (arr[j] > arr[i]) {
          [arr[i], arr[j]] = [arr[j], arr[i]];
          const len = (arr.length - (i + 1)) >> 1;
          for (let k = 0; k < len; k++) {
            [arr[i + 1 + k], arr[arr.length - 1 - k]] = [arr[arr.length - 1 - k], arr[i + 1 + k]];
          }
          return true;
        }
      }
    }
  }
  return false;
}
// 順列生成器。配列を配列として返すため、文字列が欲しい場合はjoin("")で結合する必要がある
// 配列用にスプレッド構文を使用しているが、遅いので文字列を出力する場合はjoin("")に書き換える
const generatePermutations = (arr) => {
  let sorted = arr.sort();
  const res = [[...sorted]];
  while (nextPermutation(sorted)) res.push([...sorted]);
  return res;
};

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

本番では難しい解き方をしてしまったが、下記のように各要素が1以上$Pi$以下で長さNの順列を再帰で全列挙して、総和がKの倍数かどうかを判定する方法でも解ける。
この方法であれば、最初から辞書順に順列を生成するため最後にソートする必要もない。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, K] = input[0].split(" ").map(Number);
  const R = input[1].split(" ").map(Number);
  let st = [];
  let ans = [];
  const dfs = (pos) => {
    if (pos === N) {
      if (st.reduce((a, b) => a + b, 0) % K === 0) ans.push([...st]);
      return;
    }
    for (let i = 1; i <= 5; i++) {
      if (R[pos] < i) continue;
      st.push(i);
      dfs(pos + 1);
      st.pop();
    }
    return;
  };
  dfs(0);
  console.log(ans.join("\n").replace(/,/g, " "));
}
Main(require("fs").readFileSync(0, "utf8"));

D - Pedometer

まず、点0から時計回りに出発して、距離がMの倍数となる点を数え上げるのは、
点0からの距離の累積和（mod M）が0となる点0以外の点の個数を数えることで可能。

スタート地点が点0のときの個数はわかったので、次にスタート地点を時計回りに一つずらしたときを考える（点1からスタート）。
このとき、点0以外の点については、点1と同じ累積和（mod M）の値の個数の分だけ数え上げればよいことがわかる。一方で、点0については１周余分に歩いた時の累積和（mod M）にあらかじめ更新しておけば、ほかの点と同じように扱うことが可能になる。
よって、上記の操作を点N-1まで実行することでO(N+M)でこの問題を解くことができた。

以下のコードでは、me配列に点0から任意の点への距離の累積和（mod M）を、m配列に距離の累積和（mod M）0~M-1である点がそれぞれいくつあるかを格納している。

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);
  const m = new Array(M).fill(0);
  const me = new Array(N).fill(0);
  let n = 0;
  m[0] = 1;
  let sum = 0;
  for (let i = 0; i < N; i++) {
    me[i] = n;
    n = (n + A[i]) % M;
    if (i !== N - 1) m[n]++;
    else sum = n;
  }

  let ans = m[0] - 1;
  for (let i = 0; i < N - 1; i++) {
    m[me[i]]--;
    me[i] = (me[i] + sum) % M;
    m[me[i]]++;
    ans += m[me[i + 1]] - 1;
  }
  console.log(ans);
}

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