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")
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 不参加より成績無し
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
- 解説で示したF問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- コンテストの日，カラオケ🎤&焼肉🍖&オール🌃してました．