[ABC409] ABC 409(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# [ABC409] ABC 409(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)

# A問題
- `T` と `A` で両方とも `"o"` になっている部分を見つける。
```A.py
"""
<方針>
- `T` と `A` で両方とも `"o"` になっている部分を見つける。
"""
# 入力
N = int(input())
T = input()
A = input()

# 前から見る
for i in range(N):
  # TとAが"o"のところがあれば、
  if(T[i] == A[i] == "o"):
    print("Yes") # Yesとする
    exit() # プログラムを終了する

# 見つからなかったら、Noを出力する。
print("No")
```

# B問題
- `N<=100` なので、`100` から順番に、条件を満たすものを考える。
```B.py
"""
<方針>
- `N<=100` なので、`100` から順番に、条件を満たすものを考える。
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 100->0をみる
for x in reversed(range(100+1)):
  # x以上のaをカウント
  cnt = 0
  for a in A:
    if(x <= a):
      cnt += 1
  
  # カウントがx以上になったら、
  if(x <= cnt):
    # 抜ける
    break

# 出力
print(x)
```

# C問題
## 方針
- 円周上で三角形が正三角形になるときは、`+L//3` ずつしたところを確認すれば良い。
- また、`L%3 == 0` の時だけ正三角形が存在しうる。
- 最初の点は、`0~L//3` だけ確認すれば良い。
- 計算時間は `O(N+L)` になるはず。
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 円周上で三角形が正三角形になるときは、`+L//3` ずつしたところを確認すれば良い。
- また、`L%3 == 0` の時だけ正三角形が存在しうる。
- 最初の点は、`0~L//3` だけ確認すれば良い。
- 計算時間は `O(N+L)` になるはず。
"""
# 入力
N, L = map(int, input().split())
D = list(map(int, input().split()))

# 正三角形を生成できないとき
if(L%3 != 0):
  print(0)
  exit()

# 円周上に点を置く
ind = 0
C = [0]*L
C[0] += 1
for d in D:
  ind += d
  ind %= L
  C[ind] += 1

# カウントをする
ans = 0
# L//3だけ見れば良い
for i in range(L//3):
  X = C[i+0*L//3]
  Y = C[i+1*L//3]
  Z = C[i+2*L//3]
  
  ans += X*Y*Z

# 出力
print(ans)
```

# D問題
- 左から走査すればまあわかる。
- 大きい文字はなるべく右に持っていこうぜ。
- クソみたいな説明でごめん。
```D.py
"""
<方針>
- 左から走査すればまあわかる。
- 大きい文字はなるべく右に持っていこうぜ。
- クソみたいな説明でごめん。
"""
T = int(input())
for _ in range(T):
  N = int(input())
  S = list(input())
  # 文字列の長さが1は例外
  if(N == 1):
    print(S[0])
    continue
  
  # 左から順番に大きい文字を見つける
  for i in range(N-1):
    if(S[i] > S[i+1]):
      break
  
  # 見つけた大きい文字より大きい右の文字を見つける
  j = N
  for _j in range(i+1, N):
    if(S[_j] > S[i]):
      j = _j
      break
  
  # 文字の順番を変える
  T = S[:i] + S[i+1:j] + S[i:i+1] + S[j:N]
  
  print("".join(T))
```

# E問題
- 葉にある電荷を中心に移動させれば良い。
```E.py
"""
<方針>
- 葉にある電荷を中心に移動させれば良い。
"""
# 入力
N = int(input())
X = list(map(int, input().split()))

# グラフ構築
E = [[] for _ in range(N)]
for _ in range(N-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  
  E[u].append([v, w])
  E[v].append([u, w])
  
# 電荷を中心に移動させるDFS
ans = 0
q = [[0, -1, 0]]
while q:
  u, p, edge = q.pop() # DFS
  
  # 端っこであれば、
  if(edge):
    for v, w in E[u]:
      if(v != p):
        ans += w*abs(X[v])
        X[u] += X[v]
  # 端っこでなければ、
  else:
    q.append([u, p, 1])
    for v, w in E[u]:
      if(v != p):
        q.append([v, u, 0])

# 出力
print(ans)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc409)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc409/submissions/66610121)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc409/submissions/66610305)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc409/submissions/66610919)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc409/submissions/66610996)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc409/submissions/66611410)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- `いいかい！もっとも『むずかしい事』は！『自分を乗り越える事』さ ...`