0
0

More than 3 years have passed since last update.

# AtCoder Beginner Contest 185 参戦記

Last updated at Posted at 2020-12-13

# AtCoder Beginner Contest 185 参戦記

また全完のチャンスを逃してしまった、悔しい!

## ABC185A - ABC Preparation

1分で突破. 書くだけ. min を間違えて max と書いて無駄に時間を使った.

``````A = list(map(int, input().split()))

print(min(A))
``````

7分半で突破. え、これがB問題!?ってなった. とはいっても、off-by-one エラーをしないように考えながら丁寧に書いていくだけではある.

``````N, M, T = map(int, input().split())

n = N
p = 0
for _ in range(M):
A, B = map(int, input().split())
n -= A - p
if n <= 0:
print('No')
exit()
n = min(N, n + B - A)
p = B
n -= T - p
if n <= 0:
print('No')
exit()
print('Yes')
``````

## ABC185C - Duodecim Ferra

8分半で突破. L-1C11 を求めるだけなのだが、間違って LC12 で書いて無駄に時間をロストした. ダダっと掛けた後に、ダダっと割って求めたけど、int64 だと溢れちゃうんですかねえ? Python なので何も考えずに解いたけど.

``````L = int(input())

result = 1
for i in range(11):
result *= (L - 1) - i
for i in range(1, 12):
result //= i
print(result)
``````

## ABC185D - Stamp

22分で突破. WA1. M = 0 のときに0を出力するトンマをやらかした.

``````N, M, *A = map(int, open(0).read().split())

if M == 0:
print(1)
exit()

A.sort()
p = 0
intervals = []
for a in A:
t = a - p - 1
if t != 0:
intervals.append(t)
p = a
t = N - A[-1]
if t != 0:
intervals.append(t)
if len(intervals) == 0:
print(0)
exit()
k = max(min(intervals), 1)

result = 0
for x in intervals:
result += (x + k - 1) // k
print(result)
``````

## ABC185E - Sequence Matching

``````from collections import deque

def conv(i, j):
return i * 1001 + j

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 10 ** 12

dp = [INF] * (1001 * 1001)

dp[0] = 0
q = deque([(0, 0)])
while q:
i, j = q.popleft()

if i >= N:
dp[conv(N, M)] = min(dp[conv(N, M)], dp[conv(i, j)] + (M - j))
continue

if j >= M:
dp[conv(N, M)] = min(dp[conv(N, M)], dp[conv(i, j)] + (N - i))
continue

if A[i] == B[j] and dp[conv(i + 1, j + 1)] > dp[conv(i, j)]:
dp[conv(i + 1, j + 1)] = dp[conv(i, j)]
q.append((i + 1, j + 1))
continue

if dp[conv(i + 1, j + 1)] > dp[conv(i, j)] + 1:
dp[conv(i + 1, j + 1)] = dp[conv(i, j)] + 1
q.append((i + 1, j + 1))

if dp[conv(i + 1, j)] > dp[conv(i, j)] + 1:
dp[conv(i + 1, j)] = dp[conv(i, j)] + 1
q.append((i + 1, j))

if dp[conv(i, j + 1)] > dp[conv(i, j)] + 1:
dp[conv(i, j + 1)] = dp[conv(i, j)] + 1
q.append((i, j + 1))
print(dp[conv(N, M)])
``````

## ABC185F - Range Xor Query

10分で突破. 「F問題なのにこんなに簡単でいいの!? 何か見落としがある!?」ってなったくらい簡単な問題. セグ木一発.

``````from sys import stdin

class SegmentTree:
def __init__(self, size, op, e):
self._op = op
self._e = e
self._size = size
t = 1
while t < size:
t *= 2
self._offset = t - 1
self._data = [e] * (t * 2 - 1)

def __getitem__(self, key):
return self._data[self._offset + key]

def __setitem__(self, key, value):
op = self._op
data = self._data
i = self._offset + key
data[i] = value
while i >= 1:
i = (i - 1) // 2
data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

def build(self, iterable):
op = self._op
data = self._data
data[self._offset:self._offset + self._size] = iterable
for i in range(self._offset - 1, -1, -1):
data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

def query(self, start, stop):
def iter_segments(data, l, r):
while l < r:
if l & 1 == 0:
yield data[l]
if r & 1 == 0:
yield data[r - 1]
l = l // 2
r = (r - 1) // 2
op = self._op
it = iter_segments(self._data, start + self._offset,
stop + self._offset)
result = self._e
for v in it:
result = op(result, v)
return result

st = SegmentTree(N, lambda x, y: x ^ y, 0)
st.build(A)

result = []
for _ in range(Q):
T, X, Y = map(int, readline().split())
if T == 1:
st[X - 1] = st[X - 1] ^ Y
elif T == 2:
result.append(st.query(X - 1, Y))
print(*result, sep='\n')
``````
0
0
0

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
0
0