AtCoder Beginner Contest 312 参加記録 A-D

2023年07月30日

今週もAtCoder Beginner Contest 312に参加をしました。

結果

A-Dの4完、Cで1ペナでした。

これから振り返ります。
Qlitreさんのユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)での成績：1628位
パフォーマンス：1294相当
レーティング：1027→1057 (+30) :)
Highestを更新しました！#AtCoder (ABC312) https://t.co/g4xnnSCl5m
— Qlitre (@kuri_tter) July 29, 2023

B問題が重実装で、時間を多く使ってしまいましたが、最終的にD問題まで解けたので満足ができました。

早速振り返っていきたいと思います。

A - Chord

https://atcoder.jp/contests/abc312/tasks/abc312_a

文字列が与えられて、ACE、BDF、CEG、DFA、EGB、FAC、GBDのいずれかと等しい時にYesと答える問題です。

意味ありげな文字に見えますが、単純に６文字を集合に入れて含まれているかで判定をしました。

a_set = set(['ACE', 'BDF', 'CEG', 'DFA', 'EGB', 'FAC', 'GBD'])
 
s = input()
if s in a_set:
    print('Yes')
else:
    print('No')

B - TaK Code

https://atcoder.jp/contests/abc312/tasks/abc312_b

高橋君は以下のような、2 次元コード TaK Code を考案しました。

縦9マス横9マスの領域である
左上及び右下の縦3マス横 3マスの領域に含まれる計18マスは全て黒である
左上及び右下の縦3マス横3マスの領域に八方位で隣接する計14マスは全て白である

グリッドの情報が与えられるので、Tak Codeが含まれる領域の左上のポジションを全て出力する、という問題です。

縦横の制約が100までと小さいので、全探索すれば解けそうですが、Tak Codeのチェックが少し面倒そうです。

タックコードは図にすると以下のような形です。

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

コンテスト中は、以下のようなチェック関数を書きました。

def check(grid):
    # 左上が3x3マスが黒か確認
    for i in range(3):
        for j in range(3):
            if grid[i][j] != '#':
                return False
    # 右下の3x3マスが黒か確認
    for i in reversed(range(6, 9)):
        for j in reversed(range(6, 9)):
            if grid[i][j] != '#':
                return False
    # 左上と右下の黒の周りが白か確認
    for i in range(4):
        if grid[3][i] != '.':
            return False
        if grid[i][3] != '.':
            return False
        if grid[5 + i][5] != '.':
            return False
        if grid[5][5 + i] != '.':
            return False
    return True

テストコードでバグらせながらも、なんとかACができました。

解説を見て、Tak Codeをコピって判定に使うという方法があり、なんでコンテスト中に気づけなかったんだろう、と愕然をしました。

Tak Codeをコピってしまうと、?以外のところが一致するか判定すればよいので、かなり実装が楽になります。

def check(grid):
    tak_code = [
        '###.?????',
        '###.?????',
        '###.?????',
        '....?????',
        '?????????',
        '?????....',
        '?????.###',
        '?????.###',
        '?????.###',
    ]
    for i in range(9):
        for j in range(9):
            if tak_code[i][j] == '?':
                continue
            if tak_code[i][j] != grid[i][j]:
                return False
    return True


def solve():
    h, w = map(int, input().split())
    ans = []
    grid = [list(input()) for _ in range(h)]
    for i in range(h):
        for j in range(w):
            # 下端
            new_i = i + 8
            # 右端
            new_j = j + 8
            if new_i <= h - 1 and new_j <= w - 1:
                # gridを新しく作る
                new_grid = []
                for ii in range(i, new_i + 1):
                    tmp = []
                    for jj in range(j, new_j + 1):
                        tmp.append(grid[ii][jj])
                    new_grid.append(tmp)
                # 条件を満たしていたら答えに加える
                if check(new_grid):
                    ans.append([i + 1, j + 1])

    for a in ans:
        print(*a)


if __name__ == '__main__':
    solve()

C - Invisible Hand

https://atcoder.jp/contests/abc312/tasks/abc312_c

N人のりんごをある価格以上で売りたい人とM人のある価格以下で買いたい人がいます。

売りたい人の数が買いたい人の数を上回るような最小の金額を求める、という問題です。

ある価格が基準になっているときに、売れる人数と買える人数を計算するのは簡単です。

それぞれの配列を走査して、売りたい人の数は、ある価格が売りたい金額以上なら＋１。

買いたい人の数はある価格が買いたい金額以下なら＋１とすればいいです。

ただ、価格を全探索すると、当然間に合わないです。

答えで二分探索をしながら確認を行っていきます。

def check(price, uri, kai):
    cnt_sell = 0
    cnt_buy = 0
    for u in uri:
        if u <= price:
            cnt_sell += 1
    for k in kai:
        if price <= k:
            cnt_buy += 1
    return cnt_sell >= cnt_buy


def solve():
    n, m = map(int, input().split())
    sell = list(map(int, input().split()))
    buy = list(map(int, input().split()))

    ng, ok = 0, 10 ** 10
    while ok - ng > 1:
        mid = (ng + ok) // 2
        if check(mid, sell, buy):
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == '__main__':
    solve()

D - Count Bracket Sequences

https://atcoder.jp/contests/abc312/tasks/abc312_d

文字列 S は (, ), ? からなる空でない文字列として与えられます。? の数を x としたとき、? を(または)に置き換えて新しい文字列を作る。この中で、新しい文字列が括弧列となるような置き換え方の数を求める、という問題です。

文字列の長さが3000までと比較的小さいので、凄くDPという感じがします。

DP[i][j] = i番目までの文字を見ているときに、j個(が開いている通り数としました。

まず文字が何もない、dp[0][0]は１です。

そこから順番に見ていって…

(だった時には一個開いている数を増やせるので、dp[i+1][j+1]+=dp[i][j]

)だった時には開いている数を一個減らせるので、dp[i+1][j-1]+=dp[i][j]

?だったらどっちもできる、というようにします。

最終的には開いている(の数はゼロでないといけないので、dp[n][0]が答えです。

def solve():
    s = input()
    n = len(s)
    mod = 998244353
    # dp[i][j]: i番目までの文字で開いている'('の数がj個
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(n):
        for j in range(i + 1):
            # 1個開きを増やせる
            if s[i] == '(' or s[i] == '?':
                dp[i + 1][j + 1] += dp[i][j]
                dp[i + 1][j + 1] %= mod
            # 1個閉じれる
            if s[i] == ')' or s[i] == '?':
                if j > 0:
                    dp[i + 1][j - 1] += dp[i][j]
                    dp[i + 1][j - 1] %= mod
    # 一個も開いているのがないのが答え
    print(dp[n][0])


if __name__ == "__main__":
    solve()

おわりに

D問題までは比較的スムーズに解くことができたのでよかったです。

ただ、E,Fが何も分からず、ここからの壁が高いなーと感じています。

ちょっとブレークスルーしないとスコアが頭打ちになるような感覚もあります。

引き続き頑張ります。ではでは。

記事一覧へ