Concours AtCoder pour débutants Défi des questions passées 9

Concours AtCoder pour débutants Défi des questions passées 9

ABC071D - Coloring Dominoes

Premièrement, si le bord gauche est vertical, il y a 3 façons de peindre. S'il est horizontal, il y a 6 façons avec 3 * 2. Ensuite, si la verticale vient à côté de la verticale, elle doit être différente de la couleur verticale précédente, donc 2 Si l'horizontale vient à côté de la verticale, si vous décidez du côté supérieur, il y a deux façons car il devrait être différent de la verticale, et il n'y a qu'une seule autre façon sur le côté inférieur, il y a donc deux façons. Horizontal Si la verticale vient à côté de l'horizontale, il n'y a qu'une seule façon car deux couleurs ont déjà été décidées.Lorsque l'horizontale vient à côté de l'horizontale, il y a trois façons comme suit.

0022  0011  0011
1100  1100  1122

Tout ce que vous avez à faire est de faire l'addition.

N = int(input())
S1 = input()
S2 = input()

if S1[0] == S2[0]:
    result = 3
else:
    result = 6
x = 0
W = len(S1)
while x < W:
    if S1[x] == S2[x]:
        if x + 1 == W:
            break
        result *= 2
        result %= 1000000007
        x += 1
    else:
        if x + 2 == W:
            break
        if S1[x + 2] != S2[x + 2]:
            result *= 3
            result %= 1000000007
        x += 2
print(result)

ABC109D - Make Them Even

Il n'y a pas de limite au mouvement minimum, alors allez du coin supérieur gauche vers la droite, descendez un à gauche lorsque vous atteignez la fin, descendez d'un à droite lorsque vous atteignez la fin, et ainsi de suite. Ensuite, s'il s'agit d'un nombre impair, si vous répétez l'envoi au carré suivant, ce sera soit un nombre pair, soit seul le dernier carré sera un nombre impair.

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

result = []
y = 0
while y < H:
    x = 0
    while x < W:
        if a[y][x] % 2 == 1:
            if x == W - 1:
                if y == H - 1:
                    break
                else:
                    result.append('%d %d %d %d' % (y + 1, x + 1, y + 2, x + 1))
                    a[y + 1][x] += 1
            else:
                result.append('%d %d %d %d' % (y + 1, x + 1, y + 1, x + 2))
                a[y][x + 1] += 1
        x += 1
    if y == H - 1:
        break
    y += 1
    x = W - 1
    while x >= 0:
        if a[y][x] % 2 == 1:
            if x == 0:
                if y == H - 1:
                    break
                else:
                    result.append('%d %d %d %d' % (y + 1, x + 1, y + 2, x + 1))
                    a[y + 1][x] += 1
            else:
                result.append('%d %d %d %d' % (y + 1, x + 1, y + 1, x))
                a[y][x - 1] += 1
        x -= 1
    y += 1

print(len(result))
print('\n'.join(result))

ABC096D - Five, Five Everywhere

Si vous divisez par 5, vous pouvez organiser les nombres premiers restants dans l'ordre croissant selon vos besoins. Toute combinaison sera un multiple de 5.

N = int(input())

result = []
sieve = [0] * (55555  + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, 55555 + 1):
    if sieve[i] != 0:
        continue
    if i % 5 == 1:
        result.append(i)
        if len(result) == N:
            break
    sieve[i] = i
    for j in range(i * i, 55555 + 1, i):
        if sieve[j] == 0:
            sieve[j] = i
print(*result)

ABC099D - Good Grid

La combinaison de couleurs est 30 </ sub> C 3 </ sub> = 4060, vous pouvez donc faire une recherche complète, mais puisque N ≤ 500, si vous le faites sans réfléchir, * O * (4060 × 500) 2 </ sup> ≒ 10 10 </ sup>) et TLE est inévitable. (I + j) Si vous groupez par le reste de% 3 et comptez les couleurs d'origine, * O * (4060) × 30 × 3 ≒ 3,7 × 10 5 </ sup>), il est donc résolu.

from itertools import permutations

N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

a = [[0] * C for _ in range(3)]
for y in range(N):
    for x in range(N):
        t = ((x + 1) + (y + 1)) % 3
        a[t][c[y][x] - 1] += 1

result = float('inf')
for b in permutations(range(C), 3):
    t = 0
    for i in range(3):
        for j in range(C):
            t += a[i][j] * D[j][b[i]]
    result = min(result, t)
print(result)

ABC103D - Islands War

J'ai eu l'intuition que le tri par b était une douleur pendant Keyence Programming Contest 2020 B - Robot Arms. C'est un problème de planification. Après cela, je devrais supprimer autant de ponts que nécessaire, mais au début, j'ai enregistré et résolu les ponts supprimés par Segment Tree. Eh bien, * O * ( Je peux le résoudre avec N </ i> log N </ i>), mais j'ai remarqué en regardant le PDF d'explication qu'il était normal de ne retenir que le dernier supprimé.

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

ab.sort(key=lambda x: x[1])

result = 0
t = -1
for a, b in ab:
    a, b = a - 1, b - 1
    if a <= t < b:
        continue
    result += 1
    t = b - 1
print(result)

ABC055D - Menagerie

Si vous décidez du 1er et du 2ème animaux, vous aurez 1 choix après cela, et si vous faites une erreur, vous saurez qu'il y a une contradiction à la fin. Donc, si vous faites le 1er et le 2ème avec 4 motifs du tour S, W Bon. * O * (4 × 10 5 </ sup>), donc il n'y a pas de problème en termes de montant de calcul.

from itertools import product

N = int(input())
s = input()

swap = {'S': 'W', 'W': 'S'}
for a, b in product('SW', repeat=2):
    t = [None] * N
    t[0] = a
    t[1] = b
    for i in range(1, N - 1):
        if t[i] == 'S':
            if s[i] == 'o':
                t[i + 1] = t[i - 1]
            elif s[i] == 'x':
                t[i + 1] = swap[t[i - 1]]
        elif t[i] == 'W':
            if s[i] == 'o':
                t[i + 1] = swap[t[i - 1]]
            elif s[i] == 'x':
                t[i + 1] = t[i - 1]
    if t[N - 1] == 'S':
        if s[N - 1] == 'o' and t[N - 2] != t[0]:
            continue
        elif s[N - 1] == 'x' and t[N - 2] == t[0]:
            continue
    elif t[N - 1] == 'W':
        if s[N - 1] == 'o' and t[N - 2] == t[0]:
            continue
        elif s[N - 1] == 'x' and t[N - 2] != t[0]:
            continue
    if t[0] == 'S':
        if s[0] == 'o' and t[N - 1] != t[1]:
            continue
        elif s[0] == 'x' and t[N - 1] == t[1]:
            continue
    elif t[0] == 'W':
        if s[0] == 'o' and t[N - 1] == t[1]:
            continue
        elif s[0] == 'x' and t[N - 1] != t[1]:
            continue
    print(''.join(t))
    exit()
print(-1)

Recommended Posts