AtCoder Grand Contest Past Question Challenge 2

AGC009A - Multiple Array

It's easy to see that you're pushing from the A _{N button to the A _{1 button in reverse order. A _{i is B _{i < A multiple of / sub> means A _{i mod B _{i = 0, so A _{i mod B _{When i is not 0, press B _{i --A _{i mod B _{i times. By the way, by then Note that A _{i increases by the number of times you press it. Based on the above, I wrote the following code to ask for an answer.}}}}}}}}}}}}

N = int(input())

A = [None] * N
B = [None] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

result = 0
for i in range(N - 1, -1, -1):
    t = (A[i] + result) % B[i]
    if t != 0:
        result += B[i] - t
print(result)

AGC011A - Airport Bus

The bus departs when the time limit of the first person waiting now comes or the moment the person waiting becomes C people. So, put the time limit of the first person and the current number of people waiting in the variables. Just turn the loop. Note that the time T _{i is not monotonously increasing, even though it is the i-th passenger.}

N, C, K = map(int, input().split())
T = [int(input()) for _ in range(N)]
T.sort()

c = 0
l = float('inf')
result = 0
for i in range(N):
    t = T[i]
    if t > l:
        result += 1
        l = float('inf')
        c = 0
    if c == 0:
        l = t + K
    c += 1
    if c == C:
        result += 1
        l = float('inf')
        c = 0
if c != 0:
    result += 1
print(result)

AGC034A - Kenken Race

It's easy for humans to do by hand, but I was groaning that it was annoying to implement, but I just overlooked that I could only go to the right (laugh). Priority is given to the one with the goal on the right. If you can't move it, move the other, and if you can't move both, display No, that's it.

N, A, B, C, D = map(int, input().split())
S = input()


def move_snuke():
    global A, B
    if B == D:
        return False
    if S[B + 1] == '.' and A != B + 1:
        B += 1
        return True
    if S[B + 2] == '.' and A != B + 2:
        B += 2
        return True
    return False


def move_fnuke():
    global A, B
    if A == C:
        return False
    if S[A + 1] == '.' and B != A + 1:
        A += 1
        return True
    if S[A + 2] == '.' and B != A + 2:
        A += 2
        return True
    return False


S = '#' + S
while True:
    if C < D:
        if not move_snuke():
            if not move_fnuke():
                print('No')
                break
    else:
        if not move_fnuke():
            if not move_snuke():
                print('No')
                break
    if A == C and B == D:
        print('Yes')
        break

AGC035A - XOR Circle

If the first is a and the second is b, the third is a xor b, the fourth is a, the fifth is b, and only three kinds of numbers appear. So, a _{i < If there are 4 or more types of / sub>, you can set No at that point. If there are 3 types, there are only 9 types of the first 2 numbers, and even if you simulate all combinations, N ≤ 10 ^{5 to the maximum O (9 × 10 ^{5 ), AC is possible.}}}

from itertools import product

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

c = {}
for e in a:
    c.setdefault(e, 0)
    c[e] += 1

if len(set(c)) > 3:
    print('No')
    exit()

t = {}
for x, y in product(set(c), repeat=2):
    i = x
    j = y
    t[i] = 1
    if t[i] > c[i]:
        continue
    t.setdefault(j, 0)
    t[j] += 1
    if t[j] > c[j]:
        continue
    for _ in range(N - 2):
        k = i ^ j
        t.setdefault(k, 0)
        t[k] += 1
        c.setdefault(k, 0)
        if t[k] > c[k]:
            j = -1
            break
        i, j = j, k
    if j ^ x == y:
        print('Yes')
        exit()
print('No')

AGC028A - Two Abbreviations

Since L is divisible by N and M, it is a multiple of the least common multiple of N and M. When L / N * i == L / M * j, it must be S [i] == T [j], Even if L becomes L * a, the pair of i and j to be compared does not change because it is only multiplied by a on both sides. Since the answer is the shortest, L is the least common multiple of N and M. Become.

from fractions import gcd


def lcm(x, y):
    return x // gcd(x, y) * y


N, M = map(int, input().split())
S = input()
T = input()

for i in range(N):
    if M * i % N == 0 and S[i] != T[M * i // N]:
        print(-1)
        exit()
print(lcm(N, M))

AGC022A - Diverse Word

The next colorful word is

If the length of the string is less than 26, add the smallest unused characters in lexicographical order.
If the length of the string is 26 characters, take the last character and add the last character that is larger than the last character and the smallest in the dictionary order. If there is no such thing, take the last letter and repeat.

Will be.

After all, since it is a character string with a maximum length of 26, there is no problem in actually adding or adding it, so implementation is not so difficult.

def next_diverse_word(s):
    alphabets = set(chr(ord('a') + i) for i in range(26))
    if s == 'zyxwvutsrqponmlkjihgfedcba':
        return -1
    r = alphabets - set(s)
    if len(r) != 0:
        return s + sorted(r)[0]
    s = list(s)
    r = [s[-1]]
    s = s[:-1]
    while True:
        k = s[-1]
        r.append(s[-1])
        s = s[:-1]
        t = [c for c in r if c > k]
        if len(t) != 0:
            s.append(sorted(t)[0])
            return ''.join(s)


S = input()
print(next_diverse_word(S))