AtCoder Beginner Contest 386

ABCDの4完（58分2ペナ）でした。
1212perfでレートは938->969（+31）となりました。
C問題まで13分でACできていましたが、D問題で真の解法を思いつくまでにかなり時間を浪費してしまったため、そこまでの上振れとはなりませんでした。とはいえ、一年を締めくくるコンテストで水色perfは嬉しいものです。

今回はコンテスト中に解けたA~Dをまとめます。

A - Full House 2

あと1枚カードを何か追加すればフルハウスになるようなカードの組み合わせを考えます。
まずは具体例で考えてみましょう。

カードの手持ち	種類数	パターン	フルハウスにできるか？
$1,1,1,1$	1	${x: 4}$	`No`
$1,1,2,2$	2	${x: 2, y: 2}$	`Yes`
$1,2,2,2$	2	${x: 1, y: 3}$	`Yes`
$1,2,3,3$	3	${x: 1, y: 1, z: 2}$	`No`
$1,2,3,4$	4	${x: 1, y: 1, z: 1, w: 1}$	`No`

具体例を考えるとわかりやすいですね。たとえば種類数が$1$の場合を考えると、すでに挙がっている数字を加えると5カードになり、挙がっていないカードを加えると4カードになります。したがって、この場合はどのカードを追加してもフルハウスになりえません。

他のパターンについても同様に考えた結果、種類数が$2$の時に限りフルハウスとなる可能性がある、かつ種類数が$2$でありながらフルハウスにならない組み合わせはありえないことがわかります。

したがって、$A,B,C,D$の入力をそのままsetに追加して重複を排除し、setの大きさが$2$のときにだけYesを出力、それ以外はNoを出力することでこの問題をACできます。

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

  // 持っているカードを全てsetに追加する
  const set = new Set([A, B, C, D]);

  // 実は持っているカードの種類数が2ならフルハウスになる
  if (set.size == 2) console.log("Yes");
  // 種類数が2ではない場合はフルハウスにならない
  else console.log("No");
}

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

B - Calculator

左から文字列$S$を作成するシミュレーションを行うことでこの問題を解くことができます。
もし2回連続して0が現れる場合（00がある場合）はそれを$1$カウントとみなしてボタンを押す総回数を数え上げれば良いです。

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

  let ans = 0;
  for (let i = 0; i < S.length; i++) {
    ans++;
    // i番目とi+1番目が0の場合は00として1回で処理できる
    if (i < S.length - 1 && S[i] === "0" && S[i + 1] === "0") i++;
  }
  console.log(ans);
}

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

C - Operate 1

$S$と$T$の文字列の長さの差で場合分けして、以下の条件を満たす場合Yes、それ以外は全てNoです。

$|S|=|T|$のとき、「何もしない」か「$S$を適当に$1$文字だけ変更する」と$T$に一致する
$|S|=|T|+1$のとき、「$S$の適当な位置から$1$文字だけ文字を削除する」と$T$に一致する
$|S|=|T|-1$のとき、「$S$の適当な位置に$1$文字だけ文字を追加する」と$T$に一致する

$|S|=|T|$のとき

$S$と$T$の長さは同じなので、「$cnt := SとTが何文字異なるか$」を数えましょう。
もし、$cnt=0$であれば$0$文字分だけ異なる、すなわち$S$と$T$は最初から一致します。
また、$cnt=1$であれば$1$文字分だけ異なるため、$1$文字修正したら済みます。
$cnt>1$のときは$2$回以上の修正が必要となるためNGです。

|S|=|T|のとき
      ↓ ↓ 2箇所一致しないため、cnt=2>1となりNG
S    abc386
T    arc086

$|S|=|T+1|$のとき

$S$と$T$の長さが異なる場合には、文字列の参照の仕方を少し工夫する必要があります。
この場合は$S$の方が$T$よりも$1$文字分だけ長いためどこかで$S$から$1$文字だけ削除する必要があるのですが、それを「$S$だけ$1$進めて、$T$はその位置にとどまる」と読み替えましょう。
「$cnt := Sから何文字削除したか$」とすれば、$S[i]=T[i-cnt]$で比較することができます。また、$cnt>1$のとき$1$回以上の削除が必要となるためNGです。

|S|=|T+1|のとき
        ↓ ここでcnt=1とすれば、次の比較でS[4]=T[4-cnt]として辻褄があう
S    abc386
T    abc86

$|S|=|T-1|$のとき

考え方は、「$|S|=|T+1|$のとき」と同じです。$T$から$1$文字だけ削除するのを「$T$だけ$1$進めて、$S$はその位置にとどまる」と読み替えましょう。
「$cnt := Tから何文字削除したか$」とすれば、$S[i- cnt]=T[i]$で比較することができます。また、$cnt>1$のとき$1$回以上の削除が必要となるためNGです。

|S|=|T-1|のとき
        ↓ ここでcnt=1とすれば、次の比較でS[4-cnt]=T[4]として辻褄があう
S    abc386
T    abc0386

以上で、どの場合でも$O(\text{max}(|S|,|T|))$でこの問題を解くことができました。

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

  // cnt := 追加または削除または変更の回数
  let cnt = 0;
  // SとTの長さが等しい場合は変更の回数のみカウントして1回以下で等しくできるならYes
  if (S.length == T.length) {
    for (let i = 0; i < S.length; i++) if (S[i] !== T[i]) cnt++;
    if (cnt <= K) return console.log("Yes");

    // SがTより1文字多い場合はSから1文字削除した回数のみカウントして、1回で等しくできるならYes
  } else if (S.length == T.length + 1) {
    for (let i = 0; i < S.length; i++) {
      // cnt分だけTの参照位置を前にずらせば継続して比較できる
      if (S[i] !== T[i - cnt]) cnt++;
    }
    if (cnt == K) return console.log("Yes");

    // SがTより1文字少ない場合はSに1文字追加した回数のみカウントして、1回で等しくできるならYes
  } else if (S.length + 1 == T.length) {
    for (let i = 0; i < T.length; i++) {
      // cnt分だけSの参照位置を前にずらせば継続して比較できる
      if (S[i - cnt] !== T[i]) cnt++;
    }
    if (cnt == K) return console.log("Yes");
  }

  // 上記の条件に当てはまらない場合はNo
  console.log("No");
}

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

D - Diagonal Separation

まずは問題文をよく理解しましょう。
この問題は、白いマスの左上に黒いマスが存在する場合に矛盾が生じるためNoを出力し、矛盾なく全てのクエリを処理できたらYesを出力します。なお、左上というのは真上と真左を含みます。
（筆者は逆にマスの左上を見ずに真上と真左だけを見て30分以上ロスしました）

具体例を見ましょう。以下のような場合はOKです。

*:指定のないマス B:黒で指定されたマス W: 白で指定されたマス

***B*
B*BW*
*W***
W***W

逆にNG例は以下のような場合です。

*:指定のないマス B:黒で指定されたマス W: 白で指定されたマス
例1
***B*
W*BW* ← (2,3)のBの真左にWがある
*W***
W***W

例2
**WB*
B*BW* ← (2,3)のBの真上にWがある
*W***
W***W

例3
W**B*
B*BW* ← (2,3)のBの左上にWがある
*W***
W***W

このようなNGを検出する方法を考えましょう。まず咄嗟に思いつきそうなのは以下の二つでしょうか。

ダメそうな解法その1

まず愚直に黒で指定された各マスについて、「左上に白で指定されたマスがあるか」を1マスずつしらみつぶしに全探索で確認する方法が挙げられますが、マス目は$N^2$の平面のため$O(N^2)$です。今回は$N≦10^9$という大きめな制約のためこれでは間に合わなさそうです。

左上のマスを全探索

*****………***
*****………***
**B**………***
…
*****………*B* ←左上に広大なマスが広がる場合は時間がかかりすぎる。O(N^2)

ダメそうな解法その2

次に、1マスずつではなく左上の「指定のあるマス」だけ見ていく方法が挙げられますが、うまく左上の指定マスだけを高速に抽出できたとしても、以下のように左上から右下へとマスを指定するようなケースで最悪計算量$O(M^2)$となり、$M≦10^5$のためこれも厳しそうです。

左上の「指定のあるマス」だけ全探索
最悪な例（左上から右下へと指定マスが存在するようなケース）

B****
*B***
**B**
…

(n,n)のマスでは、(1,1)~(n-1,n-1)のマスの色を全てを確認する必要がある。O(M^2)

ではどうするかですが、この問題の着眼点としてはマスの色を指定する順番は、矛盾なくマスを塗り分けられるかの答えには影響しないということが重要です。
つまり、マスの色の指定（以下クエリと呼びます）をどう並び替えても答えは変わりません。
もしクエリをうまく並び替えることによって高速に矛盾判定ができるとするならば、どんな風に並び替えればよいかを考えましょう。

先ほどのNG例を観察すると、矛盾検出に必要な情報は「
min_i_w $:= 今見ているクエリと同じ列か左側の列にある白マスのy座標の最小値$」であることがわかります（$y$座標の値は下に向かって大きくなることに注意）。
ということは、左から右、同じ列の場合は上から下の順番にクエリを見ていき、その過程でmin_i_wを保持できていれば良さそうですね。

なぜなら、min_i_wは過去に見た白マスを表すので今のクエリと同じかそれより左にあることが保証されています。その上で、今見ているクエリよりもmin_i_wが小さい（上の位置にある）のであれば、過去に見た白マスは今のクエリよりも必ず左上にあることが検出できます。

したがって、以下の順に実装すればこの問題はソートがボトルネックとなり$O(MlogM + M)$で解くことができます。

クエリを行の昇順でソートする
クエリを列の昇順でソートする
クエリを順番に処理する

「今見ているクエリの色が黒」かつ、「今見ているクエリのy座標がmin_i_wよりも小さい」場合にNoを出力し終了する
「今見ているクエリの色が白」かつ「今見ているクエリのy座標がmin_i_wよりも小さい」ならばmin_i_wを更新する

矛盾なく全てのクエリを処理し切ればYesを出力する

このように、愚直に全探索すると$O(M^2)$となるような問題で、適切にクエリを並び替えることでメイン部分の計算量を$O(M)$に落とし込むようなアルゴリズムを総称して平面走査といいます。平面走査について興味のある方は調べてみてください。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, M] = input[0].split(" ").map(Number);
  let [X, Y, C] = [[], [], []];
  for (let i = 0; i < M; i++) [X[i], Y[i], C[i]] = input[i + 1].split(" ");
  [X, Y] = [X.map(Number), Y.map(Number)];
  let tile = [];
  for (let i = 0; i < M; i++) tile.push([X[i] - 1, Y[i] - 1, C[i]]);

  // y軸の昇順、x軸の昇順でソートする
  tile.sort((a, b) => a[1] - b[1]);
  tile.sort((a, b) => a[0] - b[0]);

  // min_i_w := 今まで見てきたマスの中で、最も左上にある白マスのy座標
  let min_i_w = N;

  // 左の列から順に、同じ列の中で上から下へマスを見ていく。
  // 下から上の順に見ていくと、真上に白マスがある場合を見逃してしまう。
  for (let i = 0; i < M; i++) {
    let [x, y, c] = tile[i];
    if (c === "B") {
      // 今黒マスを見ていて、かつ左上に白マスがある場合はNo
      if (y >= min_i_w) return console.log("No");
    // min_i_wよりも上に白マスがある場合は、min_i_wを更新する
    } else min_i_w = Math.min(min_i_w, y);
  }
  console.log("Yes");
}

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

1年を振り返って

これが今年最後の記事となるので、簡単な振り返りと謝辞を述べさせてください。

4ヶ月ほど前から毎週ABCの振り返りの記事を書くようになり、仕事の傍ら少なくない時間を費やしてプログラミングそのものの学習と記事の執筆を欠かさずに行ってきました。

結果として、記事の執筆が過度な負担となることもなく、むしろ記事執筆のために確かな知識を得ているためプラス要素の方が大きかったのではないかと考えています。実際、ABCのアルゴリズム部門のレーティング遷移ですが、入緑以降もレーティング増加の傾きがあまり衰えず線形的な成長を維持できています。

また、記事執筆の副産物として「抽象的なものの言語化」や「人に伝えるためのストーリーラインの組み立て」が私基準ですと以前よりも上達したことも収穫の一つだと感じています。

確かに記事執筆にはそこそこの労力がいるのですが、ここまで活動を継続できたのは毎回記事を見てくださる方々やいいねをつけて応援してくださる皆様のおかげです。とてもモチベーションにつながっているので本当にありがとうございます。

今後もJavaScriptで競プロを楽しむ誰かにとって有用な情報を発信していきたいと思いますので、ぜひ応援いただければ幸いです。

また来年のABC387でもお会いしましょう。
良いお年を！