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

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

# A問題
- `B_3` が `A_1` `A_2` `A_3` となるパターンを全て試して，条件を満たすかを確認すれば良い．
```A.py
"""
<方針>
- `B_3` が `A_1` `A_2` `A_3` となるパターンを全て試して，条件を満たすかを確認すれば良い．
"""
# 入力
AA = list(map(int, input().split()))

# 条件を満たすかのフラグ
ok = False
# 3パターン試す
for i in range(3):
  B1 = AA[i]
  B2 = AA[i-1]
  B3 = AA[i-2]
  # 式が成立するかどうか
  if(B1*B2 == B3):
    # 成立するならフラグを立てる
    ok = True

# 出力
if(ok):
  print("Yes")
else:
  print("No")
```

# B問題
- 存在しない判定を `not in` で確認する．
```B.py
"""
<方針>
- 存在しない判定を `not in` で確認する．
"""
# 入力
N, M = map(int, input().split())
AA = list(map(int, input().split()))

# 存在しないものを格納する．
ans = []

# 1~Nまで確認する．
for i in range(1, N+1):
  # 数字がAAの中に含まれていないか
  if(i not in AA):
    ans.append(i)

# 出力
print(len(ans))
print(*ans)
```

# C問題
## 方針
- `S` を左から順番に求めると，その `index` を探すのにも時間がかかり，`O(N^2)` かかってしまう．
- そこで，`S` の配列を用意しておき，`P` `Q` を左から探していき，それが `S` に準ずる場所に答えを入れれば，`O(N)` でいける．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `S` を左から順番に求めると，その `index` を探すのにも時間がかかり，`O(N^2)` かかってしまう．
- そこで，`S` の配列を用意しておき，`P` `Q` を左から探していき，それが `S` に準ずる場所に答えを入れれば，`O(N)` でいける．
"""
# 入力
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

# あらかじめ用意していく．
S = [-1]*N

# P, Qを左から見ていく
for i in range(N):
  p = P[i]
  q = Q[i]
  
  # Sを埋める．
  S[q-1] = Q[p-1]

# 出力
print(*S)
```

# D問題
- 事前処理
  - どの出目が何個出るかを `Counter` を使って `dict` で保持する．
  - そして，その出目が出る確率を `K` で割って取得する．
- 全ての組み合わせを計算
  - `combinations` を使って，サイコロの組み合わせを総当たりする．
  - `&` を使って共通の `key` だけ掛け合わせて確率を出す．
```D.py
"""
<方針>
- 事前処理
  - どの出目が何個出るかを `Counter` を使って `dict` で保持する．
  - そして，その出目が出る確率を `K` で割って取得する．
- 全ての組み合わせを計算
  - `combinations` を使って，サイコロの組み合わせを総当たりする．
  - `&` を使って共通の `key` だけ掛け合わせて確率を出す．
"""
# ライブラリ
from collections import Counter
from itertools import combinations

# 事前処理
N = int(input())
DI = []
for _ in range(N):
  K, *AA = map(int, input().split())
  
  # Counterをdictで取得
  di = dict(Counter(AA))
  
  # 確率を出すためにKで割る
  for ke, va in di.items():
    di[ke] = va/K
    
  DI.append(di)

# 答え
ans = -1
# 全ての組み合わせを計算
for i, j in combinations(range(N), 2):
  # 辞書を取得
  diI = DI[i]
  diJ = DI[j]
  
  # 共通のkeyだけ取得
  keys = diI.keys() & diJ.keys()
  
  # 確率の合計値
  tmp = sum([diI[ke]*diJ[ke] for ke in keys])
  
  # 確率が高い方で更新
  ans = max(ans, tmp)

# 出力
print(ans)
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc392)

### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- *今回も不参加のため，成績なし．*
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc392/submissions/62629084)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc392/submissions/62629134)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc392/submissions/62629373)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc392/submissions/62629724)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- 色々やばい．