LoginSignup
1
0
@mattsunkun

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

Posted at

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

A問題

  • 0 と 1 の falsy や truthy な特性を使って解く．
  • not L and R の時は No
  • L and not R の時は Yes
  • それ以外の時は Invalid である．
A.py
"""
<方針>
- `0` と `1` の `falsy` や `truthy` な特性を使って解く．
- `not L and R` の時は `No`
- `L and not R` の時は `Yes`
- それ以外の時は `Invalid` である．
"""
# 入力
L, R = map(int, input().split())

# Rのとき
if(not L and R):
  print("No")
# Lのとき
elif(L and not R):
  print("Yes")
# 判定不能
else:
  print("Invalid")

B問題

  • シミュレーションを行う．ただし， 0-indexedで行う(0~N-1 の数字のみを利用する．)
  • 入力を受け取り，二つの元素がどう変化するかの配列 A をあらかじめ作っておく．
  • 最初に現在の元素(e) 0 をもち， 0~N-1 を与えていく
  • ただし，現在の元素の方が番号が大きかったら，スワップする．
  • 0-indexed で処理を行っているため，最後の出力に +1 をすることを忘れてはいけない．
B.py
"""
<方針>
- シミュレーションを行う．ただし， `0-indexed`で行う(`0~N-1` の数字のみを利用する．)
- 入力を受け取り，二つの元素がどう変化するかの配列 `A` をあらかじめ作っておく．
- 最初に現在の元素(`e`) `0` をもち， `0~N-1` を与えていく
- ただし，現在の元素の方が番号が大きかったら，スワップする．
- `0-indexed` で処理を行っているため，最後の出力に `+1` をすることを忘れてはいけない．
"""
# 入力
N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

# 現在の元素
e = 0
# シミュレーション
for i in range(N):
  # 現在の元素の方が大きい時は，
  if(e>i):
    # スワップする
    e, i = i, e
  
  # 現在の元素を更新する
  e = A[i][e]

# 現在の元素を出力する．
print(e+1)

C問題

方針

  • 文字が異なる部分を一つずづ変更すれば良い．
  • しかし，どの順番で変更するかを考えないと，計算時間が現実的でない．全パターン試すと， O(len(S)!) になってしまう．
  • 実は，以下の２回に分けて変更すると，効率が最も良い．
    • 先頭から見て，辞書順で大きいやつがあれば，変更する．
    • 後ろから見て，辞書順で小さいやつがあれば，変更する．
  • 以上を行うと， S==T となり，制約を満たす X が得られる．計算時間は O(len(S))

前提

  • C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
  • AとB問題では，基本的に制約条件を見ずにやっても解ける．
  • しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
  • 詳しい話は私の352回の記事 のC問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 文字が異なる部分を一つずづ変更すれば良い．
- しかし，どの順番で変更するかを考えないと，計算時間が現実的でない．全パターン試すと， `O(len(S)!)` になってしまう．
- 実は，以下の２回に分けて変更すると，効率が最も良い．
  - 先頭から見て，辞書順で大きいやつがあれば，変更する．
  - 後ろから見て，辞書順で小さいやつがあれば，変更する．
- 以上を行うと， `S==T` となり，制約を満たす `X` が得られる．計算時間は `O(len(S))`
"""
# 入力
S = list(input())
T = list(input())

# 文字列の長さ
N = len(S)

# 答え
X = []

# 先頭から見る
for i in range(N):
  # 辞書順で大きい時，
  if(S[i]>T[i]):
    # 文字を変える
    S[i] = T[i]
    # 答えに追記
    X.append(S[:])

# 後ろから見る
for i in reversed(range(N)):
  # 辞書順で小さいとき
  if(S[i]<T[i]):
    # 文字を変える
    S[i]=T[i]
    # 答えに追記
    X.append(S[:])
    
# 出力
print(len(X))
for x in X:
  # Xを一つずつ，出力する．
  print("".join(x))

D問題

SortedSet を使う方針

  • 公式解説と一緒です．
D(SortedSet).py
"""
<方針>
- 公式解説と一緒です．
"""
from sortedcontainers import SortedSet
from bisect import bisect

H, W, Q = map(int, input().split())

g1 = [SortedSet() for _ in range(H)]
g2 = [SortedSet() for _ in range(W)]

# 壁を全て登録
for i in range(H):
  for j in range(W):
    g1[i].add(j)
    g2[j].add(i)

# 壁を消す(g1, g2のデータを同時に消す必要があるため．)
def erase(i, j):
  g1[i].discard(j)
  g2[j].discard(i)

for _ in range(Q):
  r, c = map(int, input().split())
  r -= 1;c -= 1
  
  # 壁があったら
  if c in g1[r]:
    # その壁を消す
    erase(r, c)
  # 壁がなかったら
  else:
    # 左右のブロックを削除する
    if(g1[r]):
      m = bisect(g1[r], c)
      for j in [m, m-1]:
        if(0<=j<len(g1[r]) and 0<=g1[r][j]<W):
          erase(r, g1[r][j])
    
    # 上下のブロックを削除する
    if(g2[c]):
      m = bisect(g2[c], r)
      for i in [m, m-1]:
        if(0<=i<len(g2[c]) and 0<=g2[c][i]<H):
          erase(g2[c][i], c)

print(sum([len(g1[i]) for i in range(H)]))

D問題

UnionFind を使う方針

  • ユーザ解説と一緒です．
D(UnionFind).py
"""
<方針>
- ユーザ解説と一緒です．
"""

# 最左右を保持するUnionFind
class UnionFind:
  
  def __init__(self, N):
    # 全体要素数
    self.N = N
    # 根っこの時は，-(要素数)を表し，そうで無い時は，親のインデックス
    self.P = [-1]*N
    # 最左のもの
    self.L = list(range(N))
    # 最右のもの
    self.R = list(range(N))
  
  def find(self, x):
    # 根っこと判定されたとき
    if(self.P[x] < 0):
      # 根っこを返す
      return x
    # 根っこでないとき
    else:
      # 経路圧縮
      self.P[x] = self.find(self.P[x])
      # 親を返す
      return self.P[x]
  
  def union(self, y, x):
    # 根っこを取得
    y = self.find(y)
    x = self.find(x)
    
    # 同一グループだったら終了
    if(x==y):return
    
    # xの方が要素数が小さい時，
    if(-self.P[x] < -self.P[y]):
      # xの方が要素数が大きいようにする
      x, y = y, x 
    
    # xの要素数を増やす
    self.P[x] += self.P[y]
    # yの親をxにする
    self.P[y] = x
    # 最左を更新
    self.L[x] = min(self.L[x], self.L[y])
    # 最右を更新
    self.R[x] = max(self.R[x], self.R[y])
    
  # 最左右を取得
  def LR(self, x):
    # 根っこが最左右のデータを持っているため，根っこに変更
    x = self.find(x)
    return self.L[x], self.R[x]

# 入力 
H, W, Q = map(int, input().split())

# UnionFindを縦横別で保持
ufYX = [UnionFind(W) for _ in range(H)]
ufXY = [UnionFind(H) for _ in range(W)]

# 壁が削除されたかどうか
erased = [[False]*(W) for _ in range(H)]

# 壁を削除する
def erase(y, x):
  # 有効範囲内の時のみ処理
  if(0<=y<H and 0<=x<W):
    # 壁を削除
    erased[y][x] = True
    
    # 上下の壁の最左右を登録
    for d in [-1, 1]:
      Y = y + d
      # 壁が存在する時
      if(0<=Y<H and erased[Y][x]):
        # 最左右を更新
        ufXY[x].union(y, Y)
    
    # 左右の壁の最左右を登録
    for d in [-1, 1]:
      X = x + d
      # 壁が存在する時
      if(0<=X<W and erased[y][X]):
        # 最左右を更新
        ufYX[y].union(x, X)

# シミュレーション
for _ in range(Q):
  # 入力
  y, x = map(int, input().split())
  y -= 1;x -= 1
  
  # 壁が破壊されている時，
  if(erased[y][x]):
    # 上下の壁を壊す
    Lx, Rx = ufYX[y].LR(x)
    erase(y, Lx - 1)
    erase(y, Rx + 1)
    
    # 左右の壁を壊す
    Ly, Ry = ufXY[x].LR(y)
    erase(Ly - 1, x)
    erase(Ry + 1, x)
  
  # 壁が破壊されていない時，
  else:
    # その壁を壊す
    erase(y, x)

# 残った壁の数を計測
print(H*W - sum(sum(erased, [])))

補足

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

筆者について

その他

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

最後に一言

  • D問題が解けそうで解けなくて，時間だけが溶けました🫠🫠🫠
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0