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

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

# A問題

- `A`と`B`が一緒の値の時，容疑者が絞れないため，`-1`を出力して終了する．
- 容疑者を管理する，`suspects`を作成し，初期値を`{1, 2, 3}`とする．
- `suspects`から`A`と`B`を除く．
- `suspects`に残った数字を出力する．
```A.py
"""
<方針>
- `A`と`B`が一緒の値の時，容疑者が絞れないため，`-1`を出力して終了する．
- 容疑者を管理する，`suspects`を作成し，初期値を`{1, 2, 3}`とする．
- `suspects`から`A`と`B`を除く．
- `suspects`に残った数字を出力する．
- 
"""
# AとBを受け取る．
A, B = map(int, input().split())

# AとBが一緒の時，
if(A==B):
  # 容疑者が絞れないため，-1を出力する．
  print(-1)
  # 実行を終了する．
  exit()

# 容疑者を管理する集合．初期値は{1, 2, 3}とする．
suspects = {1, 2, 3}

# Aを容疑者から除外する．
suspects.remove(A)
# Bを容疑者から除外する．
suspects.remove(B)

# 残った容疑者を出力する．
print(*suspects)
```

# B問題

- `C`を作成する際に，その数字が`A`出身か`B`出身か`kind`も持たせておく．
- `C`を連続`2`つ見て，それらが両方とも`A`出身であった場合は，`Yes`を出力して終了する．
- `Yes`を出力しなかった時に，`No`を出力する．
```B.py
"""
<方針>
- `C`を作成する際に，その数字が`A`出身か`B`出身か`kind`も持たせておく．
- `C`を連続`2`つ見て，それらが両方とも`A`出身であった場合は，`Yes`を出力して終了する．
- `Yes`を出力しなかった時に，`No`を出力する．
"""
# 標準入力を受け取る．
N, M = map(int ,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# Cを空のリストで作成する．
C = []

# Aの要素をCに追加する．
for a in A:
  # A出身であることを示しながら，Cに追加する．
  C.append([a, "A"])

# Bの要素をCに追加する．
for b in B:
  # B出身であることを示しながら，Cに追加する．
  C.append([b, "B"])

# Cをソートする．
C.sort()

# Cを二つずつ見る．
for i in range(len(C)-1):
  # Cがどこ出身かを見る．
  _, kind0 = C[i]
  _, kind1 = C[i+1]
  
  # 出身が両方ともAのとき，
  if(kind0=="A" and kind1=="A"):
    # Yesを出力して終了する．
    print("Yes")
    exit()

# Yesが出力されなかった時，Noを出力する．
print("No")
```

# C問題
## 方針

- `set`を使うことで，BINGOかどうかの判定を`O(1)`で済ませる．
- これを`T`ターン毎回行っても，計算量は`O(T)`で済ませられる．
- BINGOに穴を開けるのと，その判定は，「縦(`Y`)横(`X`)」と「左上開始の斜め(`TL`)」と「右上開始の斜め(`TR`)」で実装が少々異なる．
- だが，BINGOの`set`に追加して，それがBINGOかどうか判定する部分は共通しているため，関数化する．関数名を`judge`とする．
  - 縦(`Y`)横(`X`)：`A_i - 1`ごとに，該当する行と列の部分で`judge`を実行する．
  - 左上開始の斜め(`TL`): `A_i - 1`ごとに，`N+1`との`mod`が`0`のとき，`judge`を実行する．
  - 右上開始の斜め(`TR`): `A_i - 1`ごとに，`N-1`との`mod`が`0`かつ，`1`以上，`(N**2)-1`未満のとき，`judge`を実行する．
- BINGOが成立しなかったとき，最後に`-1`を出力して，終了する．
## 前提
- `C`問題あたりで，`TLE`になる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の[352回の記事](https://qiita.com/mattsunkun/items/837444254f03e6105922) の`C`問題の解説に記したので，是非参照してほしい．
```C.py
"""
<方針>
- `set`を使うことで，BINGOかどうかの判定を`O(1)`で済ませる．
- これを`T`ターン毎回行っても，計算量は`O(T)`で済ませられる．
- BINGOに穴を開けるのと，その判定は，「縦(`Y`)横(`X`)」と「左上開始の斜め(`TL`)」と「右上開始の斜め(`TR`)」で実装が少々異なる．
- だが，BINGOの`set`に追加して，それがBINGOかどうか判定する部分は共通しているため，関数化する．関数名を`judge`とする．
  - 縦(`Y`)横(`X`)：`A_i - 1`ごとに，該当する行と列の部分で`judge`を実行する．
  - 左上開始の斜め(`TL`): `A_i - 1`ごとに，`N+1`との`mod`が`0`のとき，`judge`を実行する．
  - 右上開始の斜め(`TR`): `A_i - 1`ごとに，`N-1`との`mod`が`0`かつ，`1`以上，`(N**2)-1`未満のとき，`judge`を実行する．
- BINGOが成立しなかったとき，最後に`-1`を出力して，終了する．
"""
# 標準入力を受け取る．
N, T = map(int, input().split())
A = list(map(int, input().split()))

# BINGOの穴あき状態を管理する`set`．
X = [set() for i in range(N)]
Y = [set() for i in range(N)]
TL = set()
TR = set()

# BINGOの`set`に追加して，それがBINGOかどうか判定する
def judge(se, a, t):
  # 集合に追加する．
  se.add(a)
  # BINGOの穴がN個になったとき，
  if(len(se)==N):
    # ターンを出力して終了する．
    print(t+1)
    exit()

# ターン毎に見る．
for i in range(T):
  # A_i - 1を見る．
  a = A[i] - 1
  
  # aをNで割った商と余りをとる．
  di, mo = divmod(a, N)
  
  # 縦方向のBINGOを判定する．
  judge(Y[di], a, i)
  
  # 横方向のBINGOを判定する．
  judge(X[mo], a, i)
  
  # 数字がN+1の倍数の時，
  if(a%(N+1)==0):
    # 左上からの斜めのBINGOを判定する．
    judge(TL, a, i)
  
  # 数字がN-1の倍数 かつ 1~N**2-1の時，
  if(a%(N-1)==0 and 1<=a<(N**2)-1):
    # 右上からの斜めのBINGOを判定する．
    judge(TR, a, i)

# BINGOしなかった時に，-1を出力して終了する．
print(-1)
```

# D問題

- 区間の左と右をリスト`ls`に追加する．その際に，左右をそれぞれ表現する値も追加しておく．今回のケースは，+1を左に，-1を右に追加する．
- `ls`を区間の値でソートし，値が一緒であった場合は，区間の左(+1)が区間の右(-1)よりも左に来るようにソートする．
- 閉じてない区間を何個見ているかの変数`open`を持つ．
- `ls`を左から見ていき，`open`の値を変動させる．だが，`open`をインクリメントする直前で，`open`を`ans`に追加する．
```D.py
"""
<方針>
- 区間の左と右をリスト`ls`に追加する．その際に，左右をそれぞれ表現する値も追加しておく．今回のケースは，+1を左に，-1を右に追加する．
- `ls`を区間の値でソートし，値が一緒であった場合は，区間の左(+1)が区間の右(-1)よりも左に来るようにソートする．
- 閉じてない区間を何個見ているかの変数`open`を持つ．
- `ls`を左から見ていき，`open`の値を変動させる．だが，`open`をインクリメントする直前で，`open`を`ans`に追加する．
"""

N = int(input())
ls = []
for i in range(N):
  l, r = map(int, input().split())
  
  # 最初の引数に値を入れて，その次に，左右を表現する値を追加しておく．
  ls.append([l, +1])
  ls.append([r, -1])
  
# 昇順でソートして，区間の左(+1)が区間の右(-1)よりも左に来るようにする．
ls.sort(key=lambda x: (x[0], -x[1]))

# 答え
ans = 0
# 閉じていない区間の数
open = 0
# 一つずつ見ていく．
for _, p in ls:
  # 区間の右(-1)のとき
  if(p<0):
    open -= 1
  # 区間の左(+1)のとき
  else:
    ans += open
    open += 1

print(ans)
```

# 補足
### 関係するリンク(参考文献など)
- [今回のコンテスト](https://atcoder.jp/contests/abc355)
### 筆者について
- [Atcoderアカウント](https://atcoder.jp/users/mattsunkun)
- [今回の成績(oooo---)](https://atcoder.jp/users/mattsunkun/history/share/abc355)
- [解説で示したA問題の提出](https://atcoder.jp/contests/abc355/submissions/53901592)
- [解説で示したB問題の提出](https://atcoder.jp/contests/abc355/submissions/53901864)
- [解説で示したC問題の提出](https://atcoder.jp/contests/abc355/submissions/53902521)
- [解説で示したD問題の提出](https://atcoder.jp/contests/abc355/submissions/53902819)
### その他
- **間違いを含んでいる可能性があります．**
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
### 最後に一言
- NDA(?)っぽいやつであんま詳しくは言えないけど，月曜日から2週間，ゲキ忙しくなるんすよね．だから(?)，A~Dの解説はいつもより雑いし，EとFは復習してないっすね．．．
- mattsunkunを応援してください！！！