AtCoder Beginners Contest Past Question Challenge 6

AtCoder Beginners Contest Past Question Challenge 6

ABC090D - Remainder Reminder

If the remainder of dividing a by b is K or more, it is confirmed that b is K + 1 or more. The remainder of dividing by b is 0..b-1, and the number of K or more that appears in this one cycle is b. --K. Since a is N or less, the number of cycles is N / b. After that, it is necessary to think about the remainder of the cycle, but since N starts from 1, the cycle is 1, 2, ..., Note that the order is b --1, 0. That is, if N% b is n, then 1, 2, ..., n, and the number of K = 0 and K = 1 is the same.

N, K = map(int, input().split())

result = 0
for b in range(K + 1, N + 1):
    result += (N // b) * (b - K) + max(N % b - max(K - 1, 0), 0)
print(result)

ABC115D - Christmas

The number of layers of the level L burger and the number of patties contained in it are N ≤ 50, so it can be calculated easily (and the formula to be calculated can be easily derived without rotating the loop). The rest is recursive until X is exhausted. If you encounter a level L burger and the remaining X is greater than the level L burger, reduce X by that number of layers, add that number of patties to the counter, and if it is smaller, level L -1 burger. Just go inside.

N, X = map(int, input().split())


def f(N, X):
    result = 0

    if X >= 1:
        X -= 1
    else:
        return result

    if X >= 2 ** ((N - 1) + 2) - 3:
        X -= 2 ** ((N - 1) + 2) - 3
        result += 2 ** ((N - 1) + 1) - 1
    else:
        return result + f(N - 1, X)

    if X >= 1:
        X -= 1
        result += 1
    else:
        return result

    if X >= 2 ** ((N - 1) + 2) - 3:
        X -= 2 ** ((N - 1) + 2) - 3
        result += 2 ** ((N - 1) + 1) - 1
    else:
        return result + f(N - 1, X)

    if X >= 1:
        X -= 1
    else:
        return result

    return result


print(f(N, X))

ABC053D - Card Eater

If you have 3 or more dub cards, you can reduce 2 duplications without reducing the number of card types no matter how you choose 3. If you have 2 dub cards, you can buy 2 dub cards on one side. One duplicating card can reduce duplication to 0 without reducing the number of card types. If there is one duplicating card, two duplicating cards and one other card can reduce the number of card types. Can be reduced by 1 but the duplication can be reduced to 0. After all, the answer is the number of card types minus 1 if the number of duplications is odd and 0 if it is even.

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

t = len(set(A))
if (len(A) - t) % 2 == 0:
    print(t)
else:
    print(t - 1)

ABC072D - Derangement

If p i </ sub> = i, just swap with p i </ sub> and p i + 1 </ sub> and count the number of times. P Swap with the previous p N-1 </ sub> only when N </ sub> = N. Since p i </ sub> is a permutation of 1..N, If you swap, it will always be p i </ sub>! = I, and of course p i + 1 </ sub>! = I, so p i + 1 </ sub> is always okay. It is clear that it is best to do it in order so that the continuous p i </ sub> = i that can be processed in one time is not processed in two times.

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

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

ABC040D --About measures against road deterioration

It's obvious to use a sized UnionFind by all means, then just sort by year and add roads in sequence to see how many cities people can come and go.

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())
roads = []
for _ in range(M):
    a, b, y = map(int, input().split())
    roads.append((y, a - 1, b - 1))
Q = int(input())
citizen = []
for i in range(Q):
    v, w = map(int, input().split())
    citizen.append((w, v - 1, i))

parent = [-1] * N

roads.sort(reverse=True)

results = [None] * Q
t = 0
for c in sorted(citizen, reverse=True):
    while t < M and roads[t][0] > c[0]:
        unite(parent, find(parent, roads[t][1]), find(parent, roads[t][2]))
        t += 1
    results[c[2]] = -parent[find(parent, c[1])]
print(*results, sep='\n')

ABC129E - Sum Equals Xor

When L = XXXX, the number of pairs satisfying the condition is n. When L = 1XXXX, the number of pairs satisfying the condition is 0 to 1111 and the number of pairs satisfying the condition and 10000 to 1XXXX. By the way, if YYYY + ZZZZ = YYYY xor ZZZZ, then 1YYYY + ZZZZ = 1YYYY xor ZZZZ holds, and YYYY + 1ZZZZ = YYYY xor 1ZZZZ also holds. 2 * n.

The number of pairs that satisfy the condition when L = 1 is (0,0), (0,1), (1,0), which is three. The number of pairs that satisfy the condition when L = 11 is as described above. The sum of 0 to 1 = 3 and 10 to 11 = 2 * 3 gives 3 * 3 = 9. Similarly, L = 111 becomes 9 * 3 = 27 and L = 1111 becomes 3 4 </ sup>. = 81. As a result, when L = 1XXXX, the number of pairs that satisfy the condition is 2 * n + 3 4 </ sup>.

At this point, you can calculate the answer one digit at a time from the last digit.

L = input()

result = 1
t = 1
for c in L[::-1]:
    if c == '1':
        result = result * 2 + t
        result %= 1000000007
    t *= 3
    t %= 1000000007
print(result)

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 117 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 076 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 047 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 083 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