ABC369(Atcoder Beginner Contest)のA~F(A,B,C,D,E,F)問題をPythonで解説(復習)

# ABC369(Atcoder Beginner Contest)のA~F(A,B,C,D,E,F)問題をPythonで解説(復習)

# A問題
- 以下の `3` パターンしかない．
  - `A == B` のとき， `1` 種類のみ
  - `(A - B)%2 == 1` のとき，`2` 種類のみ
  - それ以外の時， `3` 種類のみ
```A.py
"""
<方針>
- 以下の `3` パターンしかない．
  - `A == B` のとき， `1` 種類のみ
  - `(A - B)%2 == 1` のとき，`2` 種類のみ
  - それ以外の時， `3` 種類のみ
"""
# 入力
A, B = map(int, input().split())

# 1種類
if(A==B):
  print(1)
# 2種類
elif((A-B)%2==1):
  print(2)
# 3種類
else:
  print(3)
```

# B問題
- 右手と左手で分けて考える．
- ピアノを弾く時に，手を動かせば最小の疲労になる．
- 愚直にシミュレーションを行う．
```B.py
"""
<方針>
- 右手と左手で分けて考える．
- ピアノを弾く時に，手を動かせば最小の疲労になる．
- 愚直にシミュレーションを行う．
"""
# 入力
N = int(input())
L = []
R = []
for i in range(N):
  # a, bを文字列をして受け取る
  a, b = map(str, input().split())
  # aは数字に変換する
  a = int(a)
  
  # 右手に登録
  if(b=="R"):
    R.append(a)
  # 左手に登録
  else:
    L.append(a)

# 疲労度のシミュレーション
def simulate(hand):
  # 疲労度の合計値
  ret = 0
  # 弾くとき，
  if(len(hand)>0):
    # 最初の位置
    x = hand[0]
    for i in range(1, len(hand)):
      # 疲労度を増やす
      ret += abs(x-hand[i])
      # 次の手の位置
      x = hand[i]
  return ret
  

# 疲労度の合計値
ans = 0
# 左手のシミュレーション
ans += simulate(L)
# 右手のシミュレーション
ans += simulate(R)

print(ans)
```

# C問題
## 方針
- 等差数列の左端を固定して，一つずつ考えていては，計算量が `N^2` になってしまい， `TLE` してしまう．
- そこで，等差数列を成すには，全ての等差が等しくなければならないことを利用する．
  - 等差が等しく連続しているところに分けて，それぞれ `O(1)` で個数が求められれば，計算量は全体で `O(N)` となる．
  - 等差が等しく `L` 個連続するところは，自分自身のみをのぞいて， `(L-1)*L//2` と計算できる．(定数時間で求まる)
  - 最後に，自分自身のみ分 `N` を足せば `AC` する．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- 等差数列の左端を固定して，一つずつ考えていては，計算量が `N^2` になってしまい， `TLE` してしまう．
- そこで，等差数列を成すには，全ての等差が等しくなければならないことを利用する．
  - 等差が等しく連続しているところに分けて，それぞれ `O(1)` で個数が求められれば，計算量は全体で `O(N)` となる．
  - 等差が等しく `L` 個連続するところは，自分自身のみをのぞいて， `(L-1)*L//2` と計算できる．(定数時間で求まる)
  - 最後に，自分自身のみ分 `N` を足せば `AC` する．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# 差分を計算する．
dif = []
for i in range(N-1):
  dif.append(A[i]-A[i+1])
dif.append(10**11) # 番兵

# 個数
ans = 0
# 現在の差分
now = 10**10 # 初期値は番兵
# 連続した数
L = 0
for i in range(N):
  # 現在の差分
  d = dif[i]
  
  # 差分が直前と等しいとき
  if(now==d):
    L += 1
  # 差分が直前と等しくなかったので，直前の等差数列の個数を計算
  else:
    ans += (L-1)*L//2 
    # 次回の分
    now = d
    L = 2

# 自分自身のみのパターンを足す
ans += N

# 出力
print(ans)
```

# D問題
- 今回の敵を偶数回目に倒したかどうかで分けた `dp` を作成すればいける．

```D.py
"""
<方針>
- 今回の敵を偶数回目に倒したかどうかで分けた `dp` を作成すればいける．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# dp[i][j]
## i: i匹目までの敵
## j: 0の時，奇数回目で倒した．1の時，偶数回目で倒した．
dp = [[-1]*2 for _ in range(N)]

# 初期値
dp[0][0] = A[0]
dp[0][1] = 0

# 遷移
for i in range(N-1):
  # 「偶数回目で直前倒して，今回倒す」 or 「今回倒さない」
  dp[i+1][0] = max(dp[i][1] + A[i+1], dp[i][0])
  # 「奇数回めで直前倒して，今回倒す」 or 「今回倒さない」
  dp[i+1][1] = max(dp[i][0] + 2*A[i+1], dp[i][1])
  
print(max(dp[N-1]))
```

# E問題
- `N=400` より，ワーシャルフロイドを使って，任意の頂点間の最短距離を求めておく．
- `K=5` より，橋をどの順番で，どの向きで渡るかを全列挙して，最短距離となるパターンを出力する．
- 計算量は， `O(N^3 + Q*K!*2^K)` より，`10^7` ほどの計算量だが，実行時間が長めなので，多分大丈夫．
```E.py
"""
<方針>
- `N=400` より，ワーシャルフロイドを使って，任意の頂点間の最短距離を求めておく．
- `K=5` より，橋をどの順番で，どの向きで渡るかを全列挙して，最短距離となるパターンを出力する．
- 計算量は， `O(N^3 + Q*K!*2^K)` より，`10^7` ほどの計算量だが，実行時間が長めなので，多分大丈夫．
"""
N, M = map(int, input().split())

# 橋のコストを記録する．
INF = 10**20
dp = [[INF]*N for _ in range(N)]
# 単純に橋を記録
L = []
for i in range(M):
  u, v, t = map(int, input().split())
  u -= 1
  v -= 1
  
  # 単純に橋を記録
  L.append([u, v, t])
  
  # 複数の橋がある時は，最短の橋だけを記録する．
  dp[u][v] = min(dp[u][v], t)
  dp[v][u] = min(dp[v][u], t)

# 自分自身への橋は距離0である
for i in range(N):
  dp[i][i] = 0

# ワーシャルフロイド
for k in range(N):
  for i in range(N):
    for j in range(N):
      dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])


import itertools

Q = int(input())
for i in range(Q):
  # 入力
  K = int(input())
  B = list(map(lambda x: int(x)-1, input().split()))
  
  # 最短距離
  ANS = INF
  
  # どの橋の順番で渡るかの全パターン
  P = list(itertools.permutations(B))
  for p in P:
    # 橋を右から渡るか左から渡るかの全パターン
    for j in range(1<<K):
      # 渡る島の順番
      ls = []
      ls.append(0) # 最初の島
      # 距離
      ans = 0
      # 島を渡ってみる
      for k in range(K):
        
        # 今の橋の情報
        u, v, t = L[p[k]]
        
        # 指定された橋で渡る
        ans += t
        
        # 左から渡るとき
        if(1<<k & j):
          ls.append(u)
          ls.append(v)
        # 右から渡る時
        else:
          ls.append(v)
          ls.append(u)
      
      ls.append(N-1) # 最後の島
      
      # 指定はされていない橋で渡って，全てを結ぶ
      for k in range(K+1):
        # 指定されていないところだけを足す
        ans += dp[ls[2*k]][ls[2*k+1]]
        
        
      # if(ans<=9):
      #   print(ans)
      # # ans +=
      # print(ls)
      # print(p)
      # print(ans)
      # exit(1)
      ANS = min(ANS, ans)
  print(ANS)
  # exit(1)
      
        
# print(dp)
  
```

# F問題
- 公式解説と一緒

```F.py
"""
<方針>
- 公式解説と一緒
"""

from bisect import bisect_right as br

H, W, N = map(int, input().split())
V = [list(map(int, input().split())) for _ in range(N)]

# C方向で昇順にする．
V.sort()

# LISを求めている．
dp = [float("inf")]*N
ind = [-1]*N
pre = [-1]*N
for i in range(N):
  it = br(dp, V[i][1])
  dp[it] = V[i][1]
  ind[it] = i
  pre[i] = ind[it - 1] if it > 0 else -1

# 何個コインの間を移動するか．
m = N-1
while ind[m] == -1:
  m -= 1

# 経路を逆順に求めている．
path = [[H, W]]
now = ind[m]
while now != -1:
  path.append(V[now])
  now = pre[now]
path.append([1, 1])
# 正順に戻す．
path.reverse()

# 具体的な求めている．
ans = []
for i in range(len(path)-1):
  # srcとdst
  dst = path[i+1]
  src = path[i]
  
  # DownとRightの個数
  d = dst[0] - src[0]
  r = dst[1] - src[1]
  
  # 答えに追記
  ans.extend(["D"]*d)
  ans.extend(["R"]*r)

# 出力
print(len(path)-2)
print("".join(ans))
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc369)
- [F問題の公式解説](https://atcoder.jp/contests/abc369/submissions/57337244)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(ooooox-)](https://atcoder.jp/users/mattsunkun/history/share/abc369)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc369/submissions/57336351)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc369/submissions/57336529)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc369/submissions/57336759)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc369/submissions/57336885)
- [解説で示したE問題の提出](https://atcoder.jp/contests/abc369/submissions/57337138)
- [解説で示したF問題の提出](https://atcoder.jp/contests/abc369/submissions/57337244)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 惰性石器，スマホ．