AtCoder Beginners Contest Past Question Challenge 7

AtCoder Beginners Contest Past Question Challenge 7

ABC046D --AtCoDeer-kun and strange rock-paper-scissors

If you put out exactly the same move as TopCoDeer, the score will be 0 points, so the maximum score will be 0 points or more. For the time being, I decided to put out exactly the same move as TopCoDeer, and gave the number of pars and goo. If you count the number of times and change from the last goo to par as many times as you meet the conditions, you will get the highest score.

s = input()

print(max((s.count('g') * 2 - len(s)) // 2, 0))

ABC097D - Equals

If 1 and 2 can be swapped, and 2 and 3 can be swapped, then 1 and 3 can also be swapped. That is, the same union can be swapped. Union Find tree. I can't prove that you can arrange them as you want within the same union. But I've never heard that there are times when bubble sort isn't possible, so it's probably okay. Intuitively, you should sort them in order from the end. So, for all p i </ sub>, the same Check if there is i in the union, and the sum of the numbers is the answer.

from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 5)


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

parent = [-1] * N
for _ in range(M):
    x, y = map(int, input().split())
    unite(parent, x - 1, y - 1)

result = 0
for i in range(N):
    if find(parent, i) == find(parent, p[i] - 1):
        result += 1
print(result)

ABC043D --Unbalanced

If you check if the majority of all substrings are the same character, it will be * O * (* N * 2 </ sup>), so TLE is inevitable. By the way, if the majority are the same character, it is the same. The same character appears with two consecutive characters or one space between them. This can be seen immediately by actually making a character with the same majority. * O * (* N *) can be used to check if this exists. You can check it, so you can solve it.

s = input()

for i in range(len(s) - 1):
    if s[i] == s[i + 1]:
        print(*[i + 1, i + 2])
        exit()
for i in range(len(s) - 2):
    if s[i] == s[i + 2]:
        print(*[i + 1, i + 3])
        exit()
print(*[-1, -1])

ABC105D - Candy Distribution

If you write it in naive, * O * (* N * 3 </ sup>), even if it is relaxed by the cumulative sum, * O * (* N * 2 </ sup>) and what to do with TLE. ? First, instead of counting "the sum is a multiple of M", count "the sum of the remainders divided by M is 0". Then A 1 </ sub>, A 1 </ sub> + A 2 </ sub>, ..., A 1 </ sub> + A 2 </ sub> ... A N Count the number of </ sub> divided by M. If t m </ sub> is the number of occurrences of the remainder m, the number to be counted when l = 1, r = 1..N Is t 0 </ sub>. Next, l = 2, r = 1..N should be counted, but the number of A 1 </ sub> divided by M is reduced from each. So, I think for a moment that t A 1 </ sub>% M </ sub>, but since l = 1 and r = 1 were only A 1 </ sub>, this Must be omitted, which is t A 1 </ sub>% M </ sub> -1 and this one must be omitted even when calculating after l = 3. Don't. Then loop to l = N for the answer.

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

t = {}
c = 0
for a in A:
    c += a
    c %= M
    if c in t:
        t[c] += 1
    else:
        t[c] = 1

result = 0
if 0 in t:
    result += t[0]
c = 0
for a in A:
    c += a
    c %= M
    t[c] -= 1
    result += t[c]
print(result)

ABC064D - Insertion

Since we are looking for the smallest lexicographical order, we want to insert'(' to the left as much as possible and')' to the right as much as possible. So'(' is on the far left and')' is Suppose that you insert only at the right end. I wonder how many will be inserted after that, but since the length of the character string is at most 100, it will not become TLE even if it is actually transformed. Just add parentheses to the left or right edge until the string is empty.

N = int(input())
S = input()

result = S
while True:
    while True:
        t = S.replace('()', '')
        if t == S:
            break
        S = t
    if S == '':
        break
    elif S[0] == ')':
        S = '(' + S
        result = '(' + result
    elif S[0] == '(':
        S = S + ')'
        result = result + ')'
print(result)

ABC088D - Grid Repainting

The maximum score is to find the shortest path from (1, 1) to (H, W) in a breadth-first search and change all the white cells that did not pass on the shortest path to black. The answer is the number of white cells. --The number of squares on the shortest path.

H, W = map(int, input().split())
s = [input() for _ in range(H)]

dp = [[2501] * W for _ in range(H)]
dp[0][0] = 1

q = [(0, 0)]
while q:
    nq = []
    while q:
        y, x = q.pop()
        t = dp[y][x] + 1
        if y < H - 1:
            if s[y + 1][x] == '.' and dp[y + 1][x] > t:
                dp[y + 1][x] = t
                nq.append((y + 1, x))
        if y > 0:
            if s[y - 1][x] == '.' and dp[y - 1][x] > t:
                dp[y - 1][x] = t
                nq.append((y - 1, x))
        if x < W - 1:
            if s[y][x + 1] == '.' and dp[y][x + 1] > t:
                dp[y][x + 1] = t
                nq.append((y, x + 1))
        if x > 0:
            if s[y][x - 1] == '.' and dp[y][x - 1] > t:
                dp[y][x - 1] = t
                nq.append((y, x - 1))
    q = nq

if dp[H - 1][W - 1] == 2501:
    print(-1)
else:
    print(sum(s[y].count('.') for y in range(H)) - dp[H - 1][W - 1])

Recommended Posts

AtCoder Beginners Contest Past Question Challenge 6
AtCoder Beginners Contest Past Question Challenge 4
AtCoder Beginners Contest Past Question Challenge 9
AtCoder Beginners Contest Past Question Challenge 7
AtCoder Beginners Contest Past Question Challenge 10
AtCoder Beginners Contest Past Question Challenge 5
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Past Question Challenge 1
AtCoder Past Question Review (12 / 6,7)
AtCoder Past Question Review (12/5)
Challenge AtCoder
AtCoder Beginner Contest 066 Review past questions
# 2 Python beginners challenge AtCoder! ABC085C --Otoshidama
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions