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

AtCoder Beginner Contest 403

ABCDの4完（47分1ペナ）でした。
1288perfでレートは1043->1070（+27）となりました。
今回はA〜Dをまとめます。

A - Odd Position Sum

$A$のうち奇数番目の総和を求めるということですが、JavaScriptをはじめとする多くのプログラミング言語では配列番号を1からではなく0から数えます。
そのため、$A$の奇数番目は$A_0,A_2,A_4,...,A_{2k}$のように偶数の配列番号に対応します。
したがって、$A$の要素のうち配列番号が偶数であるものの総和を求めれば良いです。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);
  let ans = 0;
  for (let i = 0; i < N; i++) {
    if (i % 2 === 0) ans += A[i];
  }
  console.log(ans);
}

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

B - Four Hidden

二通りの解法があります。
一つ目は、4つの?にありうる英小文字を全て代入してみる方法です。
例えば$T=$????、$U=$zzzzとします。このとき、$T$の候補としてはaaaa〜zzzzまでの$26^4=456976$通りあります。この候補全てについて、部分文字列として$U$を含むかどうかを文字列の開始位置で全探索します。
$σ=26$とおくと、計算量は$O(σ^4|T|)$で十分高速にこの問題を解くことができます。

• 解法1

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const T = input[0];
  const U = input[1];
  let st = [];
  for (let i = 0; i < T.length; i++) {
    if (T[i] == "?") st.push(i);
  }

  // "?"の位置に英小文字を代入して全探索
  let [a, b, c, d] = [st[0], st[1], st[2], st[3]];
  for (let i = 0; i < 26; i++) {
    for (let j = 0; j < 26; j++) {
      for (let k = 0; k < 26; k++) {
        for (let l = 0; l < 26; l++) {
          let str = T.split("");
          str[a] = String.fromCharCode(97 + i);
          str[b] = String.fromCharCode(97 + j);
          str[c] = String.fromCharCode(97 + k);
          str[d] = String.fromCharCode(97 + l);
          str = str.join("");
          
          // strの部分文字列にUが含まれている場合"Yes"を出力
          for (let m = 0; m < T.length; m++) {
            if (m + U.length <= T.length) {
              if (str.slice(m, m + U.length) == U) return console.log("Yes");
            }
          }
        }
      }
    }
  }
  console.log("No");
}

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

二つ目は、$U$の?以外が一致していたら$T$が$U$の部分文字列に含むことがわかる方法です。
例えば、$T=$a?c?d??に対して$U=$coderとします。このとき、$T$にはc?d??という部分文字列がありますが、二番目の?にo、四番目・五番目の?にerを代入するとcoderという文字列を構築でき、これは$U$に一致します。
これは解法1に比べて計算量を大きく改善して$O(|T||U|)$で解くことができます。

• 解法2

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const T = input[0];
  const U = input[1];
  for (let i = 0; i < T.length; i++) {
    if (i + U.length > T.length) break;
    let f = true;
    for (let j = 0; j < U.length; j++) {
      if (T[i + j] !== U[j] && T[i + j] !== "?") f = false;
    }
    if (f) return console.log("Yes");
  }
  console.log("No");
}

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

C - 403 Forbidden

クエリ1,3だけであれば、各ユーザが閲覧できるページのハッシュセット$\text{canView}$を作成し、$\text{query}=$[1 x y]に対しては$\text{canView}[x]$にページ$y$を追加、$\text{query}=$[3 x y]に対しては$\text{canView}[x]$にページ$y$があるかを確認すれば、各クエリの計算量は$O(1)$のため簡単に解くことができます。

しかし、全てのページを許可するというクエリ2があるため、$\text{canView}[x]$にページ$1〜M$まで全て追加するという愚直解法では$O(QM)$となりTLEする可能性が高いです。
そこで、新たにユーザーが全てのページを閲覧できるかどうかのフラグ$\text{canViewAll}$を作成します。そうすれば、$\text{query}=$[2 x]に対しては$\text{canViewAll}[x]=$trueに設定し、$\text{query}=$[3 x y]に対しては

• $\text{canViewAll}[x]=$trueまたは$\text{canView}[x]$にページ$y$があれば閲覧可能
• それ以外は閲覧不可

という判定方法で各クエリの計算量を$O(1)$に抑えることができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M, Q] = input[0].split(" ").map(Number);
  const query = [];
  for (let i = 0; i < Q; i++) query.push(input[i + 1].split(" ").map(Number));
  const canViewAll = new Array(N + 1).fill(false);
  const canView = new Array(N + 1).fill(0).map(() => new Set());

  const ans = [];
  for (let i = 0; i < Q; i++) {
    const [q, x, y] = query[i];
    if (q === 1) canView[x].add(y);
    else if (q === 2) canViewAll[x] = true;
    else {
      if (canViewAll[x] || canView[x].has(y)) ans.push("Yes");
      else ans.push("No");
    }
  }
  console.log(ans.join("\n"));
}

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

D - Forbidden Difference

まず、$D=0$のときは$A$に同じ要素が残らないようにしなければならないので、答えは$N-[Aの要素の種類数]$です。

次に、$D>0$のときを考えます。
問題文が数学的で少しややこしいのですが、要するに$[x, x+D]$のようなペアが存在しないような配列を、できるだけ削除回数を抑えつつ$A$から要素を削除して作成しろということです。
この言い換えを頼りに、次のような仮説を立ててみます。

• 仮説１：$[x,x+D]$のペアを見つけ、必要となる削除回数が少ない方を貪欲に削除する

結論から言うとこの解法は誤りです。
具体例を見てみましょう。

例1) D=2, A=[1,1,3,4]
Aに[1,3]のペアが含まれているため、1か3のどちらかを削除する必要がある
・1を削除する場合：Aに1は二つ含まれているため2つの要素を消す
・3を削除する場合、Aに3は一つしかないので1つの要素を消す
↓
3を削除した方が削除回数を少なく抑えられるので、3を削除した場合の`1`を出力

この例では、$A$に含まれる$[x, x+D]$のペアを一つずつ見ていって、出現回数の少ない方を削除するという貪欲法で解くことができました。
では、他の例で実験してみましょう。

例2) D=2, A=[1,3,3,5,5]
Aに[1,3]と[3,5]の二種類ペアが含まれている
・[1,3]について着目すると、1を削除することで1回の削除回数で済む
・[3,5]について着目すると、3と5どちらを削除しても2回の削除回数がかかる
よって合計の3を出力？？？

貪欲法だと答えが$3$となりますが、この場合明らかに$3$を削除することで$2$回の削除回数で$A$から$[x,x+D]$のペアがなくなるため誤りということがわかります。

一般化すると、$A$の中に$x, x+D, x+2D,..., x+kD$のように$D$間隔で要素が存在する時に貪欲法が通用しないということです。
続いて、次の仮説を考えてみましょう。

• 仮説２：$x, x+D, x+2D,..., x+kD$のグループについて$k$の偶奇でグループ分けし、少ない方のグループを削除する

$x, x+2D, x+4D,...$と$x+D, x+3D, x+5D,...$のグループに分けるということですが、これも結論から言うと誤りです。
確かに、このように分けてどちらかのグループを全て削除することで$[x,x+D]$のペア自体はなくなりますが、以下のような例で正しく答えを出力できません。

例3) D=2, A=[1,1,3,5,7,7,7]
・偶数グループ(1,5)：3回の削除回数が必要
・奇数グループ(3,7)：4回の削除回数が必要
よって偶数グループの3を出力？？？

上記の例だと$3$が答えとなってしまいますが、実は$3,5$を削除することで$2$回の削除回数で$[x,x+D]$のペアをなくすことができます。

偶奇でのグループ分けもできないなら、もはや打つ手なしだと思われる方もいるかもしれませんが、実はDP（動的計画法）というテクニックを知っていれば次の仮説に辿り着くことができます。この仮説こそが今回の正解解法です。

• 仮説３（正解解法）：$x, x+D, x+2D,..., x+kD$について、$[x,x+D]$のペアを含まない要素の選び方のうち、残る要素数の最大値を動的計画法によって求める。それを$x, x+D, x+2D,..., x+kD$の要素の合計数から差し引いたものが削除する要素数の最小値である

ここで、DPテーブルを次のように定めます。

$$dp[i][j]:=x, x+D, x+2D,..., x+kDをi=kまで見て、j=0のときi番目の要素を選択しない、j=1のとき選択する行動を取った時に残る要素数の最大値$$

このDPテーブルの遷移としては二種類あり、

• $dp[i][0]=\text{max}(dp[i-1][0],dp[i-1][1])$
• $dp[i][1]=dp[i-1][0]+\text{freq}[x+iD]$

です。なお、$\text{freq}[x]$は$x$の出現回数を表します。
$i$番目で要素を選択しない場合は$i-1$番目で要素を選んだか選んでないかに関わらず大きい方を選択できますが、$i$番目で要素を選択する場合は$i-1$番目で要素を選んでいない必要があるためこのような遷移となります。

参考として、$D=2, A=[1,1,3,5,7,7,7]$の場合における遷移の流れを示します。

$x+kD$	1	3	5	7
$A$内の$[x+kD]$の出現回数	2	1	1	3
$dp[i][0]$	0	2	2	3
$dp[i][1] $	2	1	3	5
$\text{max}(dp[i][0],dp[i][1])$	2	2	3	5

以上より、$[x,x+D]$のペアを含まない選び方としては要素数が最大$5$個残るものがあるため、全体の$7$から$5$を引いた結果の$2$がこの例における削除回数の最小値となります。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, D] = input[0].split(" ").map(Number);
  const A = input[1].split(" ").map(Number);
  const max = 10 ** 6 + 1;
  const freq = new Array(max).fill(0);
  for (let i = 0; i < N; i++) freq[A[i]]++;
  const seen = new Array(max).fill(false);
  
  // D=0のとき、Aの要素の種類数が答え。N-new Set(A).sizeでも良い
  if (D == 0) return console.log(N - freq.filter((x) => x > 0).length);

  let ans = 0;
  for (let i = 0; i <= max; i++) {
    // 一度見た要素や、出現回数が0の要素はスキップ
    if (seen[i]) continue;
    if (freq[i] == 0) continue;

    // i, i+D, i+2D, ... のグループを見つける
    let st = [];
    let j = i;
    let sum = 0;
    while (j <= max && freq[j] > 0) {
      st.push(j);
      seen[j] = true;
      sum += freq[j];
      j += D;
    }
  
    // dp[i][j]:= stのi番目まで見たとき、j=0なら選択しない、j=1なら選択するとしたときに残る要素数の最大値
    let dp = new Array(st.length + 1).fill(0).map(() => new Array(2).fill(-Infinity));
    dp[0][0] = 0;
    for (let k = 1; k <= st.length; k++) {
      dp[k][0] = Math.max(dp[k - 1][0], dp[k - 1][1]);
      dp[k][1] = dp[k - 1][0] + freq[st[k - 1]];
    }
    
    let res = Math.max(dp[st.length][0], dp[st.length][1]);
    // Σfreq - resとすれば、削除する要素数の最小値となる
    ans += sum - res;
  }

  console.log(ans);
}

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

まとめ

E問題は想定解のTrie木が未履修なので厳しいものがありました。
コンテスト後にRolling Hashでゴリゴリ解いてみてはみましたがWAが取れないので多分ハッシュ衝突でもしてるんですかね？

とはいえ、今回は緑と水のボーダーラインあたりの難易度のD問題を比較的早く解けたのはよかったです。
仮説→検証→仮説の改善→検証→…という仮説検証のサイクルを回せたことと、丁寧に場合分けをする意識をきちんと持てたことが今回の勝ちにつながったのだと思います。

来週も頑張ります！