# AtCoder Beginner Contest 312 参加記録 A-D **公開日**: 2023-07-30T00:57:04+09:00Z **カテゴリー**: Diary **タグ**: プログラミング --- 今週もAtCoder Beginner Contest 312に参加をしました。 ## **結果** A-Dの4完、Cで1ペナでした。 これから振り返ります。 Qlitreさんのユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)での成績：1628位 パフォーマンス：1294相当 レーティング：1027→1057 (+30) :) Highestを更新しました！[#AtCoder](https://twitter.com/hashtag/AtCoder?src=hash&ref_src=twsrc%5Etfw) (ABC312) [https://t.co/g4xnnSCl5m](https://t.co/g4xnnSCl5m) — Qlitre (@kuri_tter) [July 29, 2023](https://twitter.com/kuri_tter/status/1685292859447267328?ref_src=twsrc%5Etfw) B問題が重実装で、時間を多く使ってしまいましたが、最終的にD問題まで解けたので満足ができました。 早速振り返っていきたいと思います。 ## **A - Chord** [https://atcoder.jp/contests/abc312/tasks/abc312_a](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](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](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](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が何も分からず、ここからの壁が高いなーと感じています。 ちょっとブレークスルーしないとスコアが頭打ちになるような感覚もあります。 引き続き頑張ります。ではでは。