ABC-373

A

$URL\:\to$ https://atcoder.jp/contests/abc373/tasks/abc373_a

#愚直

cnt = 0
for i in range(12):
  w = Word().content
  if len(w)==i+1: cnt+=1
print(cnt)

解法

$i(0\to11)$ として $S_{i}==i+1 \to cnt++$ すると題意を満たせる。

---

B

$URL\:\to$ https://atcoder.jp/contests/abc373/tasks/abc373_b

#愚直

a = "BCDEFGHIJKLMNOPQRSTUVWXYZ"
s = Word().content
poz = s.index("A")
ans = 0
for i in a:
  ans += abs(poz-s.index(i))
  poz = s.index(i)
print(ans)

解法

$poz$ の初期値を $index(A)$ とし、$i\:(B\to Z)$ とし、$ans+=abs(poz-index(i))$ とした後、$poz=index(i)$ に更新すると題意を満たせる。

---

C

$URL\:\to$ https://atcoder.jp/contests/abc373/tasks/abc373_c

#愚直

Python

n = Integer().content
    a = max(IntegerList().content)
    b = max(IntegerList().content)
    print(a+b)

C++

ll n; scanf("%lld", &n);
ll a[n]; rep(i,0,n) scanf("%lld", &a[i]);
ll b[n]; rep(i,0,n) scanf("%lld", &b[i]);

dsort(a, n);
dsort(b, n);

cout << a[0]+b[0] << endl;

解法

$max(A_{i}+B_{j})\:\longleftrightarrow\:max(A_{i})+max(B_{j})$ は自明なので、題意を満たすことができる。

---

D

$URL\:\to$ https://atcoder.jp/contests/abc373/tasks/abc373_d

#DFS/BFS

n,m = Integer().content
ug = UndirectedGraph(n,m)
visited = [False]*n
ans = [0]*n

## dfs
for i in range(n):
  if visited[i]: continue
  currentNode = [i]
  visited[i] = True
  while currentNode:
    u = currentNode.pop()
    for v,w in ug.graph[u]:
      if not visited[v]:
        visited[v] = True
        ans[v] = ans[u]+w
        currentNode.append(v)
print(*ans)

解法

有向グラフは双方向のコストのうち片方の正負を逆転させることで無向グラフに落とすことができる。 ある頂点に関して、初期値を決めて、$DFS$ することで繋がっている頂点の値を一意に確定させることができる。

---

E

解法

---