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 C _{0 + _{a C _{2 + ... + _{a C _{floor (a / 2) * 2 ) * (_{b C _{0 + _{b C _{1 + ... + _{b C _{b ). By the way, _{b C _{0 + _{b C _{1 + ... + _{b C _{b is 2 ^{b , 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)