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

AtCoder Beginner Contest 407

ABCDの4完（26分0ペナ）でした。
1352perfでレートは1132->1156（+24）となりました。
今回はA〜Dの解説と、upsolveしたEの感想を記載します。

A - Approximation

実数$A/B$は、整数$\lfloor A/B \rfloor ≦ A/B <\lfloor A/B \rfloor + 1$を満たします。
したがって、$\lfloor A/B \rfloor$と$\lfloor A/B \rfloor + 1$で、$A/B$との差の絶対値が小さい方を出力すれば良いのですが、$A/B$のような割り算をしてしまうと誤差の影響で異なる答えを出力してしまうことがあります。

割り算を避けるために、各辺に$B$を掛け、$\lfloor A/B \rfloor×B ≦ A <(\lfloor A/B \rfloor + 1)×B$の形に直してから比較しましょう。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [A, B] = input[0].split(" ").map(Number);
  let floor = Math.floor(A / B);
  let ceil = floor + 1;
  let l = floor * B;
  let r = ceil * B;
  if (Math.abs(A - l) < Math.abs(A - r)) console.log(floor);
  else console.log(ceil);
}

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

B - P(X or Y)

異なるサイコロを二つ振った時、出目の出方は$36$通りあります。
出目の合計が$X$以上、または差が$Y$以下となるような出目の出方の通り数$cnt$を数えることで、二条件の和事象が起こる確率を$cnt/36$で計算することができます。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [X, Y] = input[0].split(" ").map(Number);
  let cnt = 0;
  for (let i = 0; i < 6; i++) {
    for (let j = 0; j < 6; j++) {
      if (i + j + 2 >= X || Math.abs(i - j) >= Y) cnt++;
    }
  }
  console.log(cnt / 36);
}

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

C - Security 2

$|S|≦5×10^5$と、$S$の長さは比較的大きいので、$O(|S|)$で解く方法を考えます。
この問題を解く上で重要な性質は以下の通りです：

• ボタンAは必ず$|S|$回押す
• ボタンBは既に表示されている桁のみに影響し、未表示の桁には影響しない

2点目について具体例で説明します。$S$が1234で現在の表示$t$が012の場合、ボタンBを押すと既存の各桁に+1されて123となりますが、まだ表示されていない4桁目には影響しません。

この性質を利用して、右から順番にボタンBを押す回数を決定していく貪欲法で解くことができます。

具体的には、左から$k$桁目でボタンBを押す最小回数を$b_k$として、これまでの累積B操作回数を$x=(b_{k+1}+b_{k+2}+ \cdots +b_N) \pmod{10}$として管理します。
問題文の流れの通り左から順に処理する場合、ボタンAで末尾に追加される初期値は0ですが、右から順に処理する場合、ボタンAで$x$が先頭に追加されるというふうに読み替えることができます。
このようにすると、ボタンBは今いる桁より左にしか影響しませんので、まさに$k$桁目を$S_k$に合わせるために必要なボタンBを押す回数は$b_{k}=S_k+10-x$と一意に求めることができます。

最終的な答えは、ボタンAの回数$|S|$とボタンBの回数$\sum_{k=1}^{|S|}b_k$の合計となるため、全体で$O(|S|)$で解くことができました。

どうしても数式を用いての説明となってしまったため、最後に一つ例を示します。

例)S=21のとき
t=0（ボタンAを1回押す。x=0）
↓
t=1（ボタンBを1回押す。x=1）
↓
t=11（ボタンAを1回押す。x=1）
↓
t=21（ボタンBを1回押す。x=1）

以上、ボタンAを2回、ボタンBを2回押す必要があるため、合計で4回ボタンを押す必要がある。
これは、想定解と一致する。

function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const S = input[0];
  let ans = S.length;
  let cur = 0;
  for (let i = S.length - 1; i >= 0; i--) {
    let num = Number(S[i]);
    let pl = (10 + num - cur) % 10;
    ans += pl;
    cur = (cur + pl) % 10;
  }
  console.log(ans);
}

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

D - Domino Covering XOR

JavaScriptではBigInt型のxor演算を高速に行うことができないと思っていたので、Pythonに持ち替えてACしました。
しかしながら、先ほど試してみたところ今はJavaScriptのBigIntでもxor演算が高速に行えるようで、何の問題もなくACできました。いつの間に仕様が変わったのでしょうか。

閑話休題。
この問題は制約が$HW≦20$と非常に小さく全探索ができる範囲なので、有名な問題Polyominoとほぼ同じ解き方で解くことができます。

具体的には、左上から右下に向かって一つずつマス目をみていき、

• ドミノを横に置く
• ドミノを縦に置く
• ドミノを置かない

という三通りの処理をdfsで分岐しながら行っていけばよいです。
この全探索により、全ての可能なドミノ配置を試すことができます。
厳密な計算量解析に興味のある方は公式解説を見てください。

緑色以上を目指す方へのアドバイスとして、ドミノの配置・除去処理をdfs内に直接書くのではなく、事前にメソッド化することをお勧めします。事前に宣言的な関数を用意してdfs内で呼び出すことでコードの可読性が向上し、実装ミスも減ります。

h, w = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

is_placed = [[False] * w for _ in range(h)]
def place_line (i, j):
    if j + 1 >= w:
        return False
    global is_placed
    if is_placed[i][j] or is_placed[i][j + 1]:
        return False
    is_placed[i][j] = True
    is_placed[i][j + 1] = True
    return True

def place_column (i, j):
    if i + 1 >= h:
        return False
    global is_placed
    if is_placed[i][j] or is_placed[i + 1][j]:
        return False
    is_placed[i][j] = True
    is_placed[i + 1][j] = True
    return True

def remove_line (i, j):
    if j + 1 >= w:
        return False
    global is_placed
    is_placed[i][j] = False
    is_placed[i][j + 1] = False
   
def remove_column (i, j):
    if i + 1 >= h:
        return False
    global is_placed
    is_placed[i][j] = False
    is_placed[i + 1][j] = False
    
xor_max = 0 
def dfs (i, j):
    global xor_max, is_placed
    if i >= h:
        cur_xor = 0
        for k in range(h):
            for l in range(w):
                if is_placed[k][l]:
                    continue
                cur_xor ^= a[k][l]
                
        xor_max = max(xor_max, cur_xor)
        return
    
    if j >= w:
        dfs(i + 1, 0)
        return
    
    if is_placed[i][j]:
        dfs(i, j + 1)
        return
    
    # ドミノを横に置く場合
    if place_line(i, j):
        dfs(i, j + 2)
        remove_line(i, j)
        
    # ドミノを縦に置く場合
    if place_column(i, j):
        dfs(i, j + 1)
        remove_column(i, j)
        
    # ドミノを置かない場合
    dfs(i, j + 1)
    
dfs(0, 0)
print(xor_max)

E - Most Valuable Parentheses

左から $k$番目までの(と)の個数の関係について考えると、$「(」の個数 - 「)」の個数 ≥ 0$が常に成り立つ必要があります。
この制約を考慮して、以下のような動的計画法が解法の候補として考えられます：
$$\text{dp}[i][j] := \text{左から}i\text{番目まで見て、「(の個数 - )の個数」が}j\text{となるように選んだ場合のAの総和の最大値}$$
しかし、この手法は $O(N^2)$ の計算量となるため、制約に間に合いません。

全探索や動的計画法では解けなさそうということがわかったので、貪欲法を考えます。
本番では、たとえば$N=4$のとき初期状態を(((())))のような形として、5~7番目の)を$「(」の個数 - 「)」の個数 ≥ 0$の条件を満たしながら(と交換していく方法を考えていましたが、どうしてもWAが取れずタイムアップとなりました。

想定解法は、左から$1,3,5,...,2k-1$番目までに、必ず(が$1,2,3,...,k$個含まれるという性質を利用して、(を一つずつ確定させていくという貪欲法で解くという方法で、言われてみれば簡単なのですが初見で気づくのが難しい問題でした。
最後に、流れの具体的なイメージを示します。

例)N=4、A=[1,6,7,5,3,2,8,0]のときのイメージ
※.は未確定を表す

"(" score=1　
↓
"(.(" score=8
↓
"(((.." score=14
↓
"(((...(" score=22
↓
"((()))()" score=22

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

    const pq = new PriorityQueue((a, b) => b - a);
    let max = A[0];
    for (let k = 0; k < N - 1; k++) {
      pq.add(A[2 * k + 1]);
      pq.add(A[2 * k + 2]);
      max += pq.remove();
    }
    console.log(max);
  }
}
// 以下、PriorityQueueクラスのため割愛

まとめ

D問題まで早解きに成功して青perf後半ペースだったのですが、E問題がわからず入水ならずとなりました。

AtCoder Rating Estimatorによると、次回1535perf取れば入水できるとのことなので、5完すれば十分にチャンスがあると思っています。
今日のコンテストで入水できるように頑張りたいです