ABC343(Atcoder Beginner Contest)のA~F(A,B,C,D,E,F)問題をPythonで解説(復習)
A問題
- 実際にAとBを足してみる．
- 0~9を順番に見て，それがA+Bに一致していないものがあったら出力する．
- 答えが見つかった瞬間にbreakして，一致していない答えを一つだけ出す．
A.py
"""
<方針>
- 実際にAとBを足してみる．
- 0~9を順番に見て，それがA+Bに一致していないものがあったら出力する．
- 答えが見つかった瞬間にbreakして，一致していない答えを一つだけ出す．
"""
# 入出力を受け取る
A, B = map(int, input().split())
# 答えを0~9まで順番にみる．
for i in range(10):
# A+Bがiと一致していないとき
if(A+B!=i):
# そのiを出力する．
print(i)
# for文から抜ける(このbreakは必須)
break
B問題
- 最初の頂点数Nの次から順番に行をみる．
- その行にて，1となっているところの列を順番に取得する．
- 左から列を見れば，自動で昇順になるので，愚直にprintする．
- 0-indexedになっていることに注意する．
B.py
"""
<方針>
- 最初の頂点数Nの次から順番に行をみる．
- その行にて，1となっているところの列を順番に取得する．
- 左から列を見れば，自動で昇順になるので，愚直にprintする．
- 0-indexedになっていることに注意する．
"""
# 0行目入力受け取り
N = int(input())
# 1~N行目まで順番に見る
for i in range(N):
# i行目(頂点iについての情報)を取得
A = list(map(int, input().split()))
# 頂点iにつながっている他の頂点を格納するリストを準備する．
ans = []
# 列を左から見る．
for j in range(N):
# i行j列の要素を取得
a = A[j]
# 頂点iと頂点jがつながっているとき，
if(a==1):
# 答えに格納する．(0-indexedなので，+1することに注意)
ans.append(j+1)
# ansの中身は昇順に既になっているので，そのままunpackして出力
print(*ans)
C問題
- Nが10**18とかなり大きいので，下から愚直に計算しては，間に合わない(TLE)．
- ならば，10**18の立方根くらいを考える．
- 10**(18/3)→10**6となるため，計算が間に合いそう．
- 回文のチェックはせいぜい，(10**18)の18桁しかないから，計算時間は気にしなくて良い．
- 入力(N)に関わらず，10**18までのテーブルをあらかじめ作っておく．
- そのテーブルから二分探索(筆者はめぐる式二分探索をしました)で入力N以下で最大のものを取得する．
C.py
"""
<方針>
- Nが10**18とかなり大きいので，下から愚直に計算しては，間に合わない(TLE)．
- ならば，10**18の立方根くらいを考える．
- 10**(18/3)→10**6となるため，計算が間に合いそう．
- 回文のチェックはせいぜい，(10**18)の18桁しかないから，計算時間は気にしなくて良い．
- 入力(N)に関わらず，10**18までのテーブルをあらかじめ作っておく．
- そのテーブルから二分探索で入力N以下で最大のものを取得する．
"""
"""
<めぐる式二分探索>
- バグりにくい二分探索の実装です．
- 詳しくは各自調べてみてください．
"""
# 注意，全て満たすor満たさない時は，-1, Nが帰ってくる．
def binSearch(a, sep, rightInclude=True, rev=False):
left = -1
right = len(a)
while (right - left > 1):
mid = left + ((right - left) // 2)
# 大>小 モード
if(rev):
if(a[mid] < sep): right = mid
elif(a[mid] == sep and rightInclude): right = mid
else: left = mid
# 小<大 モード
else:
if(a[mid] > sep): right = mid
elif(a[mid] == sep and rightInclude): right = mid
else: left = mid
# sep境界値とした左右
return left, right
N = int(input())
# テーブルの上限値(10**18)
MAX = 10**18+1
# 回文立方数を格納するテーブル
tabl = []
# 1から順番に10**(18/3)までループを回す．
for i in range(1, int(MAX**(1/3))):
# iを3乗してみる．この段階ではKは立法数である保証しか取れていない．
K = pow(i, 3)
# Kを文字列として扱ってみる．
strK = str(K)
# 回文立方数であるフラグ
ok = True
# 回文であるかをチェックする．
for j in range(len(strK)//2):
# 左からj文字目と右からj文字目をチェックする．
if(strK[j] != strK[len(strK)-1-j]):
# もし，文字が異なっていたら，その時点で回文ではないので，回文フラグを折って，breakする．
ok = False
break
# 回文立方数のとき
if(ok):
# 回文立方数テーブルに追加する．
tabl.append(K)
# 二分探索でN以下の回文立方数の中で最大のものを取得する．
l, r = binSearch(tabl, N, False)
# 答えを出力
print(tabl[l])
D問題
- それぞれのプレイヤーの得点を格納するリストを準備する．
- それぞれのスコアを何人の選手が持っているかの辞書を準備する．
D.py
"""
<方針>
- それぞれのプレイヤーの得点を格納するリストを準備する．
- それぞれのスコアを何人の選手が持っているかの辞書を準備する．
"""
N, T = map(int, input().split())
# プレイヤー(player)の得点のリスト
p = [0]*N
# あるスコア(score)を何人の選手が持っているかの辞書
s = {}
# 最初はみんな(N人)が0点
s[0] = N
# 時間経過を追う
for i in range(T):
a, b = map(int, input().split())
# 0-indexed
a -=1
# 時間経過する前のプレイヤーaの得点
past = p[a]
# 時間を経過させて，プレイヤーaの得点を更新する．
p[a] += b
# 時間経過した後のプレイヤーaの得点
new = p[a]
# プレイヤーaの過去の得点を辞書から一個減らす
s[past] -= 1
# その得点をとっているものがいなくなったとき，辞書から削除する．
if(s[past] == 0):
s.pop(past)
# プレイヤーaの新しい得点が辞書に登録されているとき，辞書の値をインクリメントする．
if(new in s):
s[new] += 1
# プレイヤーaの新しい得点が辞書に無い時は，辞書に新しく登録する．
else:
s[new] = 1
# 得点の多様性は辞書に登録されているスコアの数に等しい．
print(len(s))
E問題
- 3つの立方体の座標がわかれば，定数時間(O(1))で入力の条件を満たすかは判定できる．
- あとは，実行時間に間に合うように，省略できるところを考えていく．
- それぞれの頂点は-100~100の値をとる(20032)
- 重なっている体積を考える上で，頂点は一つ固定しても，問題がない．(20032)
- 他の立方体と接しないような，明らかに重ならないところは考えなくてよくて，近辺(0~14)だけを考えれば良い．(1432)
- 動かす立方体のうち，一つは0~7or7~14にしても良い．なぜなら，最初の立方体から明らかに離れてしまうところは考えなくて良いから．
- また，前述の動かす立方体は，対称性より，0~7を採用しても問題なく，(もちろん7~14でもOK)(a<=b<=c)としても問題ない．(73 * 143 (ただし，a<=b<=cの対称性より計算量は落ちる))
E.py
"""
<方針>
- 3つの立方体の座標がわかれば，定数時間(O(1))で入力の条件を満たすかは判定できる．
- あとは，実行時間に間に合うように，省略できるところを考えていく．
- それぞれの頂点は-100~100の値をとる(200**3**2)
- 重なっている体積を考える上で，頂点は一つ固定しても，問題がない．(200**3**2)
- 他の立方体と接しないような，明らかに重ならないところは考えなくてよくて，近辺(0~14)だけを考えれば良い．(14**3**2)
- 動かす立方体のうち，一つは0~7or7~14にしても良い．なぜなら，最初の立方体から明らかに離れてしまうところは考えなくて良いから．
- また，前述の動かす立方体は，対称性より，0~7を採用しても問題なく，(もちろん7~14でもOK)(a<=b<=c)としても問題ない．(7**3 * 14**3 (ただし，a<=b<=cの対称性より計算量は落ちる))
-
"""
Vs = list(map(int, input().split()))
# 二つの立方体の被っている部分の体積
def D(ls1, ls2):
a1, b1, c1 = ls1
a2, b2, c2 = ls2
x = ls1[0] - ls2[0]
y = ls1[1] - ls2[1]
z = ls1[2] - ls2[2]
if(x<0):
x *= -1
if(y<0):
y *= -1
if(z<0):
z *= -1
lA = max(7-x, 0)
lB = max(7-y, 0)
lC = max(7-z, 0)
return lA*lB*lC
# 3つの立方体全てが被っているところの体積
def T(ls1, ls2, ls3):
a1, b1, c1 = ls1
a2, b2, c2 = ls2
a3, b3, c3 = ls3
A = sorted([a1, a2, a3])
lA = max(A[0]+7 - A[2], 0)
B = sorted(([b1, b2, b3]))
lB = max(B[0]+7 - B[2], 0)
C = sorted(([c1, c2, c3]))
lC = max(C[0]+7-C[2], 0)
return lA*lB*lC
N2 = 8
N3 = 15
for a2 in range(N2):
for b2 in range(N2):
for c2 in range(N2):
# 対称性より，省くことができる．(a<=b<=cのみを考える．)
if(a2>b2 or b2>c2):
continue
for a3 in range(N3):
for b3 in range(N3):
for c3 in range(N3):
# (筆者はコンテスト中，ここを[0, 0, 0]にしてて，無限にエラーしてました🥺)
l1 = [7,7,7]
l2 = [a2, b2, c2]
l3 = [a3, b3, c3]
# 三つの立方体を完全に分離した時の体積の合計値
ally = (7**3) * 3
# 2つ以上の立方体が重なっているところの和(3つ被っているところは3回カウントする．)
dbly = D(l1, l2)+D(l2, l3)+D(l3, l1)
# 3つの立方体全てが重なっているところの体積
triy = T(l1, l2, l3)
# 丁度2つの立方体が重なっている体積
db = dbly-3*triy
# 入力V1の条件を満たすとき
v1 = (Vs[0] == ally-2*db-3*triy)
# 入力V2の条件を満たすとき
v2 = (Vs[1] == db)
# 入力V3の条件を満たすとき
v3 = (Vs[2] == triy)
if(v1 and v2 and v3):
print("Yes")
print(*l1, *l2, *l3)
exit()
print("No")
F問題
- queryとupdateがあるので，おそらくセグ木を使う．
- 二番目に大きいものの個数を求められるように適切に「モノイド」を考える．
- 元を[(最大), (最大の個数), (二番目に最大), (二番目に最大の個数)]とする．
- 1<=Aなので，単位元を[0, 0, 0, 0]とする．
- 関数は二つの元のそれぞれの大小で場合分けして，作成する．
F.py
"""
<方針>
- queryとupdateがあるので，おそらくセグ木を使う．
- 二番目に大きいものの個数を求められるように適切に「モノイド」を考える．
- 元を[(最大), (最大の個数), (二番目に最大), (二番目に最大の個数)]とする．
- 1<=Aなので，単位元を[0, 0, 0, 0]とする．
- 関数は二つの元のそれぞれの大小で場合分けして，作成する．
"""
class clsSegTree:
def __init__(self, arr, func, ide) -> None:
self.func = func
self.ide = ide
self.num = 1 << (len(arr) - 1).bit_length()
self.tree = [ide]*2*self.num
for i in range(len(arr)):
self.tree[self.num + i] = arr[i]
for i in range(self.num - 1, 0, -1):
self.tree[i] = self.func(self.tree[2*i], self.tree[(2*i)+1])
def __getitem__(self, i):
"""index = i の値を求める
"""
return self.tree[i + self.num]
def update(self, k, x):
k += self.num
self.tree[k] = x
while k>1:
self.tree[k>>1] = self.func(self.tree[k], self.tree[k^1])
k >>= 1
def query(self, l, r):
res = self.ide
l += self.num
r += self.num
while l < r:
if l&1:
res = self.func(res, self.tree[l])
l += 1
if r&1:
res = self.func(res, self.tree[r-1])
l >>= 1
r >>= 1
return res
N, Q = map(int, input().split())
A = list(map(int, input().split()))
# 関数
def func(x, y):
new = [-1]*4
if(x[0] != y[0]):
if(x[0] < y[0]):
x, y = y, x
new[0] = x[0]
new[1] = x[1]
if(x[2] > y[0]):
new[2] = x[2]
new[3] = x[3]
elif(x[2] < y[0]):
new[2] = y[0]
new[3] = y[1]
else:
new[2] = x[2]
new[3] = x[3]+y[1]
else:
new[0] = x[0]
new[1] = x[1]+y[1]
if(x[2]<y[2]):
new[2] = y[2]
new[3] = y[3]
elif(x[2]>y[2]):
new[2] = x[2]
new[3] = x[3]
else:
new[2] = x[2]
new[3] = x[3]+y[3]
return new
# セグ木初期化
dp = clsSegTree([[A[i], 1, 0, 0] for i in range(N)], func, [0]*4)
for i in range(Q):
flag, *other = map(int, input().split())
# update
if(flag==1):
p, x = other
dp.update(p-1, [x, 1, 0, 0])
# query
else:
l, r = other
ans = dp.query(l-1, r)
print(ans[3])
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回の成績(ooooxx-)
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
- 解説で示したF問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
最後に一言
- E問題あと一歩届かず．．