AtCoder Grand Contest Past Question Challenge 2

AtCoder Grand Contest Past Question Challenge 2

AGC009A - Multiple Array

It's easy to see that you're pushing from the A N </ sub> button to the A 1 </ sub> button in reverse order. A i </ sub> is B i < A multiple of / sub> means A i </ sub> mod B i </ sub> = 0, so A i </ sub> mod B When i </ sub> is not 0, press B i </ sub> --A i </ sub> mod B i </ sub> times. By the way, by then Note that A i </ sub> 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 </ sub> 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 </ sup From> to the maximum O (9 × 10 5 </ sup>), 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

  1. If the length of the string is less than 26, add the smallest unused characters in lexicographical order.
  2. 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))

Recommended Posts

AtCoder Grand Contest Past Question Challenge 2
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 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