トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）
8月ABC全休
A - Raise Both Hands
が与えられ、
のみ1ならばYes、
のみ1ならNo、両方とも同じ数値ならInvalidを返します。
3つのパターンの条件分けをすることでACできます。
#ABC370 A - Raise Both Hands
L, R = map(int, input().split())
if L==1 and R==0:
print('Yes')
elif L==0 and R==1:
print('No')
else:
print('Invalid') 提出リンク：提出 #57504516 - トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）
B - Binary Alchemy
今所持している元素と次にもってくる元素を保持します。
所持している元素番号と次の元素番号を比較して、小さいほうを今所持しているほうに置き換えます。
これを指示された回数繰り替えします。
#ABC370 B - Binary Alchemy
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
now = 0
for i in range(N):
nxt = i
if now < nxt:
now, nxt = nxt, now
now = A[now][nxt]-1
print(now+1) 提出リンク：提出 #57523535 - トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）
C - Word Ladder
文字を置き換えることで辞書順にどのような影響があるかを考えます。
を左から見ていって
から
に置き換えることで辞書順が改善する場合は採用、悪化する場合は据え置きとします。
の右端までいったら今度は右から左に向かってみていき、
と
が異なる場合は文字を置き換えていくこととします。
こうすることで置き換えた文字列を連結したときに辞書順が最善になります。
#ABC370 C - Word Ladder
S = input()
T = input()
N = len(S)
ans = []
now = []
for s in S:
now.append(ord(s))
for i in range(N):
if S[i] > T[i]:
now[i] = ord(T[i])
out = ''
for j in range(N):
out += chr(now[j])
ans.append(out)
for i in range(N-1, -1, -1):
if now[i] != ord(T[i]):
now[i] = ord(T[i])
out = ''
for j in range(N):
out += chr(now[j])
ans.append(out)
print(len(ans))
for a in ans:
print(a)提出リンク：提出 #57539211 - トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）
D - Cross Explosion
2次元盤面を作って愚直に試行するとTLEするので効率のいい方法を検討します。
盤面の縦方向の残存する壁位置を持った配列と、横方向の残存する壁位置を持った配列を保持することにします。
爆弾を投下する位置に壁がある場合は壁を破壊して終了。
無い場合は上下左右それぞれで一番近い壁を二分探索して破壊します。
二分探索するので配列は常に昇順を保っていたいのでSortedSetを使用します。
（sortedcontainersは配列内のランダムアクセスに弱い？のでtatyam Setを使います）
#ABC370 D - Cross Explosion
---tatyam Setを貼り付け---
def bsleft(A, N): #自身以下の最大
l = 0
r = len(A)-1
if A[r] <= N:
return r
if A[0] > N:
return -1
ans = 0
while l+1 < r:
mid = (l+r)//2
if A[mid] <= N:
ans = mid
l = mid
else:
r = mid
return ans
def bsright(A, N): #自身以上の最小
l = 0
r = len(A)-1
if A[r] < N:
return -1
if A[0] >= N:
return 0
ans = r
while l+1 < r:
mid = (l+r)//2
if A[mid] >= N:
ans = mid
r = mid
else:
l = mid
return ans
H, W, Q = map(int, input().split())
tate = [SortedSet([i for i in range(H)]) for _ in range(W)]
yoko = [SortedSet([i for i in range(W)]) for _ in range(H)]
wall = H*W
for _ in range(Q):
r, c = map(int, input().split())
r -= 1
c -= 1
if r in tate[c] or c in yoko[r]:
wall -= 1
tate[c].discard(r)
yoko[r].discard(c)
else:
if tate[c]:
lt = bsleft(tate[c], r)
if lt >= 0:
wall -= 1
bb = tate[c][lt]
tate[c].discard(bb)
yoko[bb].discard(c)
if tate[c]:
rt = bsright(tate[c], r)
if rt >= 0:
wall -= 1
bb = tate[c][rt]
tate[c].discard(bb)
yoko[bb].discard(c)
if yoko[r]:
ly = bsleft(yoko[r], c)
if ly >= 0:
wall -= 1
bb = yoko[r][ly]
yoko[r].discard(bb)
tate[bb].discard(r)
if yoko[r]:
ry = bsright(yoko[r], c)
if ry >= 0:
wall -= 1
bb = yoko[r][ry]
yoko[r].discard(bb)
tate[bb].discard(r)
print(wall)提出リンク：提出 #57559719 - トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）
