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

A問題

• 問題文の条件より，高橋チームの合計点Aは青木チームの合計点Bよりも高い．
• A-Bが9回表終了時の点差になる．
• 勝つためには，引き分けよりも1点高くなる必要があるので，A-B+1を出力して終了．

A.py

"""
<方針>
- 問題文の条件より，高橋チームの合計点`A`は青木チームの合計点`B`よりも高い．
- `A-B`が9回表終了時の点差になる．
- 勝つためには，引き分けよりも`1`点高くなる必要があるので，`A-B+1`を出力して終了．
"""
# 標準入力を受け取り，その合計値を記録している．
A = sum(map(int, input().split()))
B = sum(map(int, input().split()))

print(A-B+1)

B問題

• AとBの文字を一つずつ見ていく．
• 文字が異なっているところを見つけたら，その座標を出力して終了する．
• 0-indexedであることに注意して出力する．

B.py

"""
<方針>
- `A`と`B`の文字を一つずつ見ていく．
- 文字が異なっているところを見つけたら，その座標を出力して終了する．
- `0-indexed`であることに注意して出力する．
"""
# 標準入力受け取り
N = int(input())
A = []
B = []
for i in range(N):
  # 標準入力受け取り
  A.append(input())
for i in range(N):
  # 標準入力受け取り
  B.append(input())

# 文字を縦に見ていく．
for i in range(N):
  # 文字を横に見ていく．
  for j in range(N):
    # 文字が異なるところを見つけたら
    if(A[i][j]!=B[i][j]):
      # 0-indexedなので，座標に+1させて出力する．
      print(i+1, j+1)
      # プログラムを終了する．
      exit()

C問題

• リストAから要素を毎度取り出し，それをstackに格納する．
• stackに格納する値はA_iで良い．2**A_iは格納しない．
• そして，2倍した値を格納する時は，A_i+1を格納すれば良い．
• 問題文で指示されていることを愚直にやっても計算量はO(NlogN)なので，問題ない．

C.py

"""
<方針>
- リスト`A`から要素を毎度取り出し，それを`stack`に格納する．
- `stack`に格納する値は`A_i`で良い．`2**A_i`は格納しない．
- そして，`2`倍した値を格納する時は，`A_i+1`を格納すれば良い．
- 問題文で指示されていることを愚直にやっても計算量は`O(NlogN)`なので，問題ない．
"""
# 標準入力
N = int(input())
A = list(map(int,input().split()))

# 値を格納するスタック
stack = []
for i in range(N):
  # スタックに追加
  stack.append(A[i])
  
  # スタックの要素数が2以上の時は以下を繰り返す．
  while len(stack)>1:
    # 要素を二つ取り出す．
    a = stack.pop()
    b = stack.pop()
    
    # 値が異なれば，
    if(a!=b):
      # 要素を戻す．
      stack.append(b)
      stack.append(a)
      # while文から抜ける
      break
    # 値が同じであれば，
    else:
      # 最後に2倍した値(+1した値)を追加する．
      stack.append(a+1)

# 残っている要素数を出力する．
print(len(stack))

D問題

• それぞれのマスについて以下の内容を繰り返す．
  • このマスと上下左右に🧲が無く，後述のBFSで「探索済み」でなければ，以下の処理を行います．
    • 現在のマスから4方にBFSを行い，現在のマスを「探索済み」にする．
    • 4方全てのマスに🧲がなく，**今回のBFS**において，「探索済み」で無いマスに対してBFSを行う．
  • 今回探索を行ったマスの個数が今までの探索の中で最も多かったら，その回数を更新する．

D.py

"""
<方針>
- それぞれのマスについて以下の内容を繰り返す．
  - このマスと上下左右に🧲が無く，後述の`BFS`で「探索済み」でなければ，以下の処理を行います．
    - 現在のマスから4方に`BFS`を行い，現在のマスを「探索済み」にする．
    - 4方全てのマスに🧲がなく，**今回の`BFS`**において，「探索済み」で無いマスに対して`BFS`を行う．
  - 今回探索を行ったマスの個数が今までの探索の中で最も多かったら，その回数を更新する．
"""
from collections import deque

# 開始位置が(i, j)において，探索済みであることを表す一意な整数を返す関数．
def num(i, j):
  return (i+1)*10000 + (j+1)
  
## 盤面を受け取る．
# 0: 何もない
# -1: 磁石あり．
H, W = map(int, input().split())
AA = []
for i in range(H):
  S = input()
  A = []
  for j in range(W):
    s = S[j]
    if(s == "#"):
      A.append(-1)
    else:
      A.append(0)
      
  AA.append(A)

# 自由度の初期値．
ans = -1
# それぞれのマスについて捜査する．
for i in range(H):
  for j in range(W):
    # 「探索済み」であれば，次のマスを探索する．
    if(AA[i][j] != 0):
      continue
    
    # 上下左右に磁石があれば，Falseになるフラグ
    ok = True
    # 上下左右を確認
    for k in range(4):
      y = i
      x = j
      if(k==0):
        y -= 1
      if(k==1):
        y += 1
      if(k==2):
        x -= 1
      if(k==3):
        x += 1
      # 磁石があれば，
      if(0<=y<H and 0<=x<W and AA[y][x] == -1):
        ok = False
    
    # 上下左右のどこかに磁石があれば，
    if(not ok):
      continue
    
    # BFSを行うdeque
    q = deque()
    q.append((i, j))
    # 探索を行ったマスの個数．
    ansTmp = 0
    while q:
      # BFS
      _y, _x = q.popleft()
      
      # そのマスが今回のBFSで探索済みであれば，探索を行わない．
      if(AA[_y][_x] == num(i, j)):
        continue
      
      # 上下左右の座標を格納するリスト
      tmp = []
      # 上下左右のどこかが磁石であれば，Falseが格納されるフラグ
      ok = True
      # 上下左右で探索
      for k in range(4):
        y = _y
        x = _x
        if(k==0):
          y -= 1
        if(k==1):
          y += 1
        if(k==2):
          x -= 1
        if(k==3):
          x+= 1
        
        # 枠外になければ，
        if(0<=y<H and 0<=x<W):
          # 磁石であれば，
          if(AA[y][x] == -1):
            ok = False
          # 今回探索済みでなければ，
          elif(AA[y][x] != num(i, j)):
            tmp.append((y, x))
            
      # 上下左右に磁石がなければ，
      if(ok):
        # 探索対象に追加する．
        for item in tmp:
          q.append(item)
        
      # 今回探索したことを記録する．
      AA[_y][_x] = num(i, j)
      # 探索したマスの個数を増やす．
      ansTmp += 1
    
    # 記録を更新する．
    ans = max(ansTmp,ans)

# 全ての空きマスが磁石に隣接していると，BFSを行えないことがあるため，その場合は，答えを1にする．
if(ans==-1):
  ans = 1

print(ans)

E問題

• 公式解説通りです．
• 公式解説に書いてあるコードをPythonで書いただけです．

E.py

"""
<方針>
- 公式解説通りです．
- 公式解説に書いてあるコードを`Python`で書いただけです．
"""
N = int(input())

A = [[] for i in range(4)] # 偶奇*(xとy)で4つのリストを格納
for i in range(N):
  X, Y = map(int, input().split())
  
  # 偶奇に分けて格納．
  if((X+Y)%2==0):
    A[0].append(X+Y)
    A[1].append(X-Y)
  else:
    A[2].append(X+Y)
    A[3].append(X-Y)
    
# カウントしていく．
ans = 0
for i in range(4):
  a = sorted(A[i])
  for j in range(len(a)):
    ans += a[j]*(2*j+1-len(a))

# 2回カウントしているので，2で割る．
print(ans//2)

F問題

• 公式解説通りです．
• 公式解説に書いてあるコードのうち，以下の内容を変更しました．
  • FenwickTree → セグ木
  • bisect → めぐる式2分探索

F.py

"""
<方針>
- 公式解説通りです．
- 公式解説に書いてあるコードのうち，以下の内容を変更しました．
  - FenwickTree → セグ木
  - bisect → めぐる式2分探索
"""

"""セグ木の実装"""
class clsSegTree:
  def __init__(self, arr, func, ide) -> None:
    self.func = func
    self.ide = ide
    self.num = 1 << (len(arr) - 1).bit_length()
    self.tree = [ide]*2*self.num
    for i in range(len(arr)):
      self.tree[self.num + i] = arr[i]
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.func(self.tree[2*i], self.tree[(2*i)+1])
  
  def __getitem__(self, i):
    """index = i の値を求める
    """
    return self.tree[i + self.num]

  def update(self, k, x):
    k += self.num
    self.tree[k] = x
    while k>1:
      self.tree[k>>1] = self.func(self.tree[k], self.tree[k^1])
      k >>= 1
  
  def query(self, l, r):
    res = self.ide
    l += self.num
    r += self.num
    while l < r:
      if l&1:
        res = self.func(res, self.tree[l])
        l += 1
      if r&1:
        res = self.func(res, self.tree[r-1])
      l >>= 1
      r >>= 1
        
    return res

"""めぐる式2分探索"""
# 注意，全て満たすor満たさない時は，-1, Nが帰ってくる．
def binSearch(a, sep, rightInclude=True, rev=False):
  left = -1
  right = len(a)
  
  while (right - left > 1):
    mid = left + ((right - left) // 2)
    
    # 大>小 モード
    if(rev):
      if(a[mid] < sep): right = mid
      elif(a[mid] == sep and rightInclude): right = mid
      else: left = mid
    # 小<大 モード
    else:
      if(a[mid] > sep): right = mid
      elif(a[mid] == sep and rightInclude): right = mid
      else: left = mid
  
  # sep境界値とした左右
  return left, right

N = int(input())
A = list(map(int, input().split()))
B = sorted(list(set(A)))

C = clsSegTree([0]*N, lambda x, y:x+y, 0)
S = clsSegTree([0]*N, lambda x, y:x+y, 0)

ans = 0
for i in reversed(range(N)):
  l, _ = binSearch(B, A[i], False)
  
  ind = l
  
  c = C.query(ind, N)
  s = S.query(ind, N)
  
  ans += s - c*A[i]
  
  C.update(ind, 1+C.query(ind, ind+1))
  S.update(ind, A[i]+S.query(ind, ind+1))
  
print(ans)

補足

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

• 今回のコンテスト
• E問題の公式解説
• F問題の公式解説

筆者について

• Atcoderアカウント
• 今回の成績(ooooxx-)
• 解説で示したA問題の提出
• 解説で示したB問題の提出
• 解説で示したC問題の提出
• 解説で示したD問題の提出
• 解説で示したE問題の提出
• 解説で示したF問題の提出

その他

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

最後に一言

• 風来のシレンというゲームが好きです．好きな配信者さんを一部紹介します．
• しらたきさん
• ごましおいやんさん
• おんさん
• 菓郎さん
• U字🧲さん
  などなど．．