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

AtCoder Beginner Contest 402

ABCDの4完（44分0ペナ）でした。
1080perfでレートは1039->1043（+4）となりました。
今回はA〜Dをまとめます。

A - CBC

JavaScriptのcharCodeAt()メソッドは、文字列を整数のUTF-16コードに変換します。
また、英大文字のUTF-16コードの範囲は65〜90（アルファベット順に、A=65〜Z=90）で、英小文字のUTF-16コードの範囲は97〜122（アルファベット順に、a=97〜z=122）です。

したがって、英文字$S_i$のUTF-16コードについて、a=97より小さいとき$S_i$は英大文字であり、a=97以上のとき$S_i$は英小文字であるという判定方法が利用できます。

このように、英大文字の方が英小文字よりもUTF-16コードが小さいということさえ覚えていれば、わざわざ具体的なUTF-16コード番号を覚えておく必要がありません。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0];
  const T = [];
  for (let i = 0; i < S.length; i++) {
    if (S[i].charCodeAt(0) < "a".charCodeAt(0)) T.push(S[i]);
  }
  console.log(T.join(""));
}

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

B - Restaurant Queue

クエリ１では待ち行列の末尾に食券番号$X$を追加し、クエリ２では待ち行列の先頭の食券番号$X$を出力します。
この場合はシンプルなキューが要件を満たします。

なお、JavaScriptでは標準機能にキューがないので、参考コードのように自作するか、スタックをうまく使って代用するかしかありません。

補足として、自作ライブラリDequeのappend(x)メソッドについては末尾にxを追加し、popleft()メソッドについては先頭の値を返します。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const Q = Number(input[0]);
  const query = [];
  for (let i = 0; i < Q; i++) query[i] = input[i + 1].split(" ").map(Number);
  const que = new Deque();
  for (let i = 0; i < Q; i++) {
    const [t, x] = query[i];
    if (t === 1) que.append(x);
    else console.log(que.popleft());
  }
}
// 以下、Dequeクラスのため割愛

C - Dislike Foods

まず、考え方の方針を示します。
ある料理が食べられるようになるということは、その料理にふくまれる苦手な食材がなくなるということです。
したがって、各料理に含まれる苦手な食材のセット$\text{dish_to_food}$を管理しておいて、各食材を克服する都度そのセットから食材を消去し、$\text{dish_to_food}$から食材がなくなった時に食べられる料理の個数が一つ増えるというようなプログラムを書けばこの問題に正解できそうです。

以下、イメージアップのために例を示します。
$N=4, M=4, B=[1,4,3,2]$としましょう。

• ０日目

料理番号	$\text{dish_to_food}$	食べられるかどうか
1	1,2,3	×
2	3,4	×
3	2,3	×
4	4	×
食べられる料理の合計数		0

• １日目（料理１を克服）

料理番号	$\text{dish_to_food}$	食べられるかどうか
1	2,3	×
2	3,4	×
3	2,3	×
4	4	×
食べられる料理の合計数		0

• ２日目（料理４を克服）

料理番号	$\text{dish_to_food}$	食べられるかどうか
1	2,3	×
2	3	×
3	2,3	×
4	-	◯
食べられる料理の合計数		1

• ３日目（料理３を克服）

料理番号	$\text{dish_to_food}$	食べられるかどうか
1	2	×
2	-	◯
3	2	×
4	-	◯
食べられる料理の合計数		2

• ４日目（料理２を克服）

料理番号	$\text{dish_to_food}$	食べられるかどうか
1	-	◯
2	-	◯
3	-	◯
4	-	◯
食べられる料理の合計数		4

したがって、この例の答えは1〜4日目の$0,1,2,4$を改行して出力すればよいことになります。
あとはこの問題をどう高速に解くかですが、$\text{dish_to_food}$からの食材の消し込みは$O(1)$で高速に行えるので問題ありません。一方で、ある食材がどの料理に含まれているかについての情報がなければ、$N$回にわたり$M$種類の料理を逐一確認して各食材が含まれているかどうかを確認しにいかなければならず、最悪$NM$回の計算回数がかかりTLEする可能性が高いです。

そこで、あらかじめ各食材がどの料理に含まれているかのセット$\text{food_to_dish}$を作成しておきましょう。そうすることにより、ある食材$B_i$がどの料理に含まれているかの確認回数は、料理に含まれる食材の総和である$\sum{K}$で抑えることができます。

以上の考え方をコードに落とし込むことでこの問題を解くことができました。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  const K = [];
  const A = [];
  for (let i = 0; i < M; i++) {
    const line = input[i + 1].split(" ").map(Number);
    K[i] = line[0];
    A[i] = line.slice(1);
  }
  const B = input[M + 1].split(" ").map(Number);
  
  // food_to_dish[i]:= 食材iを含む料理のセット
  // dish_to_food[i]:= 料理iに含まれる食材のセット
  const food_to_dish = new Array(N).fill(0).map(() => new Set());
  const dish_to_food = new Array(M).fill(0).map(() => new Set());
  for (let i = 0; i < M; i++) {
    for (let j = 0; j < K[i]; j++) {
      food_to_dish[A[i][j] - 1].add(i);
      dish_to_food[i].add(A[i][j] - 1);
    }
  }
  
  // 初期状態では、各料理のすべての食材が苦手のためdish_to_foodにはすべての食材が含まれている
  // 苦手な食材を克服するごとに、dish_to_foodから食材を削除して、苦手な食材がなくなった料理の数をカウントする
  let ans = 0;
  for (let i = 0; i < N; i++) {
    let f = B[i] - 1;
    for (const d of food_to_dish[f]) {
      dish_to_food[d].delete(f);
      if (dish_to_food[d].size === 0) ans++;
    }
    food_to_dish[f].clear();
    console.log(ans);
  }
}

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

D - Line Crossing

はじめに断っておきますが、この解説では数学的に厳密な証明は避けます。
円に内接する正多角形をじっと観察することにより、ある事実に気づくことができます。

それは、任意の相異なる頂点$(a, b)$を通る直線と、頂点$(1,x)$を通る直線とが平行となるような頂点$x$が（ほぼ）必ず存在するということです。
ここで「ほぼ」と言っているのは、例えば頂点$(2,8)$を通る直線のように、頂点$1$の接線と平行となるようなパターンが例外として存在するからです。逆に、頂点$1$の接線と平行となるパターン以外については頂点$(a,b)$に対応する頂点$(1,x)(x≠1)$が必ず存在するため、頂点$1$の接線と平行となるパターンを頂点$(1,1)$に対応させることで直線を$N$種類にグルーピングすることができます。

それを踏まえて、頂点$(a,b)$を頂点$(1,x)$で表すための方法について考えましょう。
以下の図を見てください。

例えば、頂点$(1,2)$と平行な直線は頂点$(8,3)$、頂点$(7,4)$、頂点$(6,5)$の三種類ですが、ここから言えることは、$a$を反時計回りに$k$個ずらした点$a'$と$b$を時計回りに$k$個ずらした点$b'$を通る直線と、頂点$(a,b)$を通る直線は平行であるということです。

この性質を利用すれば、任意の頂点$(a,b)$を頂点$(1,x)$に対応づけることができます。
なお、円環状のため頂点番号が負にならないように注意して実装する必要があります。

以上で、任意の頂点$(a,b)$を通る$M$本の直線を$N$種類にグルーピングすることができました。
あとは、直線から２本を選ぶ組み合わせの全体から、各グループごとに２本選ぶ組み合わせを差し引けば求める答えが得られます。

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

  // 頂点番号が大きい方を1に移動してパターン分けする
  const pat = new Array(N).fill(0);
  for (let i = 0; i < M; i++) {
    let [a, b] = [A[i] - 1, B[i] - 1];
    if (a > b) [a, b] = [b, a];
    let diff = N + 1 - b;
    let nex_a = a - diff;
    nex_a += N;
    nex_a %= N;
    pat[nex_a]++;
  }
  
  // すべての組み合わせから、平行な組み合わせを差し引く
  let ans = M * (M - 1) / 2;
  for (let i = 0; i < N; i++) {
    ans -= pat[i] * (pat[i] - 1) / 2;
  }

  console.log(ans);
}

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

まとめ

E問題は$2^NX$の$DP$テーブルを構築するアイデア自体はすぐにわかりましたが、期待値の漸化式をうまく立てることができませんでした。
最近は精進する時間が出てきたので、ABC394 F - Alkaneや、ABC401 F - Add One Edge 3など解く時間がなく放置していた問題をupsolveしました。グラフや細かく丁寧に場合分けする問題が苦手だという自分の弱点がよくわかってきたので、ぜひ克服したいと思います。

今回のC問題のように、苦手な領域を一つずつ潰していって解ける問題を増やしていくというアルゴリズムで、今日もABC403をかんばります。