Home / Python /

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

投稿日：　 更新日：2023/10/16

Atcoder Python

B!
Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, 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型に含まれるかを判定すればよいです.

if input() in {"ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"}:
print("Yes")
else:
print("No")
view raw atcoder-abc-312-a.py hosted with ❤ by GitHub

B - TaK Code

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

  • 左上の縦3マス, 横3マスの領域は全て黒である.
  • 右下の縦3マス, 横3マスの領域は全て黒である.
  • 左上に接する7マスの領域は全て白である.
  • 左右下に接する7マスの領域は全て白である.
def TaK_code_check(grid, offset_i, offset_j):
"""以下がTaK Codeの条件を満たすかを返す
上からoffset_i行目、左からoffset_j列目を左上とする縦9マス横9マスの領域
Args:
grid (list[list[bool]]): 調査対象を含む領域
offset_i (int): 左上の座標i
offset_j (int): 左上の座標j
Returns:
bool: 調査結果 TrueならばTaK Codeの条件を満たす
"""
# 左上の縦3マス、横3マスの領域は全て黒である
for ii in range(3):
for jj in range(3):
if not grid[offset_i + ii][offset_j + jj]:
return False
# 右下の縦3マス、横3マスの領域は全て黒である
for ii in range(6, 9):
for jj in range(6, 9):
if not grid[offset_i + ii][offset_j + jj]:
return False
# 左上に接する7マスの領域は全て白である
for jj in range(3):
if grid[offset_i + 3][offset_j + jj]:
return False
for ii in range(3):
if grid[offset_i + ii][offset_j + 3]:
return False
# 右下に接する7マスの領域は全て白である
for jj in range(5, 9):
if grid[offset_i + 5][offset_j + jj]:
return False
for ii in range(5, 9):
if grid[offset_i + ii][offset_j + 5]:
return False
return True
# 入力
N, M = map(int, input().split())
S = [[s == "#" for s in list(input())] for _ in range(N)]
# 出力
for i in range(N - 8):
for j in range(M - 8):
if TaK_code_check(S, i, j):
print(i + 1, j + 1)
view raw atcoder-abc-312-b.py hosted with ❤ by GitHub

C - Invisible Hand

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

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

import bisect
def count_seller(selling_price_list, price):
"""price円で売ってもよいと考える売り手の人数を返す
Args:
selling_price_list (list[int]): ある売り手が売ってもよいと考える値段のリスト(昇順ソート済み)
price (int): 金額
Returns:
int: 人数
"""
return bisect.bisect_right(selling_price_list, price)
def count_buyer(buying_price_list, price):
"""price円で買ってもよいと考える買い手の人数を返す
Args:
selling_price_list (list[int]): ある買い手が買ってもよいと考える値段のリスト(昇順ソート済み)
price (int): 金額
Returns:
int: 人数
"""
return len(buying_price_list) - bisect.bisect_left(buying_price_list, price)
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort()
# 二分探索をして、問題の金額を求める
low = 0
high = 10000000000
while high - low > 1:
mid = low + (high - low) // 2
if count_seller(A, mid) >= count_buyer(B, mid):
high = mid
else:
low = mid
# 出力
print(high)
view raw atcoder-abc-312-c.py hosted with ❤ by GitHub

D - Count Bracket Sequences

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

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

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

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

  • dpi,j：i文字目までにある?を(あるいは)に置き換える方法の数. ただし, 以下を満たす方法である.
    • 任意のk≤iに対し, k文字目までに含まれる(の個数が)の個数以上である.
    • (i文字までの(の個数) − (i文字までの)の個数) =jとなる.

初期条件として, dp0,0=1とします. iとjは0からNまでの範囲で考えます.

dpi,jは, dpi−1,0,dpi−1,1,…,dpi−1,Nに依存します. その依存の仕方は, Sのi文字目に応じて以下のようになります.

  • Si=(の場合：(の数が増えるので……
    • dpi,j+1 += dpi−1,j
  • Si=)の場合：)の数が増えるので……
    • dpi,j−1 += dpi−1,j
  • Si=?の場合：(の数が増える場合と)の数が増えるの両方を考慮して……
    • dpi,j+1 += dpi−1,j
    • dpi,j−1 += dpi−1,j

最終的にdpN,0が求める答えです.

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

# 入力
S = list(input())
N = len(S)
MOD = 998244353
# dp_ij：i文字目までにある?を(あるいは)に置き換える方法
# ・任意のk <= iに対し、k文字目までに含まれる(の個数が)の個数以上である
# ・（i文字までの ( の個数）−（i文字までの ) の個数）=jとなる
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0] = 1
# dpを計算して埋めていく
for i in range(N):
if S[i] == "(":
for j in range(N - 1):
dp[i + 1][j + 1] += dp[i][j]
elif S[i] == ")":
for j in range(1, N):
dp[i + 1][j - 1] += dp[i][j]
else:
for j in range(N - 1):
dp[i + 1][j + 1] += dp[i][j]
for j in range(1, N):
dp[i + 1][j - 1] += dp[i][j]
# 出力
print(dp[N][0] % MOD)
view raw atcoder-abc-312-d.py hosted with ❤ by GitHub

E以降

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

参考にしたサイト等