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

A問題

スライス [:] を利用する．
A の後ろ側 [N-K:] と， A の前側 [:N-K] を足したものを B とする．
アンパック * を利用して，空白区切りで出力を行う．

A.py

"""
<方針>
- スライス `[:]` を利用する．
- `A` の後ろ側 `[N-K:]` と， `A` の前側 `[:N-K]` を足したものを `B` とする．
- アンパック `*` を利用して，空白区切りで出力を行う．
"""
# 標準入力受け取り
N, K = map(int, input().split())
A = list(map(int, input().split()))

# Bの作成
B = A[N-K:] + A[:N-K]

# 出力
print(*B)

B問題

シミュレーションすれば良い．以下の内容を無限ループする．
- A に含まれる正の要素の個数が 1 以下になったかどうかをみる．
- A を降順に並び替えて，先頭 2 つの要素を 1 減らす操作．これをした時に，カウント cnt を 1 増やす．

B.py

"""
<方針>
- シミュレーションすれば良い．以下の内容を無限ループする．
  - `A` に含まれる正の要素の個数が `1` 以下になったかどうかをみる．
  - `A` を降順に並び替えて，先頭 `2` つの要素を `1` 減らす操作．これをした時に，カウント `cnt` を `1` 増やす．
"""
# 標準入力を受け取る
N = int(input())
A = list(map(int, input().split()))

# カウント
cnt = 0
while True:
  
  """正の要素の個数が1以下になったかどうかを判定する．"""
  # 正の数の個数
  positive = 0
  # 全てのAを見る
  for a in A:
    # 要素が正のとき，
    if(a>0):
      positive += 1
  # 正の数の個数が1以下のとき，
  if(positive <= 1):
    # 無限ループを終える
    break
  
  """Aを降順に並び替えて，先頭二つの要素を1減らす操作"""
  A.sort(reverse=True) # 降順にする
  A[0] -= 1 # 先頭の要素を1減らす
  A[1] -= 1 # 先頭の次の要素を1減らす
  cnt += 1 # カウントを増やす

# 出力
print(cnt)

C問題

方針

H がデカすぎるので，シミュレーション(計算量： O(NH) )したら， TLE する．
T が 3 の倍数の時，ダメージが 3 になるので， H は周期 5 でパターン的に減少していることに気づく．
それぞれの H の要素を 5 で割った時の余り mo だけシミュレーションを行えば，計算量は O(N) になって，間に合う．

前提

C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう．
AとB問題では，基本的に制約条件を見ずにやっても解ける．
しかし，C問題以降では，制約条件を見ないと必ずTLEすると思っても良い．
詳しい話は私の352回の記事のC問題の解説に記したので，是非参照してほしい．

C.py

"""
<方針>
- `H` がデカすぎるので，シミュレーション(計算量： `O(NH)` )したら， `TLE` する．
- `T` が `3` の倍数の時，ダメージが `3` になるので， `H` は周期 `5` でパターン的に減少していることに気づく．
- それぞれの `H` の要素を `5` で割った時の余り `mo` だけシミュレーションを行えば，計算量は `O(N)` になって，間に合う．
"""
# 入力
N = int(input())
H = list(map(int, input().split()))

T = 0
# 敵を前から順番に見る．
for h in H:
  # 5で割る
  di, mo = divmod(h, 5)
  
  # 周期の回数の3倍だけ，Tは増える
  T += 3*di
  
  # シミュレーションを行う
  while True:
    # 敵の体力が0以下になった時，
    if(mo<=0):
      # シミュレーション終了
      break
    
    # 敵に攻撃をする
    T += 1
    # Tが3の倍数のとき，
    if(T%3 == 0):
      # 体力を3減らす
      mo -= 3
    # Tが3の倍数で無い時，
    else:
      # 体力を1減らす
      mo -= 1

# 出力
print(T)

D問題

これは木(辺の本数が N-1 )なので，V_1 から始めて，他の頂点( V_i )に出会ったら，それまでの道程を必要な頂点と考えて良い．
再帰プログラムを，帰りがけで書けばいける．
また，とある頂点が指定された K 個の頂点に含まれるかどうかをすぐ( O(1) )判定するために，リスト W を作っておく．

D.py

"""
<方針>
- これは木(辺の本数が `N-1` )なので，`V_1` から始めて，他の頂点( `V_i` )に出会ったら，それまでの道程を必要な頂点と考えて良い．
- 再帰プログラムを，帰りがけで書けばいける．
- また，とある頂点が指定された `K` 個の頂点に含まれるかどうかをすぐ( `O(1)` )判定するために，リスト `W` を作っておく．
"""
"""
Pythonで再帰を書く時のおまじない．
これを書かないと，TLEや，REになることがある．
"""
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
import sys
sys.setrecursionlimit(10**6)

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

# Eはグラフの辺を表す．
E = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  E[a].append(b) # a->b
  E[b].append(a) # b->a

# 標準入力．0-indexedで受け取る．
V = list(map(lambda x: int(x) - 1, input().split()))

# すぐに指定された頂点かを判定するためのリストを作成
W = [False]*N
for v in V:
  W[v] = True
  
# 必要な頂点である時にTrue
ans = [False]*N

# 再帰的に，必要な頂点かどうかを判定するプログラム
# 引数 v: 必要な頂点かどうかを見る対象
# 引数 p: どこの頂点から見に来たか(親を指す)．これが無いと無限ループになる．
# 戻り値: 引数vが必要な頂点であったかどうか
def rec(v, p):
  
  # 自分自身が必要な頂点であれば，当然必要．
  need = W[v]
  
  # vの隣接頂点を全て見る．
  for u in E[v]:
    # 無限ループを防ぐため，親は見ない．
    if(u==p):
      continue
    
    # 子供に対して，再帰的に見る．
    if(rec(u, v)):
      # 子供が必要な頂点であったら，自分自身も必要
      need = True
  
  # 自分自身が必要な頂点のとき，
  if need:
    # 自分自身が必要であるとグローバルに伝える．
    ans[v] = True
  
  # 自分自身が必要であるかどうかを親(呼び出し元)に伝える
  return need
  
# 必要な頂点どこから始めても答えは定まる．親は無いので，0~N-1以外の数字を選ぶ．今回は適当に-1にする．
import random # 遊び心
rec(V[random.randrange(K)], -1)

# 必要な頂点をカウントして出力
print(ans.count(True))

E問題

公式解説と一緒です．

E.py

"""
<方針>
- 公式解説と一緒です．
"""
N, M, X1 = map(int, input().split())
# イベントを管理する．
# 引数0: 時刻
# 引数1: 駅の場所
# 引数2: 電車の種類
# 引数3: 出発する情報の時にTrueになる
events = []
for i in range(M):
  a, b, s, t = map(int, input().split())
  a -= 1
  b -= 1
  
  events.append([s, a, i, True])
  events.append([t, b, i, False])
events.sort(key=lambda x: (x[0], x[3])) # イベントを時刻順に並べる．次に，到着したものを優先して並べる

# それぞれの駅に一番遅く着くもの
S = [0]*N

# それぞれの電車を最小限で遅延させるもの
X = [0]*M
X[0] = X1 # X1の遅延時間は決まっている

# イベントを見ていく．
for event in events:
  match event:
    # 出発に関する情報のとき，
    case [s, a, i, True]:
      # 遅延時間が題で与えられているものは無視する．
      if(i==0):
        continue
      # 遅延時間を更新する．
      X[i] = max(0, S[a]-s)
    # 到着に関する情報のとき，
    case [t, b, i, False]:
      # 到着の遅いもので更新する．
      S[b] = max(S[b], X[i]+t)

# 出力
print(*X[1:])

F問題

Nim に帰着すればいける．
1 以外で最も割れる回数を計測 cnt する．それが Nim におけるコインの数となる．
Nim に帰着すれば，cnt を XOR で総和を取って，それが 0 かどうかで勝敗がわかる．

F.py

"""
<方針>
- Nim に帰着すればいける．
- `1` 以外で最も割れる回数を計測 `cnt` する．それが Nim におけるコインの数となる．
- Nim に帰着すれば，`cnt` を `XOR` で総和を取って，それが `0` かどうかで勝敗がわかる．
"""
# 入力
N = int(input())
A = list(map(int, input().split()))

# `XOR` の総和
sum = 0
for a in A:
  # 1以外で最も割れる回数
  cnt = 0
  # 自身以外で割れる最大回数を計算．
  for i in range(2, int(a**0.5) + 1):
    # iで割りまくる
    while True:
      di, mo = divmod(a, i)
      # 割り切れたら，
      if(mo == 0):
        # aを更新
        a = di
        # 割れた数を増やす
        cnt += 1
      # 割り切れなかったら，
      else:
        # 次のiへ
        break
    
  # aが素数だっと時，
  if(a!=1):
    # 自身で割る
    cnt += 1
  
  # 割れた回数で `XOR` を取る
  sum ^= cnt

# 答え
print("Bruno" if sum == 0 else "Anna")

補足

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

筆者について

その他

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

最後に一言

コンテストの日，カラオケ🎤&焼肉🍖&オール🌃してました．