ABC315 A~E 解説 (Python)

今回の[ABC315](https://atcoder.jp/contests/abc315/standings?watching=hiroyuk1)で、906位でパフォーマンスが水上位の<font color="00c0c0">1545</font>となり、レーティングが前回停滞の<font color="008000">1099</font>から<font color="008000">1153</font>と一気に54も上がりました。
ABCDE0ペナ5完76:15でした。
過去2番目のパフォーマンスの高さなので、嬉しいいいいいいいいいいいいいいいいいいいいいいです。

# A - tcdr

a, i, u, e, oを削除すればいいので、replaceを使えばいいです。
``` py
s = input()
for i in "aiueo":
  s = s.replace(i, "")
print(s)
```
全体2位の24秒で解けました。

# B - The Middle Day

一年の長さを求めて、それが奇数なので真ん中を求めます。
それから、for文で回して真ん中が来る月と日を求めます。僕は、ここでのバグが怖かったので、累積和を使いました。
``` py
m = int(input())
d = list(map(int, input().split()))
x = (sum(d) + 1) // 2
s = [0]
for i in d:
  s.append(s[-1] + i)
for j in range(m):
  if s[j] < x <= s[j + 1]:
    print(j + 1, x - s[j])
    exit(0)
```

# C - Flavors

一つ目の最大化と二つ目の最大化で分けました。defaultdictを二つ使いました。
``` py
from collections import defaultdict
n = int(input())
f = [0] * n
s = [0] * n
for i in range(n):
  f[i], s[i] = map(int, input().split())
d = defaultdict(list)
d2 = defaultdict(int)
for i in range(n):
  d[f[i]].append(s[i])
  d2[f[i]] = max(d2[f[i]], s[i])
l = list(d.items())
ans = 0
for i in l:
  if len(i[1]) >= 2:
    i[1].sort(reverse = True)
    ans = max(ans, i[1][0] + i[1][1] // 2)
l2 = list(d2.items())
if len(l2) >= 2:
  l2.sort(key = lambda x: -x[1])
  ans = max(ans, l2[0][1] + l2[1][1])
print(ans)
```

# D - Magical Cookies

各行、各列のそれぞれの文字の個数を管理しました。最初は、defaultdictでやろうとしたが、削除操作がうまくいかずlistに書き換えてACしました。

``` py
def f(c):
  return ord(c) - ord('a')
h, w = map(int, input().split())
s = [input() for _ in range(h)]
a = [True] * h # a[i]・・・s[i]が残ってるか　
b = [True] * w # aの縦ver.
da = [[0] * 26 for _ in range(h)]
db = [[0] * 26 for _ in range(w)]
for i in range(h):
  for j in range(w):
    da[i][f(s[i][j])] += 1
    db[j][f(s[i][j])] += 1
while True:
  p = False
  t = []
  u = []
  for i in range(h):
    if not a[i]:
      continue
    if da[i].count(0) == 25 and sum(da[i]) >= 2:
      t.append(i)
      da[i] = [0] * 26
      p = True
      """下に
      for j in range(w):
        if b[j]:
          db[j][f(s[i][j])] -= 1
      """
  for i in range(w):
    if not b[i]:
      continue
    if db[i].count(0) == 25 and sum(db[i]) >= 2:
      u.append(i)
      db[i] = [0] * 26
      p = True
      """
      for j in range(h):
        if a[j]:
          da[j][f(s[j][i])] -= 1
      """
  for i in t:
    for j in range(w):
      if b[j]:
        db[j][f(s[i][j])] -= 1
  for i in u:
    for j in range(h):
      if a[j]:
        da[j][f(s[j][i])] -= 1
  for i in t:
    a[i] = False
  for i in u:
    b[i] = False
  if not p:
    break
print(sum(a) * sum(b))
```

# E - Prerequisites

まずはトポロジカルソートします。それから、読む必要のあるものだけを取り出します。
``` py
from collections import deque
n = int(input())
g = [[] for _ in range(n)]
d = [0 for _ in range(n)]
for i in range(n):
  c, *g[i] = list(map(int, input().split()))
  for j in range(c):
    g[i][j] -= 1
    d[g[i][j]] += 1
for i in range(n): g[i].sort()
que = deque([])
for v in range(n):
  if d[v] == 0: que.append(v)
ans = []
while len(que):
  v = que.popleft()
  ans.append(v)
  for nv in g[v]:
    d[nv] -= 1
    if d[nv] == 0: que.append(nv)
should = [False] * n
# 読む必要があるやつ
q = deque([0])
while q:
  v = q.popleft()
  should[v] = True
  for nv in g[v]:
    if not should[nv]:
      q.append(nv)
ans.reverse()
nans = []
for i in ans:
  if should[i] and i != 0:
    nans.append(i + 1)
print(*nans)
```