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

AtCoder Beginner Contest 379

ABDの3完（63分）でした。
C問題はBigIntにするのをうっかりして、終了20秒後にACしました…

878perfでレートは893->892（-1）でしたが、軽傷で済んでよかったです。
今回はA~Dをまとめます。

A - Cyclic

$N$は文字列として受け取っても整数として受け取っても良いのですが、文字列として受け取った方が楽でしょう。
文字列として受け取る場合は、シンプルに左から足し算していけばよいです。
もし整数として受け取る場合は、$N$を$abc$の形で表される3桁の整数とみなし、$a = \lfloor N/100 \rfloor$,$b = \lfloor N/10 \rfloor \bmod 10$,$c = N \bmod 10$などと表せば各桁の数値が得られますが、複雑なためおすすめはしません。

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

  let a = N[1] + N[2] + N[0];
  let b = N[2] + N[0] + N[1];
  console.log(a, b);
}

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

B - Strawberries

「左から順に見ていき、Oが$K$個連続で続けばひとつイチゴを食べ、連続する歯（$K$番目）の次の歯からまたOが$K$個連続するかどうかを繰り返し見る」という貪欲法によりこの問題を解くことができます。

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

  let ans = 0;
  for (let i = 0; i < N; i++) {
    if (S[i] == "X") continue;
    for (let j = 0; j < K; j++) {
      if (S[i + j] == "X") break;
      if (i + K > N) break;
      if (j == K - 1) {
        ans++;
        i += K - 1;
      }
    }
  }
  console.log(ans);
}

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

※追記
split("X")して、要素ごとにOの個数を$K$で割った商の整数部分を足し上げていくのが最も楽なようです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, K] = input[0].split(" ").map(Number);
  const S = input[1].split("X");
  let ans = 0;
  for (let i = 0; i < S.length; i++) ans += Math.floor(S[i].length / K);
  console.log(ans);
}

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

C - Sowing Stones

公式解説通りに解きましたが、コンテスト中は

• $X$がソートされていないのに気づかず1ペナ
• ソート後の$X_0≠1$のとき-1であることを忘れ1ペナ
• 累積和の添字ミスで1ペナ
• Number型をBigInt型にキャストするのを忘れ1ペナ

で合計4ペナしてしまい、結局コンテスト終了20秒後にACするという災難な結果になってしまいました。最後のはJavaScriptの弱みが出てしまってますね…

この問題はただでさえ考えることが多い上、ソートや$N$の最大値制約が大きく非常にWAしやすくなっているため細心の注意が必要です。この問題を解くための考え方は次のように整理します。

Nマスに"ちょうど"一つずつ石を置ける条件

• 石の合計がちょうど$N$である（$\sum_{i \in M} A_i = N$）
• 1マス目に石が置かれている（$\min_{i \in M} X_i = 1$）
• 空きマスを右から見ていった時、自分より左に石が複数重複しているマスがある

上の条件を一つでも満たせない場合、即座に-1を出力して終了します。
三つ目の条件については、ソート済みの配列$X$について、$X_{i+1} -X_i-1(空きマスの数) ≦ \sum_{j=1}^i A_j - X_i(余った石の数)$が常に正しいかどうか、累積和などで右から調べていけば良いです。
なお、上記全ての条件を満たす場合、必要な操作回数の最小値は$\sum_{i=1}^N i - \sum_{i=1}^M X_i A_i$*で表せます。

*理由：まず、石が$i$マス目に一つ存在する時、得点$i$を得られるとします。なお、存在するすべての石にこのルールを適用します。すると得点の初期値は$\sum_{i=1}^M X_i A_i$となります。次に、目指すべき状態である「$1〜N$マス目すべてに石がちょうど1個ずつ充填されている状態」の得点を考えると、$\sum_{i=1}^N i$で表せることがわかります。
ここで、$i$マス目の石を$i+1$に動かすという操作は、全体の得点を1だけ増加させることに他なりません。したがって、石を$N$マスにちょうど一つずつ置ける場合、最終状態の得点と初期状態の得点の差分$\sum_{i=1}^N i - \sum_{i=1}^M X_i A_i$がそのまま答えになります。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map((x, i) => i === 0 ? BigInt(x) : Number(x));
  const X = input[1].split(" ").map(BigInt);
  const A = input[2].split(" ").map(BigInt);
  const stones = new Array(M).fill(0);
  for (let i = 0; i < M; i++) stones[i] = [X[i], A[i]];
  stones.sort((a, b) => Number(a[0] - b[0]));

  let total = A.reduce((acc, cur) => acc + cur, 0n);
  if (total !== N) return console.log(-1);
  if (stones[0][0] !== 1n) return console.log(-1);

  let rest;
  let sum = new Array(M + 1).fill(0n);
  for (let i = 0; i < M; i++) sum[i + 1] = sum[i] + stones[i][1];

  for (let i = M - 1; i >= 0; i--) {
    let canPlace = sum[i + 1] - stones[i][0];
    if (i == M - 1) rest = N - stones[i][0];
    else rest = stones[i + 1][0] - stones[i][0] - 1n;

    if (canPlace < rest) return console.log(-1);
  }
  
  let ans = (N * (N + 1n)) / 2n;
  for (let i = 0; i < stones.length; i++) ans -= stones[i][0] * stones[i][1];
  console.log(ans.toString());
}

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

D - Home Garden

クエリ3の「$H$以上の植物を全て収穫する」については、一見植物を背の高い順に$O(logN)$で取得できるようなデータ構造（優先度付きキューなど）があれば解けそうです。

ただ、その場合クエリ2が問題で、すべての植えてある植物に対し一つずつ$T$だけ加算しようとすると明らかに時間が足りません。一応、区間更新一点取得の遅延セグ木という高等テクを使えば解ける（別名"セグ木で殴る"）のですが、そんなことをしなくてもある工夫をすれば優先度付きキューで解くことができます。

それは、総経過時間$sumT$を変数で管理しておいて、クエリ1のキュー追加時に$0$ではなく$-sumT$を追加するということです。
その上でクエリ2のとき$sumT$に$T$を加算、クエリ3のとき優先度付きキューの頂点の値に$sumT$を追加して$H$と比較するルールにすれば、全体で整合していることがわかります。
（例えば、総経過時間$sumT=3$のときクエリ1が来たら、キューには$-3$を追加する。次にクエリ3が来たら、ヒープの頂点は$-3+3=0$なので、結局植物の高さは辻褄が合っている）

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

  let T = 0;
  const pq = new PriorityQueue((a, b) => b - a);
  for (let i = 0; i < Q; i++) {
    if (queries[i][0] === 1) {
      pq.add(-T);
    }else if(queries[i][0] === 2){
      T += queries[i][1];
    }else if(queries[i][0] === 3){
      let cnt = 0;
      while(pq.peek() !== null && (pq.peek() + T) >= queries[i][1]){
        pq.remove();
        cnt++;
      }
      console.log(cnt);
    }
  }
}
// 以下、Priority Queueクラス。ここでは省略とする。

※追記
本問は優先度つきキューではなく、普通のキューでも解けるようです。
私が確認した限りでは、キュー,優先度付きキュー,区間更新一点取得遅延セグ木の3種類の解き方があり、この順に実装が難しくかつ計算量も大きくなります。
反面、より厳しい条件でも解けるようになります。

本問がキューで解ける理由としては、以下の二つが大きいと考えます。

• 新しい植物の高さは0で固定である（最近植えた植物ほど背が低いという単調性が保証される）
• 植えている全ての植物が同じ分だけ成長する（総経過時間として変数を外部に持つことができる）

もし、一つ目の条件が異なり「新しい植物の高さは任意の値」であれば、古い植物から収穫していく貪欲法が使えなくなるためキューは不適となり優先度付きキューを利用する必要があります。
また、二つ目の条件が異なり「クエリごと、植物グループごとに成長スピードが異なる」であれば、植物ごとに高さをトラッキングしていく必要があるため遅延セグ木を利用する必要があります。