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回の記事の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)

補足

関係するリンク(参考文献など)

今回のコンテスト

筆者について

その他

間違いを含んでいる可能性があります．
方針と言いつつ，方針ではない感想などを書いている可能性があります．
A問題から解説がだんだん省略されます．
コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．

最後に一言

NDA(?)っぽいやつであんま詳しくは言えないけど，月曜日から2週間，ゲキ忙しくなるんすよね．だから(?)，A~Dの解説はいつもより雑いし，EとFは復習してないっすね．．．
mattsunkunを応援してください！！！