Résoudre les problèmes d'AtCoder Boot camp pour les débutants (moyen 100) avec python

À propos du contenu écrit dans cet article (prémisse)

Cet article est rédigé par des professionnels de la compétition débutants pour garder une trace de leurs études.

Résumé du jour (conclusion)

1. Initialisation de la liste bidimensionnelle Lors de l'initialisation d'une liste bidimensionnelle Pas [[None] * n] * m Utilisez «[[None] * n for x in range (m)]» (ABC057 B Checkpoints)
2. Le produit des ensembles Facile à obtenir avec <set> & <set> (ABC098 B Cut and Count)
3. grouper par est pratique Si vous utilisez groupby (<list>), chaque élément et son élément seront Facile à obtenir des numéros consécutifs (ABC072 C Together)
4. index de la liste Obtenir avec <liste> .index (<num>) (ABC057 B Checkpoints)
5. Sortie de liste En ajoutant * au début de la liste comme * <liste> Vous pouvez développer les éléments de la liste et les transmettre individuellement comme arguments (Utilisé lors de la sortie de données qui ne sont pas séparées par des virgules) (ABC107 B Grid Compression)
6. Translocation d'une liste bidimensionnelle Utilisez zip (* <list>) pour transposer une liste à deux dimensions Cependant, puisque le retour de zip est un itérateur, écrivez-le en notation d'inclusion comme ↓ [list(x) for x in zip(*<list>)]
   (Zip est une fonction qui prend plusieurs objets itérables comme arguments et récupère les éléments ensemble) (ABC107 B Grid Compression)

Problème résolu aujourd'hui (sujet principal)

1. ABC098 B Cut and Count
2. ABC064 C Colorful Leaderboard
3. ABC060 B Choose Integers
4. ABC072 C Together
5. ABC057 B Checkpoints
6. [ABC107 B Grid Compression](# abc107-b-grid-compression) * Mémorandum disponible
7. ABC086 C Traveling
8. [ABC154 D Dice in Line](# abc154-d-dice-in-line) * Mémorandum disponible

ABC098 B Cut and Count

# ABC098
# B
# Cut and Count

n = int(input())
s = input()
ans = 0
for i in range(n):
    s_f = set(s[:i])
    s_b = set(s[i:])
    _l =len(s_f & s_b)
    if ans < _l:
        ans = _l

print(ans)

ABC064 C Colorful Leaderboard

# ABC064
# C
# Colorful Leaderboard

n = int(input())
a_list = list(map(int, input().split()))

color_list = [0]*8
over = 0
for i in range(n):
    _ = a_list[i] // 400
    if _ < 8:
        color_list[_] = 1
    else:
        over += 1

_tmp = sum(color_list)
if _tmp == 0:
    print("1 %d"%over)
else:
    print("%d %d"%(_tmp, _tmp+over))

ABC060 B Choose Integers

# ABC060
# B
# Choose Integers

a, b, c = map(int, input().split())
n = b

flag = False
for i in range(n):
    if (i * a) % b == c:
        flag = True
        break

if flag:
    print("YES")
else:
    print("NO")

ABC072 C Together

# ABC072
# C
# Together

import itertools

n = int(input())
a = [int(i) for i in input().split()]

a.sort()
gr = itertools.groupby(a)
hoge_list = [0]*100001
ans = 0

for key, group in gr:
    hoge_list[key] = len(list(group))

for i in range(1,100000,1):
    _tmp = hoge_list[i-1] + hoge_list[i] + hoge_list[i+1]
    if ans < _tmp:
        ans = _tmp

print(ans)

ABC057 B Checkpoints

# ABC057
# B
# Checkpoints

n, m = map(int, input().split())
ax = [None]*n
by = [None]*n
cx = [None]*m
dy = [None]*m

d_list = [[None]*m for i in range(n)]

for i in range(n):
    ax[i],by[i] = map(int, input().split())
for i in range(m):
    cx[i],dy[i] = map(int, input().split())

for i in range(n):
    for j in range(m):
        d_list[i][j] = abs(ax[i]-cx[j]) + abs(by[i]-dy[j])
        
for i in range(n):
    print(d_list[i].index(min(d_list[i]))+1)

ABC107 B Grid Compression

Mémorandum

J'ai appris l'importance des décors. <set> .issuperset (<set>) (ensemble parent) <set> .issubset (<set>) (sous-ensemble) Vous pouvez facilement comparer des éléments en utilisant ces deux éléments.

# ABC107
# B
# Grid Compression

h, w = map(int, input().split())
a_list = []
for i in range(h):
    _tmp = input()
    if set(_tmp).issuperset({"#"}):
        a_list.append(_tmp)

a_list_T = [list(x) for x in zip(*a_list)]
tmp_list = []

for i in range(w):
    _tmp = a_list_T[i]
    if set(_tmp).issuperset({"#"}):
        tmp_list.append(_tmp)
        
ans = [list(x) for x in zip(*tmp_list)]

for _l in ans:
    print(*_l,sep="")

ABC086 C Traveling

# ABC086 C Traveling

n = int(input())
t, x, y = 0, 0, 0
flag = True

for i in range(n):
    _t,_x,_y = map(int, input().split())
    _d = abs(x - _x) + abs(y - _y)
    _dt = abs(t - _t)
    if _d > _dt or ((_d - _dt)%2) == 1:
        flag = False
    t,x,y = _t,_x,_y

if flag:
    print("Yes")
else:
    print("No")

ABC154 D Dice in Line

Mémorandum

Lors de l'obtention de la valeur maximale attendue, j'ai essayé d'utiliser sum (e_list [i: i + k]) au début, mais depuis qu'il est devenu TLE, j'ai changé la méthode d'utilisation de la somme cumulée d'itertools.

# ABC154 D Dice in Line

import itertools

n, k = map(int, input().split())
p_list = [int(x) for x in input().split()]
e_list = [None]*n

for i in range(n):
    e_list[i] = (1 + p_list[i])/2

cumsum = list(itertools.accumulate(e_list))
ans = cumsum[k-1]

for i in range(k,n):
    _ = cumsum[i] - cumsum[i-k]
    if ans < _:
        ans = _

print(ans)