AtCoder Problems の Boot camp for Beginners (Medium 100) を pythonで解く

この記事で書いている内容について（前提）

この記事は、競プロ初心者が自分の勉強記録を残すために書いています。

今日のまとめ（結論）

1. 二次元リストの初期化
   二次元リストを初期化するときは、
   [[None]*n]*m ではなく、
   [[None]*n for x in range(m)] をつかう
   (ABC057 B Checkpoints)
   
2. set(集合)の積
   <set> & <set> で簡単に取れる
   (ABC098 B Cut and Count)
3. groupbyは便利
   groupby(<list>) を使うと各要素とその要素が
   連続している数が簡単に取れる
   (ABC072 C Together)
4. listのindex
   <list>.index(<num>) で取得
   (ABC057 B Checkpoints)
5. listの出力
   *<list>という風にリストの先頭に*をつけることで
   リストの要素を展開して個別に引数として渡せる
   (カンマ区切りじゃない出力をするときなどに使う)
   (ABC107 B Grid Compression)
6. 二次元リストの転置
   二次元リストの転置にはzip(*<list>)を使う
   ただし、zipのreturnはiteraterなので、↓のように内包表記で書く
   [list(x) for x in zip(*<list>)]
   (zipは複数のイテラブルオブジェクトを引数にとって要素をまとめて取得する関数)
   (ABC107 B Grid Compression)

今日解いた問題（本題）

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 ※覚書有
7. ABC086 C Traveling
8. ABC154 D Dice in Line ※覚書有

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

覚書

集合(set)の重要さを学んだ。
<set>.issuperset(<set>)(親集合)
<set>.issubset(<set>)(部分集合)
の二つを使うと要素比較が簡単にできる。

# 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

覚書

期待値の最大値を出すときに、初めは安直にsum(e_list[i:i+k])でやってみたが、TLEになったので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)