Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mattsunkun

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

Posted at

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

A問題

  • 0-indexedでカウントして，3~5文字目の数字を取り出す．
  • その数字をnumとおいて，0<num<350かつnum!=316であることを確認する．
A.py
"""
<方針>
- 0-indexedでカウントして，3~5文字目の数字を確認する．
- その数字を`num`とおいて，`0<num<350`かつ`num != 316`であることを確認する．
"""

# 標準入力を受け取る．
S = input()

# 3~5文字目の数字を切り取り，それを数値として受け取る．
num = int(S[3:6])

# 数字が 0<num<350 かつ num!=316 のとき
if(0<num<350 and num!=316):
  # Yesを出力する．
  print("Yes")
else:
  # Noを出力する．
  print("No")

B問題

  • t番目の🦷が生えていたら，True，生えてなかったらFalseが入っている配列Aを用意する．
  • t番目の🦷の治療を行うときは，配列Aのt番目の値を反転させれば良い．
  • 最後に配列Aに格納されているTrueの個数をカウントすれば，それが🦷の生えている本数となる．
B.py
"""
- `t`番目の🦷が生えていたら，`True`，生えてなかったら`False`が入っている配列`A`を用意する．
- `t`番目の🦷の治療を行うときは，配列`A`の`t`番目の値を反転させれば良い．
- 最後に配列`A`に格納されている`True`の個数をカウントすれば，それが🦷の生えている本数となる．
"""

# 標準入力から受け取る．
N ,Q  = map(int, input().split())
T = list(map(int, input().split()))

# 🦷が生えているかを管理する配列．最初は全部生えているので，Trueで埋める．
A = [True]*N

# 治療を行う．
for i in range(Q):
  # i回目に治療する🦷の場所を取得する．
  t = T[i]
  t -= 1 # 0-indexedにするため，-1する．
  
  # 配列Aのt番目の値を反転させる．
  A[t] = not A[t]
  
# Trueが格納されている個数を出力する．
print(A.count(True))

C問題

  • 標準入力の配列を愚直に左から順番に入れ替える．
  • だが，入れ替え先を毎回参照しては，計算量がO(N^2)になってしまい，TLEしてしまう．
  • そこで，計算量をO(N)にするために，以下の配列AとBを用意する．
    • A: 標準入力から受け取ったAに-1して格納したもの．
    • B: 配列Aにおいて，key: i，value: aとしたときの，key: a，value: iを格納したもの．
  • 配列Bを利用することで，入れ替え先がO(1)で見つかり，全体ではO(N)でACする．
C.py
"""
<方針>
- 標準入力の配列を愚直に左から順番に入れ替える．
- だが，入れ替え先を毎回参照しては，計算量が`O(N^2)`になってしまい，`TLE`してしまう．
- そこで，計算量を`O(N)`にするために，以下の配列`A`と`B`を用意する．
  - `A`: 標準入力から受け取った`A`に`-1`して格納したもの．
  - `B`: 配列`A`において，`key: i`，`value: a`としたときの，`key: a`，`value: i`を格納したもの．
- 配列`B`を利用することで，入れ替え先が`O(1)`で見つかり，全体では`O(N)`で`AC`する．
"""

# 標準入力から受け取る.

N = int(input())
_A = list(map(int, input().split()))

# 配列Aと配列Bを作成する.
A = [-1]*N
B = [-1]*N
for i in range(N):
  a = _A[i] - 1
  A[i] = a
  B[a] = i
  
# 入れ替える順序を格納する配列
ans = []

# 入れ替える文字を左から見る．
for src in range(N):
  # 入れ替え元の文字を取得
  a = A[src]
  
  # 入れ替え元の文字が正しいところにある時は，入れ替えを行わない．
  if(src==a):
    continue
  
  # 入れ替え先の文字の場所を取得する．
  dst = B[src]
  
  # 入れ替え元と入れ替え先の文字の場所を登録する．ただし，問題文より，昇順に格納するように注意する．
  ans.append(sorted((src+1, dst+1)))
  
  # 配列Aの中身を実際に入れ替える．
  A[src], A[dst] = A[dst], A[src]
  
  # 配列Bに関しても入れ替える．
  B[src] = src
  B[a] = dst
  

# 答えを出力する．
print(len(ans))
for item in ans:
  print(*item) # 配列のunpack(*)を行うことで空白区切りで出力できる．

D問題

  • 以下，グラフ理論の簡単な用語を知っており，UnionFindの使い方(仕組みはぶっちゃけどうでも良い)も知っているものとする．
  • 仮に，グラフの頂点間を毎回計測するとなると，O(N^2)かかってしまうので，計算量を減らせる方法が絶対ありそう．
  • 実は，友達の友達は必ず友達になれる！！
  • 前述の理論を用いると，頂点数nの連結なグラフは全員お友達になれる．フルメッシュな辺の本数はn(n-1)/2という式でO(1)で求められる．
  • よって，標準入力から構築できるグラフG(N, M)(厳密な表記ではない)において，
    • どう連結しているかが重要では無い．
    • どの頂点同士が連結しているかが重要．
    • その連結している頂点には何本の辺が既に構築されているかが重要．
  • つまり，UnionFindを使えばよくね！！
  • さらに，連結グラフに何本の辺が使われているかは，グラフ全体でカウント(つまりM本になる)すればよいので，個別でカウントする必要がない．
D.py
"""
<方針>
- 以下，グラフ理論の簡単な用語を知っており，`UnionFind`の使い方(~~仕組みはぶっちゃけどうでも良い~~)も知っているものとする．
- 仮に，グラフの頂点間を毎回計測するとなると，`O(N^2)`かかってしまうので，計算量を減らせる方法が絶対ありそう．
- 実は，友達の友達は必ず友達になれる！！
- 前述の理論を用いると，頂点数`n`の連結なグラフは全員お友達になれる．フルメッシュな辺の本数は`n(n-1)/2`という式でO(1)で求められる．
- よって，標準入力から構築できるグラフ`G(N, M)`(厳密な表記ではない)において，
  - どう連結しているかが重要では無い．
  - どの頂点同士が連結しているかが重要．
  - その連結している頂点には何本の辺が既に構築されているかが重要．
- つまり，`UnionFind`を使えばよくね！！
- さらに，連結グラフに何本の辺が使われているかは，グラフ全体でカウント(つまり`M`本になる)すればよいので，個別でカウントする必要がない．
"""
"""
以下，UnionFindの実装
"""
# これはfindで再起を使っているから．
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 ]
"""
以上が，UnionFindの実装
"""


N, M = map(int, input().split())

# UnionFindの初期値
uf = UnionFind(N)

# 入力された辺の情報を見ていく．
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1

  # UnionFindを使って，クラスタの形成
  uf.union(a, b)
  
# 友達に新しくなる回数の登録
ans = 0
# クラスタの代表(root)を一つずつみる．
for r in uf.roots():
  # そのクラスタの頂点数における，フルメッシュ構築時の辺の本数．
  ans += (uf.size(r)*(uf.size(r)-1)//2)
  
# 既に構築されている辺の本数を引けば，答えになる．
print(ans-M)

E問題

  • 公式解説通りです．
  • このコードの特色を先に述べます．
    • Pythonは再帰が遅いので，非再帰でメモ化再帰を行う．理由が気になる人は調べてみてください．
    • 10**18>1024M より，愚直な配列はメモリが足りないので，メモ化は辞書型で行う．
E.py
"""
<方針>
- 公式解説通りです．
- このコードの特色を先に述べます．
  - Pythonは再帰が遅いので，非再帰でメモ化再帰を行う．理由が気になる人は調べてみてください．
  - `10**18>1024M` より，愚直な配列はメモリが足りないので，メモ化は辞書型で行う．
"""
from collections import deque

N, A, X, Y = map(int, input().split())

# メモ
di = {}
# N=0は期待値0として登録する．
di[0] = 0

# 非再帰メモ化を行うqueue
q = deque()

# 初期値を代入する．
q.append([N, False])
q.append([N, True])

while q:
  # DFS
  n, fla = q.pop()
  
  # メモ化で遷移する時，まだ必要な値が求まっているかわからない時
  if(fla):
    # 2~6で割った値で
    for i in range(2, 7, 1):
      # メモ化されていれば探索を行わない．
      if(n//i in di):
        continue
      # queueに追加する．
      q.append([n//i, False])
      q.append([n//i, True])
  # メモ化で遷移する時，必要な値がわかっているはずなので，
  else:
    di[n] = min(X+di[n//A], 6/5*Y+sum([di[n//i] for i in range(2, 7, 1)])/5)
    
print(di[N])

F問題

  • 公式解説通りです．
  • ざっくり解説すると，問題を2段階に切り分けます．
    • 最初に大小の反転だけを行う．
    • 次に，"("or")"を見つけるたびに，文字列を反転トレースして，再帰的に探索する．
  • まあ，詳細はコードのコメントを参照してください(●´ω｀●)
F.py
"""
<方針>
- 公式解説通りです．
- ざっくり解説すると，問題を2段階に切り分けます．
  - 最初に大小の反転だけを行う．
  - 次に，"("or")"を見つけるたびに，文字列を反転トレースして，再帰的に探索する．
- まあ，詳細はコードのコメントを参照してください(●´ω｀●)
"""
from collections import deque

S = input()

"""
入力された文字(1文字)の，大小を反転させたものを戻り値として返す．
"""
def invChar(s:str)->str:
  # 入力が小文字の時，
  if(ord(s) - ord("a") >= 0):
    # 大文字を返す．
    return chr(ord(s) - ord("a") + ord("A"))
  # 入力が大文字の時，
  else:
    # 小文字を返す．
    return chr(ord(s) + ord("a") - ord("A"))

"""
大文字小文字を反転させたものを文字列Tに変換する．
"""
T = [] # 大小を反転させたものを格納する．
isInv = False # 大小を反転するかのフラグ．"("or")"の文字を見るたびに，このフラグが反転する．
P = deque() # "("を見つけるたびにそのindexを格納するqueue．")"を見つけると番(つがい)判定し，popする．
pair = [-1]*len(S) # 番を登録する配列．相手のindexを登録する．
for i in range(len(S)):
  # Tに格納する文字．反転フラグが立ってる時は，大小を反転させて格納する．
  s = S[i]
  
  # 括弧の文字の時，
  if(s=="(" or s==")"):
    isInv = not isInv # フラグを反転
    if(s=="("):
      # 番のqueueに追加
      P.append(i)
    else:
      # 番を取り出す．
      x = P.pop()
      # 番を登録する．
      pair[x] = i
      pair[i] = x
  # 通常の文字の時，
  else:
    # 文字を反転させるフラグの時，
    if(isInv):
      # 文字を反転する．
      s = invChar(s)
    
  # Tに格納する．  
  T.append(s)

T = "".join(T) # Tを文字列にしている．(特に意味はない．)

"""
文字を左から見たり，右から見たりして，最終的な答えを導き出す．
"""
# 非再帰BFSをするqueue
q = deque()

# 第一引数：探索を行う左端
# 第二引数：探索を行う右端
# 第三匹数：探索を右から左へ行うときにTrueになるフラグ．
q.append([0,len(S)-1, False]) # 文字列全体を左から右へ探索する．

# 答えの文字列を格納する配列
ans = []

while q:
  # BFS
  l, r, isInv = q.pop()
  
  # "()"のように連続している文字列を探索すると，l>rとなるため．
  if(l>r):
    continue
  
  # 右から左へ文字を見る時
  if(isInv):
    for i in range(r, l-1, -1):
      # 左から右を見る必要が出た時，
      if(T[i] == ")"):
        # 相手である"("のindexを取得する．
        p = pair[i]
        # "("が今回の探索対象の左端でない時，
        if(l<p):
          # 左端~"("までを右から左へ探索を行う．
          q.append([l, p-1, True])
        # 番の間である"(......)"を左から右へ探索する．
        q.append([p+1, i-1, False])
        # 左から右へ見る必要が出たので，breakする．
        break
      # 通常の文字を感知したとき，
      else:
        # 文字を答えを格納する．
        ans.append(T[i])
        
  # 左から右へ探索する時も，前述のコメントと同じ考え方でできるため，コメントを省略する．
  else:
    for i in range(l, r+1, 1):
      if(T[i] == "("):
        p = pair[i]
        if(p<r):
          q.append([p+1, r, False])
        q.append([i+1, p-1, True])
        break
      else:
        ans.append(T[i])
        
print("".join(ans))

補足

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

筆者について

その他

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

最後に一言

  • みんな🦷は大事にしようね(´∀｀)
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

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?