Solve AtCoder Problems Boot camp for Beginners (Medium 100) with python

About the contents written in this article (premise)

This article is written by beginners of competition professionals to keep a record of their studies.

Today's summary (conclusion)

1. Initialization of 2D list When initializing a two-dimensional list, Not [[None] * n] * m Use [[None] * n for x in range (m)] (ABC057 B Checkpoints)
2. The product of sets Easy to get with <set> & <set> (ABC098 B Cut and Count)
3. group by is convenient If you use groupby (<list>), each element and its element will be Easy to get consecutive numbers (ABC072 C Together)
4. list index Get with <list> .index (<num>) (ABC057 B Checkpoints)
5. List output By adding * to the beginning of the list like * <list> You can expand the elements of the list and pass them individually as arguments (Used when outputting data that is not separated by commas) (ABC107 B Grid Compression)
6. Transpose a two-dimensional list Use zip (* <list>) to transpose a 2D list However, since the return of zip is iterator, write it in a comprehension like ↓ [list(x) for x in zip(*<list>)]
   (zip is a function that takes multiple iterable objects as arguments and gets the elements together) (ABC107 B Grid Compression)

Problem solved today (main subject)

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) * Memorandum of understanding
7. ABC086 C Traveling
8. [ABC154 D Dice in Line](# abc154-d-dice-in-line) * Memorandum available

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

Memorandum

I learned the importance of sets. <set> .issuperset (<set>) (parent set) <set> .issubset (<set>) (subset) You can easily compare elements by using these two.

# 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

Memorandum

When getting the maximum expected value, I tried using sum (e_list [i: i + k]) at first, but since it became TLE, I changed to the method of using the cumulative sum of 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)