ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)をPythonで解く

こんにちは, Shinoryoです.

今回はユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)を, Pythonで解いてみた結果を書き連ねていこうと思います.

UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Chord

入力された文字列が, {"ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"}のset型に含まれるかを判定すればよいです.

B - TaK Code

上から$i$行目左から$j$列目を左上とする縦$9$マス横$9$マスの領域を順番に調べていって, TaK Codeになっているかを調べればよいです. TaK Codeかを調べるには, 以下の全てを確認すればよいです.

• 左上の縦$3$マス, 横$3$マスの領域は全て黒である.
• 右下の縦$3$マス, 横$3$マスの領域は全て黒である.
• 左上に接する$7$マスの領域は全て白である.
• 左右下に接する$7$マスの領域は全て白である.

C - Invisible Hand

「$\mathrm{price}$円で売ってもよいと考える売り手の人数 $-$ $\mathrm{price}$円で買ってもよいと考える買い手の人数」を考えます. 価格が増加するに伴い, この数は単調増加します. よって, この数が$0$となる最小の$\mathrm{price}$を二分探索によって求める方針を考えます.

「$\mathrm{price}$円で売ってもよいと考える売り手の人数」は, $A_i \leq \mathrm{price}$を満たす$i$の数です. $A$をソートしておけば, これもまた二分探索によって求めることができます. 「$\mathrm{price}$円で買ってもよいと考える買い手の人数」に関しても同様です.

D - Count Bracket Sequences

解説より, 文字列$S$が括弧列であることは, 以下の2つの条件を満たすことと同値です.

1. 任意の$i$について, $S$の $i$文字目までに含まれる(の個数は)の個数以上である.
2. $S$に含まれる(の個数と)の個数は等しい.

例えば, 入力例1に関係する括弧列として紹介されている()()()と(())()は, 上記2つの条件を満たします.

そこで, 以下のような2次元配列を用いた動的計画法(dynamic programming)を考えます.

初期条件として, $\mathrm{dp}_{0, 0} = 1$とします. $i$と$j$は$0$から$N$までの範囲で考えます.

$\mathrm{dp}_{i, j}$は, $\mathrm{dp}_{i - 1, 0}, \mathrm{dp}_{i - 1, 1}, \ldots , \mathrm{dp}_{i - 1, N}$に依存します. その依存の仕方は, $S$の$i$文字目に応じて以下のようになります.

• $S_i =$(の場合：(の数が増えるので……
  • $\mathrm{dp}_{i, j + 1}$ += $\mathrm{dp}_{i - 1, j}$
• $S_i =$)の場合：)の数が増えるので……
  • $\mathrm{dp}_{i, j - 1}$ += $\mathrm{dp}_{i - 1, j}$
• $S_i =$?の場合：(の数が増える場合と)の数が増えるの両方を考慮して……
  • $\mathrm{dp}_{i, j + 1}$ += $\mathrm{dp}_{i - 1, j}$
  • $\mathrm{dp}_{i, j - 1}$ += $\mathrm{dp}_{i - 1, j}$

最終的に$\mathrm{dp}_{N, 0}$が求める答えです.

この方法だと, CPython 3.11.4だとTLEですが, PyPy 3.10-v7.3.12だとACです.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)」
  Editorial - UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312)

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.