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

A問題

• Z駅がX駅とY駅の間にあるかどうかを判定すれば良い．
• つまり，min(X, Y) <= Z <= max(X, Y)となっているかどうかを見れば良い．

A.py

"""
<方針>
- `Z`駅が`X`駅と`Y`駅の間にあるかどうかを判定すれば良い．
- つまり，`min(X, Y) <= Z <= max(X, Y)`となっているかどうかを見れば良い．
"""
# 標準入力を受け取る．
N, X, Y, Z = map(int, input().split())

# X駅とY駅の間にZ駅があるかを見る．
if(min(X, Y) <= Z <= max(X, Y)):
  # Yesを出力をする．
  print("Yes")
else:
  # Noを出力をする．
  print("No")
  

B問題

• 正しく入力された文字のindexを記録する変数ansを用意する．
• 文字列Sの何番目の文字を見ているかの値nowを保持する．初期値は0
• 文字列Tを左から順番に見ていき，以下を繰り返す．
  • S[now]と合致する文字が見つかった時，0-indexedに注意し，now+1をansに追加し，nowをインクリメントする．

B.py

"""
<方針>
- 正しく入力された文字の`index`を記録する変数`ans`を用意する．
- 文字列`S`の何番目の文字を見ているかの値`now`を保持する．初期値は`0`
- 文字列`T`を左から順番に見ていき，以下を繰り返す．
  - `S[now]`と合致する文字が見つかった時，`0-indexed`に注意し，`now+1`を`ans`に追加し，`now`をインクリメントする．
"""

# 標準入力
S = input()
T = input()

# 正しく入力された文字のindexを記録する変数
ans = []
# 文字列Sの何番目を見ているかを表す値
now = 0

# 文字列Tを順番に見ていく．
for i in range(len(T)):
  # Sの見ている文字と，Tの見ている文字が合致した時，
  if(S[now]==T[i]):
    # nowをインクリメントする．
    now += 1
    # 正しく入力された文字のindexを0-indexに注意して格納する．
    ans.append(i+1)

# 答えを空白区切りで出力する．
print(*ans)

C問題

• 前提
  • A問題，B問題は解けるが，C問題とかでTLEし，その先に進めない読者のために少し解説を詳しく書いた．
  • まず，TLEの意味や主な原因が分からない人は，この記事を見てほしい．
  • さて，前述の記事を見れば，制約条件を見ずに実装すると，TLEするケースがあることが理解できるだろう．
  • 今回の問題で言えば，O(N^2)はTLEするし，O(A)もTLEしてしまう．
  • もし，このC問題でTLEした読者がいれば，恐らくfor文を2重に使ったか，for文の中でsumを使ったからでは無いかと思われる．
  • 結果的に話せば，今回のケースはfor文を並列に使うか，for文の外でsumを使うことで，ACする．
  • つまり，どの実装がO(N)の処理になるかを知る必要がある．
  • それだけでなく，どの実装の組み合わせがO(N+N)=O(N)となり，どの実装の組み合わせがO(N*N)=O(N^2)になるかも知る必要がある．
  • さもなければ，TLEを事前に回避するのは困難になり，頑張って実装したけど，どう足掻いてもTLEということが起きる．
  • 前述の記事などを参考に，計算量の見積もりができるようになって初めて，C問題などが解けるようになると思って欲しい．
  • 今回の解説コードは計算量のわかりやすさのために，実装コードの末尾に計算量を記述する．それも参考に，理解を深めて欲しい．
• 方針
  • 一番上に乗っている巨人が誰かが重要であり，それより下に乗っている巨人の順番は，頭の高さに影響しない．
  • 一番上に乗っている巨人を変えて(O(N))，毎回高さを求める(O(N))と，計算量が(O(N^2))になってしまい，TLEする．
  • 高さを求める計算式は，「全員の肩の高さの和(S)」と「一番上に乗っている巨人の肩と頭の距離sh」の和として計算できる．
  • Sの値は求めるのに計算時間がかかる(O(N))が，一番上に乗っている巨人に依存しないため，一度だけ計算すれば良い(つまり，O(N))．
  • shはO(1)で計算できるが，N人分計算(O(N))し，その最大値(ma)を記録する必要がある(つまり，O(N))．
  • Sとmaは別々で計算できるので，計算時間はO(N+N)=O(N)となり，ACする．

C.py

"""
<前提>
- `A`問題，`B`問題は解けるが，`C`問題とかで`TLE`し，その先に進めない読者のために少し解説を詳しく書いた．
- まず，`TLE`の意味や主な原因が分からない人は，[この記事](https://atcoder.jp/contests/apg4b/tasks/APG4b_w?lang=ja)を見てほしい．
- さて，前述の記事を見れば，制約条件を見ずに実装すると，`TLE`するケースがあることが理解できるだろう．
- 今回の問題で言えば，`O(N^2)`は`TLE`するし，`O(A)`も`TLE`してしまう．
- もし，この`C`問題で`TLE`した読者がいれば，恐らく`for文`を2重に使ったか，`for文`の中で`sum`を使ったからでは無いかと思われる．
- 結果的に話せば，今回のケースは`for文`を並列に使うか，`for文`の外で`sum`を使うことで，`AC`する．
- つまり，どの実装が`O(N)`の処理になるかを知る必要がある．
- それだけでなく，どの実装の組み合わせが`O(N+N)=O(N)`となり，どの実装の組み合わせが`O(N*N)=O(N^2)`になるかも知る必要がある．
- さもなければ，`TLE`を事前に回避するのは困難になり，頑張って実装したけど，どう足掻いても`TLE`ということが起きる．
- 前述の記事などを参考に，計算量の見積もりができるようになって初めて，`C`問題などが解けるようになると思って欲しい．
- 今回の解説コードは計算量のわかりやすさのために，実装コードの末尾に計算量を記述する．それも参考に，理解を深めて欲しい．
<方針>
- 一番上に乗っている巨人が誰かが重要であり，それより下に乗っている巨人の順番は，頭の高さに影響しない．
- 一番上に乗っている巨人を変えて(`O(N)`)，毎回高さを求める(`O(N)`)と，計算量が(`O(N^2)`)になってしまい，`TLE`する．
- 高さを求める計算式は，「全員の肩の高さの和(`S`)」と「一番上に乗っている巨人の肩と頭の距離`sh`」の和として計算できる．
- `S`の値は求めるのに計算時間がかかる(`O(N)`)が，一番上に乗っている巨人に依存しないため，一度だけ計算すれば良い(つまり，`O(N)`)．
- `sh`は`O(1)`で計算できるが，`N`人分計算(`O(N)`)し，その最大値(`ma`)を記録する必要がある(つまり，`O(N)`)．
- `S`と`ma`は別々で計算できるので，計算時間は`O(N+N)=O(N)`となり，`AC`する．
"""
# 標準入力を受け取る．実は，標準入力を受け取るのにも，計算時間がかかる．
N = int(input()) # 入力を一つ受け取るだけなので，O(1)
A = [] # 空の配列を作るだけなのでO(1)
B = [] # 空の配列を作るだけなのでO(1)
for i in range(N): # ループを行っているので，O(N)
  a, b = list(map(int, input().split())) # 処理自体はO(1)であるが，O(N)のループの中で，O(1)の処理を行っているので，O(N*1)=O(N)
  A.append(a) # 処理自体はO(1)であるが，O(N)のループの中で，O(1)の処理を行っているので，O(N*1)=O(N)
  B.append(b) # 処理自体はO(1)であるが，O(N)のループの中で，O(1)の処理を行っているので，O(N*1)=O(N)

# 全員の肩の高さの和
S = sum(A) # 値を一つ一つ足しているので，O(N)

# 巨人の肩と頭の距離の最大値を記録する変数．初期値は0とする．
ma = 0
# 巨人の肩と頭の距離を一つ一つ見る．
for i in range(N): # ループを行っているので，O(N)
  a = A[i] # 配列の長さに依存せず，値を一つ取るだけなのでO(1)．だが，処理自体はO(1)であるが，O(N)のループの中で，O(1)の処理を行っているので，O(N*1)=O(N)
  b = B[i] # 配列の長さに依存せず，値を一つ取るだけなのでO(1)．だが，処理自体はO(1)であるが，O(N)のループの中で，O(1)の処理を行っているので，O(N*1)=O(N)
  sh = b-a # 単純な引き算なのでO(1)．だが，処理自体はO(1)であるが，O(N)のループの中で，O(1)の処理を行っているので，O(N*1)=O(N)
  ma = max(ma, b-a) # maxを得るための単純な比較なのでO(1)．だが，処理自体はO(1)であるが，O(N)のループの中で，O(1)の処理を行っているので，O(N*1)=O(N)
  
# 答えの計算
ans = S+ma # 単純な足し算と代入なのでO(1)
# 答えの出力
print(ans) # 値を出力するだけなのでO(1)

D問題

• 数列Pの値をindexとし，そのPのindexを値とする．配列Qを用意する．
• Qに対して，区間[i:i+K]の値のmaxとminをO(Log_K)で取得する(セグメント木を利用する)．
• 得られたmaxとminの差の最小値を出力する．

D.py

"""
<方針>
- 数列`P`の値を`index`とし，その`P`の`index`を値とする．配列`Q`を用意する．
- `Q`に対して，区間`[i:i+K]`の値の`max`と`min`を`O(Log_K)`で取得する(セグメント木を利用する)．
- 得られた`max`と`min`の差の最小値を出力する．
"""

"""
セグメント木の実装．
maxまたはminのクエリをO(Log_K)で返せるものであれば，セグメント木でなくても良い．
"""
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

N, K = map(int, input().split())
P = list(map(int, input().split()))

INF = 10**10

# Pのindexとvalueを入れ替えた配列．
Q = [-1]*N
for i in range(N):
  p = P[i]-1
  Q[p] = i

# 最大値をクエリできるセグメント木
maSeg = clsSegTree(Q, lambda x, y:max(x, y), -INF)
# 最小値をクエリできるセグメント木
miSeg = clsSegTree(Q, lambda x, y:min(x, y), INF)

# 「最大値と最小値の差」の最小値
ans = INF

# 区間をずらしていく．
for i in range(N-K+1):
  ma = maSeg.query(i, i+K)
  mi = miSeg.query(i, i+K)
  ans = min(ans, ma-mi)
  
print(ans)

E問題

• M回与えられる，K個の頂点同士をフルメッシュに辺を全て描くと，TLEしてしまう．
• 作りたいものは最小全域木なので，コストCが小さい順に見て，UnionFindしていく過程を記録すれば良い．
• 実は，i番目のK個の頂点を見たときに，代表の頂点(なんでも良いが，便宜上最初の頂点(A_i_1)とする．)を基準に，他の頂点(A_i_j)だけunionしても，最小全域木は作れる．
• 最悪のケース(つまり，Gが連結にならないときでも，K_iの和は4*10^5なので，間に合う．

E.py

"""
<方針>
- `M`回与えられる，`K`個の頂点同士をフルメッシュに辺を全て描くと，`TLE`してしまう．
- 作りたいものは最小全域木なので，コスト`C`が小さい順に見て，`UnionFind`していく過程を記録すれば良い．
- 実は，`i`番目の`K`個の頂点を見たときに，代表の頂点(なんでも良いが，便宜上最初の頂点(`A_i_1`)とする．)を基準に，他の頂点(`A_i_j`)だけ`union`しても，最小全域木は作れる．
- 最悪のケース(つまり，`G`が連結にならないときでも，`K_i`の和は`4*10^5`なので，間に合う．
"""

"""
UnionFindの実装．
"""
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
import sys
sys.setrecursionlimit(10**6)
class UnionFind:
  
  def __init__(self, n):
    self.Null = "nullNullUnagi"
    self.n = n
    self.groupCount = n
    # それぞれの根っこ(親)を表す．
    # もし，自分が根っこならば，-(子供の数)が入っている．
    self.parents = [-1] * n
    
  # xの根っこを返す
  def find(self, x):
    # ルートならば
    if self.parents[x] < 0:
      return x
    # 子供ならば(parents[x]が親を指すなら)
    else:
      # 経路圧縮
      self.parents[x] = self.find(self.parents[x]) # 親の親を親とする．
      return self.parents[x]
  
  # xとyを合併する．
  def union(self, x, y):
    xRoot = self.find(x)
    yRoot = self.find(y)
    
    # 根っこが一緒ならば既に併合されている
    if(xRoot == yRoot):
      return
    else:
      self.groupCount -= 1
 
    # Union by Rank
    # 根っこの親は自分の子供の数を表現している．
    if(self.parents[xRoot] < self.parents[yRoot]):
      # なるべく左側を親にする
      xRoot, yRoot = yRoot, xRoot
      
    self.parents[xRoot] += self.parents[yRoot] # 左のノードの子供の数を増やす．
    self.parents[yRoot] = xRoot # 右のノードの親をyRootとして登録する．
    
  # xと同じメンバーの数
  def size(self, x):
    return -self.parents[self.find(x)]
    
  # xとyが同じメンバーか
  def same(self, x, y):
    return self.find(x) == self.find(y)
    
  # xと同じメンバーを返す．
  def members(self, x):
    root = self.find(x) # root処理を一回で済ませるため
    return [i for i in range(self.n) if self.find(i) == root]
      
  # rootメンバーを返す
  def roots(self):
    return [i for i in range(self.n) if self.parents[i] < 0 ]
    

# 標準入力を受け取る．
N, M = map(int, input().split())
E = []
CKA = []
for i in range(M):
  K, C = map(int, input().split())
  A = list(map(lambda x: int(x)-1, input().split()))
  CKA.append([C, K, A])
  
# 一つ目の値がコストなので，コスト順にソートできる．
CKA.sort()

# コストの総和
ans = 0
uf = UnionFind(N)

# コストの低い順番に見ていく．
for i in range(M):
  C, K, A = CKA[i]
  # 最初の頂点とそれ以外の頂点を比較していく．
  for j in range(1, K):
    # まだunionされていないとき，
    if(not uf.same(A[0], A[j])):
      # unionする
      uf.union(A[0], A[j])
      # コストを追加する．
      ans += C

# コストが最小で，最初の頂点を取得する．これは必ずunionされている．
a0 = CKA[0][2][0]

# a0のサイズがNに満ちていない時は，Gは連結でない．
if(uf.size(a0) != N):
  ans = -1
print(ans)

補足

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

• 今回のコンテスト

筆者について

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

その他

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

最後に一言

• Fは解説読んだけど，実装できなかった．．