AtCoder Grand Contest Past Question Challenge 1

AtCoder Grand Contest Past Question Challenge 1

AGC003B - Simplified mahjong

It's OK to make the maximum number of pairs with the same card, carry over if there is a surplus, and give priority to the carry-over (that is, carry over the current card if there is a surplus), but to 0 cards When a carry-over comes, there is no card to use with priority, so you have to discard the carry-over. If you care about that, it's OK.

N = int(input())

result = 0
remainder = 0
for _ in range(N):
    A = int(input())
    result += (A + remainder) // 2
    if A == 0:
        remainder = 0
    else:
        remainder = (A + remainder) % 2
print(result)

AGC016A - Shrinking

Since the length of s is at most 100 and there are only 26 alphabet types, it does not TLE even if it is rounded. For all the alphabets contained in s, the string t of length N is assumed to remain at the end. The minimum value of the number of operations can be obtained by actually performing the operation of changing to the character string t'of length N-1.

s = input()


def f(s, c):
    result = 0
    while len(set(s)) != 1:
        t = ''
        for i in range(len(s) - 1):
            if s[i] == c or s[i + 1] == c:
                t += c
            else:
                t += s[i]
        s = t
        result += 1
    return result


result = float('inf')
for c in set(s):
    result = min(result, f(s, c))
print(result)

AGC017A - Biscuits

You can eat an even number of bags with an odd number and any number of bags with an even number. If the bag with an odd number is a bag and the bag with an even number is b bag, the answer is (<sub). > a </ sub> C 0 </ sub> + a </ sub> C 2 </ sub> + ... + a </ sub> C floor (a / 2) * 2 </ sub>) * ( b </ sub> C 0 </ sub> + b </ sub> C 1 </ sub> + ... + b </ sub> C b </ sub>). By the way, b </ sub> C 0 </ sub> + b < / sub> C 1 </ sub> + ... + b </ sub> C b </ sub> is 2 b </ sup>, so the rest is a loop Just turn to find the number of ways to choose an odd number of bags.

def comb(n, k):
    if n - k < k:
        k = n - k
    if k == 0:
        return 1
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        b *= i + 1
    return a // b


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

odds = sum(a % 2 for a in A)
evens = len(A) - odds

print(sum(comb(odds, i) for i in range(P, odds + 1, 2)) * (2 ** evens))

AGC007A - Shik and Stone

In the process of moving, the fact that the piece was always moving to the right or down means that the number of movements is (H -1) + (W -1). The number 1 of # including the starting point is H + W. --If it is one, it means that it is not moving up or to the left.

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

if H + W - 1 == sum(a.count('#') for a in A):
    print('Possible')
else:
    print('Impossible')

AGC031A - Colorful Subsequence

If a appears n times in the string S, then a pattern that does not use a, a pattern that uses the first a, a pattern that uses the second a, ... a pattern that uses the nth a. There is an n + 1 pattern of. Since the number of combinations is independent for each character, the answer is to count the number of occurrences for each character and add up the number of appearances + 1.

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

MOD = 1000000007

d = {}
for c in S:
    if c in d:
        d[c] += 1
    else:
        d[c] = 1

result = 1
for x in d.values():
    result *= x + 1
    result %= MOD
result += MOD - 1
result %= MOD

print(result)

Recommended Posts

AtCoder Grand Contest Past Question Challenge 1
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 Past Question Review (12/5)
AtCoder Grand Contest 048 Review
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
AtCoder Grand Contest 046 Review
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Grand Contest 047 Participation Report
Challenge AtCoder
AtCoder Beginner Contest 066 Review past questions
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 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 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