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

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

# A問題
- 入力を `str` で受け取るように注意する．
- それぞれ， `A`, `B`, `C` が次男になる必要条件は，自分が関わっている大小関係だけを見ればよい．それぞれ， `2` パターンあるのを注意
```A.py
"""
<方針>
- 入力を `str` で受け取るように注意する．
- それぞれ， `A`, `B`, `C` が次男になる必要条件は，自分が関わっている大小関係だけを見ればよい．それぞれ， `2` パターンあるのを注意
"""
# 入力(str)
x, y, z = map(str, input().split())

# Aが次男
if (
  (x == "<" and y == ">") or 
  (x == ">" and y == "<")
  ):
  print("A")
# Bが次男
if (
  (x == "<" and z == "<") or 
  (x == ">" and z == ">")
  ):
  print("B")
# Cが次男
if (
  (y == "<" and z == ">") or 
  (y == ">" and z == "<")
  ):
  print("C")
```

# B問題
- それぞれの家で男の子が生まれたかどうかを管理する配列 `taro_exists` を作成する．
- 入力を上から順に受け取って，名前が `taro` になるかどうかを判定する．
```B.py
"""
<方針>
- それぞれの家で男の子が生まれたかどうかを管理する配列 `taro_exists` を作成する．
- 入力を上から順に受け取って，名前が `taro` になるかどうかを判定する．
"""
# 入力
N, M = map(int, input().split())

# 男の子が生まれたかどうかを管理する配列
taro_exists = [False]*(N+1)

# 順に入力を受け取る
for _ in range(M):
  # 入力を受け取る
  A, B = input().split()
  # Aの入力を数値として受け取る
  A = int(A)
  
  # 初めてお家Aで男の子が生まれた
  if(B == "M" and not taro_exists[A]):
    print("Yes")
    # 男の子が生まれたことを記録する．
    taro_exists[A] = True
  # 女の子が生まれた
  else:
    print("No")
```

# C問題
## 方針
- 今回は全ての頂点を入れ替えるパターンが `O(N!)` である．
- 全部の辺を確かめても，`O(N^2)` である．
  - 全ての頂点の間を辺の有無に関わらずみていき， `G` と `H` で辺の有無が合致しないところだけをコストとして払えば，同型になる．
- 計算量は `O(N! x N^2)` 程度なので，問題なく処理できる．実装できるかどうかだ．
- 補足
  - `0-indexed` で数える．
  - `G` と `H` の受け取り方は一緒なので，関数化して，実装を軽くする．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 今回は全ての頂点を入れ替えるパターンが `O(N!)` である．
- 全部の辺を確かめても，`O(N^2)` である．
  - 全ての頂点の間を辺の有無に関わらずみていき， `G` と `H` で辺の有無が合致しないところだけをコストとして払えば，同型になる．
- 計算量は `O(N! x N^2)` 程度なので，問題なく処理できる．実装できるかどうかだ．
- 補足
  - `0-indexed` で数える．
  - `G` と `H` の受け取り方は一緒なので，関数化して，実装を軽くする．
"""
# ノードの数
N = int(input())

# グラフを受け取る関数
def getEdges():
  M = int(input())
  Edges = [[False]*N for _ in range(N)]
  
  for _ in range(M):
    u, v = map(int, input().split())
    # 0-indexed
    u -= 1
    v -= 1
    
    Edges[u][v] = True
  
  return Edges

# Gを構築
G = getEdges()

# Hを構築
H = getEdges()

# Aを構築
A = [list(map(int, input().split())) for _ in range(N-1)]

import itertools


ans = float("inf")
# 頂点を入れ替える
for table in itertools.permutations(range(N)):
  # コストの計算
  tmp = 0
  # 辺の有無を全て確認する．
  for i in range(N):
    for j in range(N):
      # 重複を防ぐ
      if(i>=j):continue
      # 並び替えを考慮する(I<Jとする)
      I = min(table[i], table[j])
      J = max(table[i], table[j])
      
      # 辺の有無が一致しない時
      if(G[I][J] != H[i][j]):
        tmp += A[i][j-i-1] # indexに注意
        
  # 最小コストの更新
  ans = min(ans, tmp)
  
print(ans)
```

# D問題
- セグメント木で区間取得を早くする．
- 取得する場所は2分探索で早くとる．
```D.py
"""
<方針>
- セグメント木で区間取得を早くする．
- 取得する場所は2分探索で早くとる．
"""
from atcoder.segtree import SegTree

N = int(input())
X = list(map(int, input().split()))
P = list(map(int, input().split()))

# セグ木
st = SegTree(lambda x,y:x+y, 0, P)

Q = int(input())
for _ in range(Q):
  L, R = map(int, input().split())
  
  # 左端を取得
  ng = -1
  ok = N
  while abs(ok - ng) > 1:
    mid = (ok+ng)//2
    
    if(L<=X[mid]):
      ok = mid
    else:
      ng = mid
  l = ok
  
  # 右端を取得
  ok = -1
  ng = N
  while abs(ok - ng) > 1:
    mid = (ok+ng)//2
    
    if(X[mid]<=R):
      ok = mid
    else:
      ng = mid
  r = ok
  
  # セグ木を使って，値を取得
  print(st.prod(l, r+1))

```

# E問題
- 公式解説と一緒です．

```E.py
"""
<方針>
- 公式解説と一緒です．
"""
N = int(input())
A = list(map(int, input().split()))

# 種類ごとにどこのインデックスにあるか
table = [[-1] for _ in range(N+1)]
for i, a in enumerate(A):
  table[a].append(i)
  
# 答え
ans = 0

# 全ての種類を見る
for indices in table:
  # 数字が存在したとき
  if(len(indices) > 1):
    # 余事象で考える
    ans += (N*(N+1)//2)
    # 番兵
    indices.append(N)
    
    # 間を見ていく
    for i in range(len(indices)-1):
      # 間の長さを取得
      le = indices[i+1] - indices[i] - 1
      # 長さがある時
      if(le>0):
        # 引いていく
        ans -= (le*(le+1)//2)
        
print(ans)
```


# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc371)
- [E問題の公式解説](https://atcoder.jp/contests/abc371/editorial/10922)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- 今回は不参加のため，成績なし．
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc371/submissions/57777932)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc371/submissions/57779605)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc371/submissions/57806617)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc371/submissions/57806927)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc371/submissions/57808340)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．