【JavaScript】ABC404まとめ（A~E）

AtCoder Beginner Contest 404

ABCDEの5完（73分0ペナ）でした。
1462perfでレートは1070->1116（+46）となりました。
今回はA〜Eをまとめます。

A - Not Found

色々と解法があると思いますが、一例として$S$に登場する英小文字の出現回数を調べて、最後に英小文字の中から一度も出現していない英小文字を特定して出力すれば良いです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0];
  
  // 各英小文字の出現回数を記録して、一度も出現しなかったものを一つ出力する
  const freq = new Array(26).fill(0);
  for (const c of S) {
    freq[c.charCodeAt(0) - 97]++;
  }

  for (let i = 0; i < 26; i++) {
    if (freq[i] == 0) return console.log(String.fromCharCode(i + 97));
  }
}

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

B - Grid Rotation

考え方自体はそこまで難しくないので簡単な説明に留めますが、必要な操作回数は「$S$の回転回数」＋「$S_{i,j}≠T_{i,j}$であるマスの個数」です。これは、一番外側に回転回数のループカウンタを０〜３まで回して、その中に1マスずつ$S_{i,j}≠T_{i,j}$かどうか全探索するようなループを書けばよいです。

難しいのは$S$を回転させる関数をどう書くかだと思いますが、$S_{i,j}$は「上から$i$行目、左から$j$列目」なので、90度右回転させると$S_{j, N-1-i}$で「上から$j$行目、左から$N-1-i$列目」に置き換わります。
この考えをもとに、自力で回転関数を書くか、あるいはconst rotateあたりまで書いてGithub Copilotに書かせるかですが、自分は本番でよく添字ミスをするので後者でガチャガチャしました（Github Copilotはコンテスト中の利用が認められています）。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  let S = [];
  for (let i = 1; i <= N; i++) S.push(input[i]);
  const T = [];
  for (let i = N + 1; i <= 2 * N; i++) T.push(input[i]);

  const rotate = (s) => {
    const res = [];
    for (let i = 0; i < N; i++) {
      res.push([]);
      for (let j = N - 1; j >= 0; j--) res[i].push(s[j][i]);
    }

    return res;
  };

  let ans = Infinity;
  for (let i = 0; i < 4; i++) {
    let cnt = 0;
    for (let j = 0; j < N; j++) {
      for (let k = 0; k < N; k++) {
        if (S[j][k] !== T[j][k]) cnt++;
      }
    }
    ans = Math.min(ans, cnt + i);
    S = rotate(S);
  }
  console.log(ans);
}

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

C - Cycle Graph?

このような問題では、まず定義をよく確認しましょう。
サイクルグラフの定義の一つ目と二つ目に着目すると、とりあえず$N$頂点全てを通る閉路が存在する必要があることがわかります。
また、三つ目の条件が肝で、$N$頂点の閉路をなす辺以外に辺はないことが言われているので、真珠のネックレスのような純粋な環の形になっていることがわかります。

以上を念頭に置いて必要条件を列挙しておき、それらを全てクリアしているかどうかを確認することで安全にこの問題に正解することができます。

必要条件としては以下の通りです。
1. 頂点数＝辺数である（$N=M$かどうか）
2. 全ての頂点の次数が2である
3. 全ての頂点が連結である

厳密には、2が満たされるとき必ず1も満たされるので、2,3だけで十分です（安全にと述べたのは、条件間の包含関係がわからないときはとりあえず必要条件を全て満たしているかどうか確認すればとりあえずは間違えることはないからです）。

2は数えるだけですね。3については、BFSやDFSを一回回した時の訪問頂点数が$N$であるか、あるいはUnionFindで直接的に確認するかなど色々とやりようがあります。

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

  // 全ての辺の次数が2のときN=Mのため、この行はなくても構わない
  if (N !== M) return console.log("No");

  const deg = new Array(N).fill(0);
  const uf = new UnionFind(N);
  for (let i = 0; i < M; i++) {
    deg[A[i] - 1]++;
    deg[B[i] - 1]++;
    uf.union(A[i] - 1, B[i] - 1);
  }
  
  // 一つでも次数が2でないものがあればNo
  if (deg.some((d) => d !== 2)) return console.log("No");
  
  // 全ての頂点が連結でなければNo
  const groups = uf.getGroups();
  if (groups[0].length != N) return console.log("No");
  console.log("Yes");
}
// 以下、UnionFindクラスのため省略

D - Goin' to the Zoo

まず、この問題のとっかかりを掴むためにヒントとなりそうな材料を探します。

第一に、本問題ではある動物を「2回以上」見ることができるかを問われていますが、当然同じ動物園に$N$回訪れるとその中にいる動物は必ず$N$回見ることになります。すなわち、最適状態において同じ動物園に3回以上訪れることはありえません。
同じ動物園に2回行けばその中の動物は2回見たことになり、それ以上行く必要がないからです。

第二に、動物園の数は$10$個しかありません。$2^{10}≒10^3$なので、この動物園のbit全探索を二重にしても約$10^6$となり十分高速です。

以上のヒントから、次のような解法を仮説として考えます。

• 任意の動物園を選んで回るツアーを計画する。このツアーを二周するとき、ありうる動物園の回り方を全探索することで費用の最小値を求めることができる。

例えば、$N=5$のとき、一周目の動物園の回り方を00110、二周目を10101と定義します。この5桁の数字は、左から$i$番目が0のとき動物園$i$に行かない、1のとき行くことを表すので、二周まとめた訪問回数はそれぞれ$(1,0,2,1,1)$回となります。

この考え方であれば、各動物園に訪れる回数は高々2回となります。
また、各動物園に2回まで訪れる場合の数を全て列挙するため取りこぼしはありません。

ただし、ツアーを2回まわる二重ループの中で、動物園の回り方を表す2進数を解読するために$N$回、各動物が2回以上見れたかどうかを確認するために$M$回必要なため、全体計算量は$O(2^{2N}(N+M))$です。
本問題ではおおよそ$10^8$程度でかなりギリギリになるため、言語によってはTLEになる可能性があります。一つでも$2$回以上見ていない動物がいたらツアーを即座に終了させる枝狩りをすることで、少しTLEする確率が減ります。

補足として、JavaScriptであれば枝狩りなしでも問題なくACできましたが、TLEするようであれば公式解説通りに動物園の周り方を3進数でもつtrit全探索をしましょう。

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

  // zoo_to_animal[i]:= i番目の動物園にいる動物のリスト
  const zoo_to_animal = new Array(N).fill(0).map(() => []);
  for (let i = 0; i < M; i++) {
    for (let j = 0; j < K[i]; j++) {
      zoo_to_animal[A[i][j] - 1].push(i);
    }
  }

  // pat[i]:= iを二進数で表したとき、1であればその動物園を訪れ、0であれば訪れないとしたときに見られる動物のリスト
  let pat = new Array(1 << N).fill(0).map(() => new Array(M).fill(0));
  for (let i = 1; i < 1 << N; i++) {
    for (let j = 0; j < N; j++) {
      if ((i >> j) & 1) {
        for (let k = 0; k < zoo_to_animal[j].length; k++) {
          const animal = zoo_to_animal[j][k];
          pat[i][animal]++;
        }
      }
    }
  }

  // 2回以上動物を見れればよいため、最適状態において同じ動物園に3回以上訪れることはない
  // したがって、動物園の訪問パターンを2回選ぶことによって最適状態を探索することができる
  let ans = Infinity;
  for (let i = 0; i < 1 << N; i++) {
    for (let j = 1; j < 1 << N; j++) {
      let pat_a = pat[i];
      let pat_b = pat[j];
      let c = 0;
      for (let k = 0; k < N; k++) {
        if ((i >> k) & 1) c += C[k];
        if ((j >> k) & 1) c += C[k];
      }
      
      // 計算量が少し厳しいので、一つでも2回以上見れない動物がいたらツアーを終了する
      let f = true;
      for (let k = 0; k < M; k++) {
        let freq = pat_a[k] + pat_b[k];
        if (freq < 2) {
          f = false;
          break;
        }
      }
      if (f) {
        ans = Math.min(ans, c);
      }
    }
  }
  console.log(ans);
}

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

E - Bowls and Beans

結論から言うと、$$dp_i:=茶碗iから、茶碗0もしくはA_j=1の茶碗jに到達するまでの最短手数$$と定義した動的計画法により、$O(N^2)$もしくはセグメント木を利用した高速化によって$O(NlogN)$でこの問題を解くことができます。今回は$N≦2000$なのでいずれにせよ十分高速です。

遷移の流れは至ってシンプルで、茶碗を$i=1,...,N-1$の順番に見ていき、$dp_i$を遷移可能な茶碗の中で最小の$dp_j$を使って$dp_j+1$で更新します。
その遷移の途中、もし$A_i=1$であれば総手数$ans$に$dp_i$を加算してから$0$に初期化しておきます。これは、$dp_i$の定義が$A_j=1$の茶碗$j$に到達するための最短手数なので、$i+1$以降を計算するために必要な処理です。

上記のアルゴリズムで求めた$ans$が今回出力するべき答えになります。

この解法はある程度理詰めで導くことができます。
入力例1を利用して説明を試みます。以下のシミュレーションを見てください。

入力例1
5
1 1 2 1
1 0 0 1

↓

まず、茶碗5のことを一回忘れる。
4
1 1 2
1 0 0
これは茶碗2の豆を茶碗1に移動すればよいだけなのでans=1

↓

次に、茶碗5のことを思い出す。
5
1 1 2 1
1 0 0 1
ここで、茶碗4までの答えはA_5が0なのか1なのかによらず、1のままである！
茶碗5を追加して考慮すると、茶碗5の豆をどこか別の茶碗を経由して茶碗1に移動させれば良い。
すると、茶碗5→茶碗4→茶碗2のように、2手で処理済みの茶碗に合流する。
したがって、先に茶碗5から茶碗2まで移動させた上で茶碗2にある豆をまとめて茶碗1に動かせば良い。
すなわち、ans=2+1=3となり想定解と一致した。

上記の考え方は一般に拡張することができます。

最後に計算量としては、$i=1,...,N-1$それぞれに$dp$を計算するのに約$N$回、$dp_i$を決定するために遷移可能な茶碗$j$それぞれを訪れて$dp_j$の最小値を求めるのに約$N$回かかるため$O(N^2)$ですが、$dp$をセグ木上で行うことで最小値を求める処理を$logN$回に抑えることによって全体計算量を$O(NlogN)$に下げることも可能です。
この問題では、$N$がそれほど大きくないためどちらでもACすることが可能です。

• $O(N^2)$解法（筆者の本番解答はこちらの方針）

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

  // dp[i]:= 茶碗0またはA[j]=1の茶碗j(j≦i)に到達するための最小手数
  const dp = new Array(N).fill(Infinity);
  dp[0] = 0;
  
  let ans = 0;
  for (let i = 1; i < N; i++) {
    let l = Math.max(0, i - C[i - 1]);
    for (let j = l; j < i; j++) dp[i] = Math.min(dp[i], dp[j] + 1);

    // A[i-1]=1であれば、これまで操作した茶碗に合流させるために必要な最小手数を足す
    // その茶碗を経由して後続の豆の移動コストを計算できるようにdp[i]を0にしておく
    if (A[i - 1] == 1) {
      ans += dp[i];
      dp[i] = 0;
    }
  }
  console.log(ans);
}

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

• $O(NlogN)$解法

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

  const seg = new SegTree(N, (x, y) => Math.min(x, y), Infinity);
  seg.set(0, 0);

  let ans = 0;
  for (let i = 1; i < N; i++) {
    const l = Math.max(0, i - C[i - 1]);
    const min = seg.prod(l, i);
    if (A[i - 1] == 1) {
      ans += min + 1;
      seg.set(i, 0);
    } else seg.set(i, min + 1);
  }
  console.log(ans);
}
// 以下SegTreeクラスのため割愛

まとめ

久しぶりに5完することができ、かなりレートを伸ばすことができました。
ただ、B,C,D問題で考察が沼りかけてたのと、E問題を適当に投げたら意外にもACしてしまったので全く手応えはありません笑
残りの時間はFを飛ばしてGを見ていましたが、牛ゲーかな？と思ったらやっぱり牛ゲーでした。いつか牛ゲーを履修したいとは思いますが、（レートがまだ低いため）今じゃない感があります。

ついに緑瓦４になりました。
入水目前ですが、特に何かを変えることなく引き続き頑張っていきたいと思います。