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

A問題

• A_iの値を順番に見ていき，それをKで割った商(di)と余り(mo)を求める．
• moが0のものだけを答えにそのdiを記録する．

A.py

"""
<方針>
- `A_i`の値を順番に見ていき，それを`K`で割った商(`di`)と余り(`mo`)を求める．
- `mo`が`0`のものだけを答えにその`di`を記録する．
"""

# 標準入力受け取り
N, K =map(int, input().split())

# 標準入力受け取り
A = list(map(int, input().split()))

# 答えを格納するリスト
ans = []

# A_iを一つずつ見ていく．
for i in range(N):
  # A_iをKで割った商と余りを求める．
  di, mo = divmod(A[i], K)
  
  # A_iをKで割った余りが0のとき，
  if(mo==0):
    # 答えを格納するリストにA_iをKで割った商を記録する．
    ans.append(di)

# 答えを出力する．
print(*ans)

B問題

• アルファベットa~zを1~26に対応させて，文字列を数字として捉える．
• 文字を切り取る開始位置と終了位置でfor文を2重に回す．
• 切り取った文字列を数値に変換し，それをsetに追加していくことで，重複なく記録できる．

B.py

"""
<方針>
- アルファベット`a~z`を`1~26`に対応させて，文字列を数字として捉える．
- 文字を切り取る開始位置と終了位置で`for`文を2重に回す．
- 切り取った文字列を数値に変換し，それを`set`に追加していくことで，重複なく記録できる．
"""

# 入力
S = input()
# 文字を数字として取得する
T = [ord(S[i]) - ord("a") + 1 for i in range(len(S))]

# 答えのset
ans = set()
# 文字列を切り取る開始位置のfor文
for i in range(len(S)+1):
  # 文字列を切り取る終了位置のfor文
  for j in range(len(S)+1):
    # 開始位置>=終了位置で文字は切り取れないため，
    if(i>=j):
      continue
    
    # 26進数として切り取った数字を取得する．
    s = 0
    # k: index
    # t: 数字
    for k, t in enumerate(T[i:j]):
      s += (pow(27, k))*t
      
    # 答えに重複なく追加する．
    ans.add(s)
    
# 答えを出力する．
print(len(ans))

C問題

<方針>

• 予定日を1週間(A+B)で割った余りで考える．
• その割った余りのうち，「一番目に大きい値(ma1)，二番目に大きい値(ma2)，一番目に小さい値(mi1)，二番目に小さい値(mi2)」の4種類を記録する．
• 以下の3通りのいずれかを満たせば，全て休日の可能性がある．

1. ma - mi < A
2. 0 > B + mi - mi2
3. 0 > B + ma2 - ma

C.py

"""
<方針>
- 予定日を1週間(`A+B`)で割った余りで考える．
- その割った余りのうち，「一番目に大きい値(`ma1`)，二番目に大きい値(`ma2`)，一番目に小さい値(`mi1`)，二番目に小さい値(`mi2`)」の`4`種類を記録する．
- 以下の`3`通りのいずれかを満たせば，全て休日の可能性がある．
1. `ma - mi < A`
2. `0 > B + mi - mi2`
3. `0 > B + ma2 - ma`
"""

# 入力
N, A, B = map(int, input().split())
D = list(map(int, input().split()))

# 無限に大きい値の定義
INF = 10**10

# 一番目に大きい値(`ma1`)，二番目に大きい値(`ma2`)，一番目に小さい値(`mi1`)，二番目に小さい値(`mi2`) 
ma = -INF
mi = INF
ma2 = -INF
mi2 =INF

# 予定を一つずつ見る．
for i in range(N):
  
  # 予定日を1週間で割った余り
  ev = D[i]%(A+B)
  
  # maを更新できるとき
  if(ma<ev):
    # ma2をmaから更新
    ma2 = ma
    # maをevから更新
    ma = ev
  # maを更新できないとき
  else:
    # ma2が更新できるか試みる
    ma2 = max(ma2, ev)
    
  # miを更新できるとき
  if(ev<mi):
    # mi2をmiから更新
    mi2 =mi
    # miをevから更新
    mi = ev
  # miを更新できないとき
  else:
    # mi2が更新できるか試みる
    mi2 = min(mi2, ev)
  

# 条件判定して，出力
if (ma-mi<A):
  print("Yes")
elif(0>B+mi-mi2):
  print("Yes")
elif(0>B+ma2-ma):
  print("Yes")
else:
  print("No")

D問題

• 入力Cを2進数で60桁になるように，0で先頭を埋める．
• Cを2進数で表したときに，1が文字として現れる回数をcとする．
• XとYの排他的論理和を取ったとき，それを2進数で表現したときに1が文字として現れる回数の最小値(mi)と最大値(ma)を計算する．
• その最小値(mi)から2ずつ増やした個数であれば，XとYの排他的論理和でその個数の1を文字として表すことができる．
• 上述の値の中にcという値が出るのであれば，ペア(X, Y)は存在すると言える．
• 以下，ペアの求め方．Cを順番に見ていく．
• 0が現れたときは，XとYそれぞれに2**iを足す．Cを満たす回数加算した場合は加算しない．
• 1が現れたとき，aとbの大きい方にその差分だけ2**iを足す．差分以降は，XとYそれぞれに交互に足していく．

D.py

"""
<方針>
- 入力`C`を`2`進数で`60桁`になるように，`0`で先頭を埋める．
- `C`を`2`進数で表したときに，`1`が文字として現れる回数を`c`とする．
- `X`と`Y`の排他的論理和を取ったとき，それを`2`進数で表現したときに`1`が文字として現れる回数の最小値(`mi`)と最大値(`ma`)を計算する．
- その最小値(`mi`)から2ずつ増やした個数であれば，`X`と`Y`の排他的論理和でその個数の`1`を文字として表すことができる．
- 上述の値の中に`c`という値が出るのであれば，ペア`(X, Y)`は存在すると言える．
- 以下，ペアの求め方．`C`を順番に見ていく．
- `0`が現れたときは，`X`と`Y`それぞれに`2**i`を足す．`C`を満たす回数加算した場合は加算しない．
- `1`が現れたとき，`a`と`b`の大きい方にその差分だけ`2**i`を足す．差分以降は，`X`と`Y`それぞれに交互に足していく．
"""

a, b, C = map(int, input().split())

# 2進数表記にして，0埋めで60桁にする．
binC = list(reversed(bin(C)[2:]))
binC += "0"*(60-len(binC))

# 1が何回出てくるか求める．
c = 0
for item in binC:
  if(item=="1"):
    c += 1

# aとbの排他的論理和で表示できる1の回数の最小値と最大値
mi = abs(a-b)
ma = -1
# a+bが60を越えるかで求め方が変わる．
if(a+b<60):
  ma = a+b
else:
  ma = 60*2 - (a+b)

# Cが実現できるかを判定している．同時に，XとYそれぞれ同時に1にする回数(dup)を求める．
dup = -1
# miからmaまで2ずつ増やしてcと一致するかをみる．
for i in range(mi, ma+1, 2):
  # cと一致すれば
  if(i==c):
    # 補足: moは必然的に0になる．
    di, mo = divmod(c - abs(a-b), 2)
    dup = min(a, b) - di
    break
  
# Cは実現不可能
if(dup==-1):
  print(-1)
  exit()

# XとYを求めて行く．
X = 0 # 答え
Y = 0 # 答え
cntSin = 0 # aまたはbの大きい方に足した回数
flagX = False # XとY交互に足すためのフラグ．
cntDup = 0 # XとY同時に足した回数．
for i in range(60):
  if(binC[i]=="0"):
    if(cntDup<dup):
      cntDup += 1
      # XとYを同時に足す．
      X += 2**i
      Y += 2**i
  else:
    if(cntSin<abs(a-b)):
      cntSin += 1
      # XまたはYにaとbの大きい方に足す．
      if(a<b):
        Y += 2**i
      else:
        X += 2**i
    else:
      flagX = not flagX
      # XとYを交互に足す．
      if(flagX):
        X += 2**i
      else:
        Y += 2**i

print(X, Y)

E問題

• x_iがSに入る時を配列Eに記録する．
• クエリ毎の加算する値を累積和として配列Bに記録する．
• x_iがSから抜けるときに，該当するAの位置に加算する．
• Sから抜けれなかったものは，最後に加算する．

E.py

"""
<方針>
- `x_i`が`S`に入る時を配列`E`に記録する．
- クエリ毎の加算する値を累積和として配列`B`に記録する．
- `x_i`が`S`から抜けるときに，該当する`A`の位置に加算する．
- `S`から抜けれなかったものは，最後に加算する．
"""

N, Q = map(int, input().split())
X = list(map(int, input().split()))

A = [0]*N
S = set()
B = [0]*(Q+1) # 加算の累積和
E = [-1]*N # i番目の値がSに入った時のindexを管理

for i in range(Q):
  x = X[i] - 1 # 0-indexedにする．
  
  # Sに入っている
  if(x in S):
    # Sから排除
    S.remove(x)
    # Aに加算
    A[x] += B[i] - B[E[x]]
  # Sにまだない
  else:
    # Sに追加
    S.add(x)
    # この瞬間を記録
    E[x] = i
  
  # 加算の累積和を作成
  B[i+1] = B[i] + len(S)
  
# Sの中に余っているものについて
for s in S:
  # Aに加算する．
  A[s] += B[-1] - B[E[s]]
  
print(*A)

補足

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

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

筆者について

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

その他

• 間違いを含んでいる可能性があります．
• 方針と言いつつ，方針ではない感想などを書いている可能性があります．
• A問題から解説がだんだん省略されます．

最後に一言

• Fは実装が無限にバグったので，記事に書けませんでした．．