Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What are the problem?
@c-yan

AtCoder Beginner Contest 185 参戦記

AtCoder Beginner Contest 185 参戦記

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

ABC185A - ABC Preparation

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

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

print(min(A))

ABC185B - Smartphone Addiction

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を出力するトンマをやらかした.

白の連続長の最小値が k. 後は各区間ではんこを何回使えばよいかを求めて、その総和が答えとなる. D問題にしては簡単? max を min と書いて時間を無駄にした. 今日は max と min の入れ違いが多いな(笑).

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

突破できず. 順位表を見るに明らかにEとFで難易度が入れ替わっているが、出題者が難易度を勘違いした以上は、Fと同じように典型問題なんだろうと腐った読みをしたが、レーベンシュタイン距離に辿り着けなかった. 辿り着けなかったものの、残り20分くらい時点で DP で解けるんじゃねと思いついたが、5分ほど足りなかった.

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


readline = stdin.readline

N, Q = map(int, readline().split())
A = list(map(int, readline().split()))

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')
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
0
Help us understand the problem. What are the problem?