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)

Recommended Posts

Solve AtCoder Problems Boot camp for Beginners (Medium 100) with python
Solve AtCoder Problems Recommendation with python (20200517-0523)
Solve AtCoder 167 with python
Solve AtCoder ABC166 with python
Solve AtCoder ABC 186 with Python
INSERT into MySQL with Python [For beginners]
[Python] Solve 10 past elite problems of Atcoder
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
WebApi creation with Python (CRUD creation) For beginners
Atcoder standard input set for beginners (python)
[For beginners] Try web scraping with Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Causal reasoning and causal search with Python (for beginners)
~ Tips for Python beginners from Pythonista with love ① ~
Solve "AtCoder version! Ant book (beginner)" with Python!
[Introduction for beginners] Working with MySQL in Python
python textbook for beginners
Solve Sudoku with Python
Solve POJ 2386 with python
OpenCV for Python beginners
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
[Python] Solve equations with sympy
Light blue with AtCoder @Python
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
Learning flow for Python beginners
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Python3 environment construction (for beginners)
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Python #function 2 for super beginners
Basic Python grammar for beginners
100 Pandas knocks for Python beginners
Python for super beginners Python #functions 1
Solve optimization problems in Python
Python #list for super beginners
~ Tips for beginners to Python ③ ~
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!
I tried to solve the ant book beginner's edition with python
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
How to write offline real time Solve F01 problems with Python
Create a USB boot Ubuntu with a Python environment for data analysis
solver> Link> Solve Excel Solver with python
Solve ABC163 A ~ C with Python
Python Exercise for Beginners # 2 [for Statement / While Statement]
Python for super beginners Python # dictionary type 1 for super beginners
Solve ABC166 A ~ D with Python
Solve Atcoder ABC169 A-D in Python
Getting Started with Python for PHPer-Classes
Python #index for super beginners, slices
Solve ABC168 A ~ C with Python
<For beginners> python library <For machine learning>
Python #len function for super beginners
Solved AtCoder ABC 114 C-755 with Python3
Created AtCoder test tool for Python
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
Beginners use Python for web scraping (1)
# 2 Python beginners challenge AtCoder! ABC085C --Otoshidama
Solve ABC158 A ~ C with Python
Run unittests in Python (for beginners)