LoginSignup
2
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

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

Posted at

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

A問題

  • 全体の半分(half)より多い票数を，高橋くん(T)が得ているか，青木くん(A)が得ていたら，勝敗は決定している．
A.py
"""
<方針>
- 全体の半分(`half`)より多い票数を，高橋くん(`T`)が得ているか，青木くん(`A`)が得ていたら，勝敗は決定している．
"""
# 標準入力を受け取っている．
N, T, A = map(int, input().split())

# 全体の半分
half = N//2

# もし，高橋くんor青木くんが全体の半分より多く表を得ていたら，
if(T>half or A>half):
  # 勝敗は決定している．
  print("Yes")
else:
  # 勝敗は決まらず．
  print("No")

B問題

  • 制約の最大 MAX=100 行分の多重リスト( SS )を作成しておく(これに逆順で文字を追記していくこととする)．
  • まず文字列( S )を素直に受け取る．
  • 今までで受け取った文字列で最も長い分( ma )だけ SS に追記する．文字がない時は * で代用する．
  • SS に逆順で文字を入れているので，出力する時は [::-1] を用いて正順に戻す．
B.py
"""
<方針>
- 制約の最大 `MAX=100` 行分の多重リスト( `SS` )を作成しておく(これに逆順で文字を追記していくこととする)．
- まず文字列( `S` )を素直に受け取る．
- 今までで受け取った文字列で最も長い分( `ma` )だけ `SS` に追記する．文字がない時は `*` で代用する．
- `SS` に逆順で文字を入れているので，出力する時は `[::-1]` を用いて正順に戻す．
"""
# 制約の最大行数
MAX = 100
# 標準入力を受け取る
N = int(input())
SS = [[] for _ in range(MAX)]

# 文字列の最大長
ma = 0
# N回文字を受け取る
for i in range(N):
  # 文字を素直に受け取る
  S = input()
  
  # 文字列の最長を更新する．
  ma = max(ma, len(S))
  
  # 文字をSSに追記していく
  for j in range(ma):
    # 追記する文字
    s = None
    
    # 文字があるときは
    if(j<len(S)):
      # その文字を使う
      s = S[j]
    # 文字がない時は，
    else:
      # *で代用する．
      s = "*"
    
    # SSにsを追記する．
    SS[j].append(s)

for i in range(ma):
  # 区切り文字なしで，正順に戻して出力する．
  print("".join(SS[i][::-1]))

C問題

方針

  • バッグに整数がどれだけ格納されているかを管理するリスト( bag )を作成する．
  • 毎回 bag の中にある整数の種類を計算しては O(xQ) で tle してしまう．
  • そこで， bag の中にある整数の数を記録する変数( kinds )を用意する．
  • bag の中にある"任意の整数"の数が 0->1 になる時と， 1->0 となる時に書き換えれば良い．

前提

  • C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
  • AとB問題では，基本的に制約条件を見ずにやっても解ける．
  • しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
  • 詳しい話は私の352回の記事 のC問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- バッグに整数がどれだけ格納されているかを管理するリスト( `bag` )を作成する．
- 毎回 `bag` の中にある整数の種類を計算しては `O(xQ)` で `tle` してしまう．
- そこで， `bag` の中にある整数の数を記録する変数( `kinds` )を用意する．
- `bag` の中にある"任意の整数"の数が `0->1` になる時と， `1->0` となる時に書き換えれば良い．
"""

# バッグの中に入りうる整数の種類の数
MAX = (10**6) + 1

# バッグを初期化する．最初は空
bag = [0]*MAX
# 何も入ってないので，0で初期化する．
kinds = 0

# クエリを処理する．
Q = int(input())
for i in range(Q):
  # クエリを受け取る．
  query = list(map(int, input().split()))
  match query:
    case [1, x]:
      # バッグにxを入れる
      bag[x] += 1
      # 0->1になった時，
      if(bag[x] == 1):
        # 種類が増えた．
        kinds += 1
        
    case [2, x]:
      # バッグからxを取り除く
      bag[x] -= 1
      # 1->0になった時，
      if(bag[x] == 0):
        # 種類が減った．
        kinds -= 1
        
    case [3]:
      # 種類を出力する．
      print(kinds)

D問題

  • 毎回値を計算していては tle するので，あらかじめ累積和を考えることで高速化を行う．
  • 3次元の累積和なので，足しすぎに気をつけて適切に引いてあげる．
  • 立方体でベン図を考えると意外とわかる．
D.py
"""
<方針>
- 毎回値を計算していては `tle` するので，あらかじめ累積和を考えることで高速化を行う．
- 3次元の累積和なので，足しすぎに気をつけて適切に引いてあげる．
- 立方体でベン図を考えると意外とわかる．
"""
# 立体の情報を得る
N = int(input())
A = [[list(map(int, input().split())) for _ in range(N)] for _ in range(N)]

# 累積和を考える．0番目の値は0とする．
B = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
  for j in range(1, N+1):
    for k in range(1, N+1):
      B[i][j][k] = 0
      # 自分自身の値を足す
      B[i][j][k] += A[i-1][j-1][k-1]
      # 自分よりも一個横の奴らも足す
      B[i][j][k] += B[i-1][j][k] + B[i][j-1][k] + B[i][j][k-1]
      # 足しすぎたので，引く
      B[i][j][k] -= B[i-1][j-1][k] + B[i][j-1][k-1] + B[i-1][j][k-1]
      # 引きすぎたので足す．
      B[i][j][k] += B[i-1][j-1][k-1]

# クエリ処理
Q = int(input())
for _ in range(Q):
  x, X, y, Y, z, Z = map(int, input().split())
  
  ans = 0
  # まずは自分自身の位置を足す
  ans += B[X][Y][Z]
  # 足しすぎなので，引く
  ans -= B[x-1][Y][Z] + B[X][y-1][Z] + B[X][Y][z-1]
  # 引きすぎたので足す
  ans += B[x-1][y-1][Z] + B[X][y-1][z-1] + B[x-1][Y][z-1]
  # 引きすぎたので足す
  ans -= B[x-1][y-1][z-1]
  
  print(ans)

E問題

  • x と y 方向で分けて考えても問題ない．
  • それぞれの方向で距離が 0~D となる箇所がいくつあるかを計算する．
  • コストの和が D 以下になるのを累積和を使って効率良く計算する．
E.py
"""
<方針>
- `x` と `y` 方向で分けて考えても問題ない．
- それぞれの方向で距離が `0~D` となる箇所がいくつあるかを計算する．
- コストの和が `D` 以下になるのを累積和を使って効率良く計算する．
"""
# 標準入力を受け取る．
N, D = map(int, input().split())
X = []
Y = []
for i in range(N):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
  
# 引数のリストで距離を計算する．
def distance(A):
  # 引数をソートする．
  A.sort()
  
  # 距離がindexとなる点がいくつあるかをvalueとしたリスト
  ans = [0]*(D+1)
  
  # indexが範囲内の時に，ansに追記する関数
  def ad(a):
    if(a<=D):
      ans[a] += 1
  
  # 最左点における距離
  l = sum(map(lambda x: x - A[0], A))
  
  # 初期値とする
  di = l
  
  # ansに追記
  ad(di)
  
  # 次の点に移動しながらansを更新する．
  for i in range(N-1):
    
    # 次の点までのマスの数
    le = A[i+1] - A[i]
    
    # 横に動くと変動する距離
    de = -( (N - (i+1)) - (i+1) )
    
    # 横に移動させつつansに追記する．
    for j in range(le):
      di += de
      ad(di)
  
  # 最右点における距離
  r = di
  
  # 最左点から左に動かしつつansに追記する．
  for i in range(l+N, D+1, N):
    ad(i)
  
  # 最右点から右に動かしつつansに追記する．
  for i in range(r+N, D+1, N):
    ad(i)
  
  return ans

# X方向での距離を求める
P = distance(X)

# Y方向での距離を求める
Q = distance(Y)

# Y方向での結果の累積和を求める．
QQ = [0] * (D+1)
QQ[0] = Q[0]
for i in range(D):
  QQ[i+1] = QQ[i] + Q[i+1]

# 場合の数
ans = 0
for i in range(D+1):
  # X方向での距離がiとなった時にあり得る場合を足している．
  ans += P[i] * QQ[D-i]

print(ans)

補足

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

筆者について

その他

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

最後に一言

  • 実は ARC181 で入水しました💧🎉
2
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
2
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?