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

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

# A問題
- 条件を全パターン考えれば良い。
```A.py
"""
<方針>
- 条件を全パターン考えれば良い。
"""
# 入力
S1, S2 = input().split()

if(S1 == "sick" and S2 == "sick"):
  print(1)
if(S1 == "sick" and S2 == "fine"):
  print(2)
if(S1 == "fine" and S2 == "sick"):
  print(3)
if(S1 == "fine" and S2 == "fine"):
  print(4)
```

# B問題
- `A` の位置 `a` を全て考える。
- 間隔 `d` を全て考える。
- `B` の位置は `a+d` で、`C` の位置は `a+2*d` となるので、あとはカウントするだけ。
```B.py
"""
<方針>
- `A` の位置 `a` を全て考える。
- 間隔 `d` を全て考える。
- `B` の位置は `a+d` で、`C` の位置は `a+2*d` となるので、あとはカウントするだけ。
"""
# 入力
S = input()

# 長さ
N = len(S)

# カウント数
ans = 0
for a in range(N):
  for d in range(N):
    # index out of range 対策
    if(a+2*d<N):
      a = a+0*d
      b = a+1*d
      c = a+2*d
      # A, B, Cが存在するかどうか
      if(
        S[a] == "A" and 
        S[b] == "B" and 
        S[c] == "C"
        ):
          # カウントアップ
          ans += 1

# 出力
print(ans)
```

# C問題
## 方針
- `u = v` となっているところは切り取って良い。
- `u != v` となっているところは、`u < v` にソートして、`(N+1)*u + v` として辞書に登録する。
- 辞書で `2` つ以上要素があるものを切り取っていけば良い。
- 辞書は `defaultdict` を使うと `key` を見なくて良いから便利。
- 全体として、辺を見る分だけ、`O(M)` かかる。
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `u = v` となっているところは切り取って良い。
- `u != v` となっているところは、`u < v` にソートして、`(N+1)*u + v` として辞書に登録する。
- 辞書で `2` つ以上要素があるものを切り取っていけば良い。
- 辞書は `defaultdict` を使うと `key` を見なくて良いから便利。
- 全体として、辺を見る分だけ、`O(M)` かかる。
"""
# ライブラリ
from collections import defaultdict
# 答え
cut = 0
# 辞書
di = defaultdict(int)
# 入力
N, M = map(int, input().split())
for _ in range(M):
  u, v = map(int, input().split())
  # 同じ時
  if(u == v):
    cut += 1
    continue
  # u < v に直す
  elif(u > v):
    u, v = v, u
  
  # 辞書に登録
  key = (N+1)*u + v
  di[key] += 1

# 同じ辺をカットする。
for ke, va in di.items():
  cut += (va-1)

# 出力
print(cut)
```

# D問題
- 左右から `"1"` を近づけていく。
- 動かすのは、`"1"` が溜まってない方にする。
```D.py
"""
<方針>
- 左右から `"1"` を近づけていく。
- 動かすのは、`"1"` が溜まってない方にする。
"""
# 入力
N = int(input())
S = input()

# 1が一つの時は例外処理
if S.count("1") == 1:
  print(0)
  exit()

# 一番左の1を見つける。
for l in range(N):
  if S[l] == "1":
    break

# 一番右の1を見つける。
for r in reversed(range(N)):
  if S[r] == "1":
    break

# 動かした数
ans = 0
# 現在左に1が溜まってる数。
cL = 1
# 現在左に1が溜まってる数。
cR = 1

# 左右が隣り合うまで続ける。
while l+1 != r:
  # 左の方が少ない時
  if(cL < cR):
    # 左を動かす
    for l in range(l+1, r):
      # 1が見つかった時、
      if S[l] == "1":
        # 溜まってる1を更新する。
        cL += 1
        break
      # 0の時、
      else:
        # 溜まってる1を動かす。
        ans += cL
  # 右の方が少ない時も上記と同等の処理
  else:
    for r in reversed(range(l+1, r)):
      if S[r] == "1":
        cR += 1
        break
      else:
        ans += cR

# 出力
print(ans)
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc393)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc393/submissions/62850295)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc393/submissions/62850626)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc393/submissions/62865055)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc393/submissions/62869956)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- キーボードの句読点を変更しました。