ABC435の振り返りをします。
A問題
$n$番目の三角数は$\frac{n(n+1)}{2}$で求められます。
提出コードです。
a.py
N=int(input())
print(N*(N+1)//2)
B問題
Nが小さいので問題文の通りに愚直に判定して間に合います。
提出コードです。
c.py
N=int(input())
A=list(map(int,input().split()))
sumA=[0]
for i in range(N):
sumA.append(sumA[-1]+A[i])
ans=0
for i in range(N):
for j in range(i,N):
sumS=sumA[j+1]-sumA[i]
for k in range(i,j+1):
if sumS%A[k]==0:
break
else:
ans+=1
print(ans)
このコードでは累積和をとっていますがこの制約であればその必要もありません。
C問題
前から判定していけばよいです。
それぞれのドミノについて、そのドミノが倒れたときにどこまで倒れるかを前計算して前からmaxをとっておき、前から倒していくようにしてどこまで倒れていくか計算しました。
提出コードです。
c.py
N=int(input())
A=list(map(int,input().split()))
for i in range(N):
A[i]+=i
maxA=[A[0]]
for i in range(1,N):
maxA.append(max(maxA[-1],A[i]))
ans=A[0]
while ans<N:
if maxA[ans-1]>ans:
ans=maxA[ans-1]
else:
break
print(min(ans,N))
公式解説のように要素を1つずつ見ていきmaxを取るのと答えを更新するのを同時にやったほうがシンプルでした。
D問題
黒色になった頂点から有向辺をさかのぼってその頂点に到達できるかを保存しておく長さNの配列を考えます。
クエリが2の時はその配列を読めばよいです。
クエリが1の時は、黒色に更新された頂点から辺を逆向きにさかのぼっていくようにBFSを行い、新たに到達可能になった頂点を探して配列を更新します。
提出コードです。
d.py
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for i in range(M):
X, Y = map(int, input().split())
X -= 1
Y -= 1
E[Y].append(X)
A = [False for _ in range(N)]
from collections import deque
Q = int(input())
for _ in range(Q):
t, v = map(int, input().split())
v -= 1
if t == 2:
print("Yes" if A[v] else "No")
if t == 1:
q = deque()
q.append(v)
while q:
item = q.popleft()
if A[item]:
continue
A[item] = True
for next in E[item]:
if not A[next]:
q.append(next)
E問題
全て1で初期化したセグ木に、区間更新（LからRを0で更新）と区間取得（全要素の和）を行えば問題は解けます。
ただし、$N\leq10^9$であるため、そのままセグ木を用意するとメモリと速度の面で間に合いません。
$Q\leq2\cdot10^5$であることから、必要な位置は$10^9$よりもはるかに小さいです。そこで座標圧縮を考えます。
$L,R$として出現する数字は飛び飛びの値ですが、その間に存在する数字たちはまとめて1つの座標と考えて問題ありません。
そこで、個数を記録したうえで座標圧縮します。
その個数を反映した初期配列をもとにセグ木を作ってクエリを実行すれば、ACを取れます。
提出コードです。
e.py
N, Q = map(int, input().split())
def segfunc(x, y):
return x + y
class LazySegTree_RUQ:
def __init__(self, init_val, segfunc, ide_ele):
n = len(init_val)
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1 << (n - 1).bit_length()
self.tree = [ide_ele] * 2 * self.num
self.lazy = [None] * 2 * self.num
for i in range(n):
self.tree[self.num + i] = init_val[i]
for i in range(self.num - 1, 0, -1):
self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
def gindex(self, l, r):
l += self.num
r += self.num
lm = l >> (l & -l).bit_length()
rm = r >> (r & -r).bit_length()
while r > l:
if l <= lm:
yield l
if r <= rm:
yield r
r >>= 1
l >>= 1
while l:
yield l
l >>= 1
def propagates(self, *ids):
for i in reversed(ids):
v = self.lazy[i]
if v is None:
continue
self.lazy[i] = None
self.lazy[2 * i] = v
self.lazy[2 * i + 1] = v
self.tree[2 * i] = v
self.tree[2 * i + 1] = v
def update(self, l, r, x):
ids = self.gindex(l, r)
self.propagates(*self.gindex(l, r))
l += self.num
r += self.num
while l < r:
if l & 1:
self.lazy[l] = x
self.tree[l] = x
l += 1
if r & 1:
self.lazy[r - 1] = x
self.tree[r - 1] = x
r >>= 1
l >>= 1
for i in ids:
self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
def query(self, l, r):
ids = self.gindex(l, r)
self.propagates(*self.gindex(l, r))
res = self.ide_ele
l += self.num
r += self.num
while l < r:
if l & 1:
res = self.segfunc(res, self.tree[l])
l += 1
if r & 1:
res = self.segfunc(res, self.tree[r - 1])
l >>= 1
r >>= 1
return res
Query = [list(map(int, input().split())) for _ in range(Q)]
qSet = set()
for i in range(Q):
Query[i][0] -= 1
Query[i][1] -= 1
qSet.add(Query[i][0])
qSet.add(Query[i][1])
qSet.add(0)
qSet.add(N - 1)
qSets = list(sorted(qSet))
for i in range(len(qSets) - 1):
if qSets[i + 1] - qSets[i] > 1:
qSet.add(qSets[i] + 1)
qSets = list(sorted(qSet))
Idict = {}
for i in range(len(qSets)):
Idict[qSets[i]] = i
tmp = []
for i in range(len(qSets) - 1):
tmp.append(qSets[i + 1] - qSets[i])
tmp.append(1)
seg = LazySegTree_RUQ(tmp, segfunc, 0)
for i in range(Q):
L, R = Query[i]
L = Idict[L]
R = Idict[R]
# print(L,R)
seg.update(L, R + 1, 0)
print(seg.query(0, len(tmp)))
F問題
猫があるタワーに立っているとき、高橋君は以下のどちらかの行動をとります。
- 猫がいるタワーを撤去し、右か左のうち高いタワーがある方に移動させる
- 次のステップで猫に特定の方向に行かせるため、猫に行ってほしくない方向のタワーを撤去し、次のステップで確実に右/左に猫を移動させられるようにする
タワーを撤去すると、連続するタワーの区画は右側と左側で分かれ、猫は右か左のどちらかに移動します。つまり、猫の動ける範囲がどんどん狭くなっていきます。
右に猫を行かせたいのにより右側の高いタワーを壊す必要性がないことは容易に分かるので、区画内で一番高いタワーから右に行かせるか左に行かせるかの探索を、区画の幅が1になるまで行っていけばよいことが分かります。
提出コードです。
もっといいやり方があるかもしれませんが、区間内の最大値を求めるのにはセグ木を使っています。
f.py
N=int(input())
P=list(map(int,input().split()))
def segfunc(x,y):
return max(x,y)
class LazySegTree_RUQ:
def __init__(self,init_val,segfunc,ide_ele):
n = len(init_val)
self.segfunc = segfunc
self.ide_ele = ide_ele
self.num = 1<<(n-1).bit_length()
self.tree = [ide_ele]*2*self.num
self.lazy = [None]*2*self.num
for i in range(n):
self.tree[self.num+i] = init_val[i]
for i in range(self.num-1,0,-1):
self.tree[i] = self.segfunc(self.tree[2*i],self.tree[2*i+1])
def gindex(self,l,r):
l += self.num
r += self.num
lm = l>>(l&-l).bit_length()
rm = r>>(r&-r).bit_length()
while r>l:
if l<=lm:
yield l
if r<=rm:
yield r
r >>= 1
l >>= 1
while l:
yield l
l >>= 1
def propagates(self,*ids):
for i in reversed(ids):
v = self.lazy[i]
if v is None:
continue
self.lazy[i] = None
self.lazy[2*i] = v
self.lazy[2*i+1] = v
self.tree[2*i] = v
self.tree[2*i+1] = v
def update(self,l,r,x):
ids = self.gindex(l,r)
self.propagates(*self.gindex(l,r))
l += self.num
r += self.num
while l<r:
if l&1:
self.lazy[l] = x
self.tree[l] = x
l += 1
if r&1:
self.lazy[r-1] = x
self.tree[r-1] = x
r >>= 1
l >>= 1
for i in ids:
self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])
def query(self,l,r):
ids = self.gindex(l,r)
self.propagates(*self.gindex(l,r))
res = self.ide_ele
l += self.num
r += self.num
while l<r:
if l&1:
res = self.segfunc(res,self.tree[l])
l += 1
if r&1:
res = self.segfunc(res,self.tree[r-1])
l >>= 1
r >>= 1
return res
segP=[(P[i],i) for i in range(N)]
maxSeg=LazySegTree_RUQ(segP,segfunc,(0,0))
from collections import deque
q=deque() # L,R,cost,start
start=-1
for i in range(N):
if P[i]==N:
start=i
if start>0:
q.append((0,start,0,start))
if start+1<N:
q.append((start+1,N,0,start))
ans=0
while q:
l,r,c,s=q.popleft()
# print(l,r)/
maxI=maxSeg.query(l,r)[1]
# if s==r:
if maxI>l:
q.append((l,maxI,c+abs(s-maxI),maxI))
if maxI+1<r:
q.append((maxI+1,r,c+abs(s-maxI),maxI))
if maxI==l and maxI+1==r:
ans=max(ans,c+abs(s-maxI))
print(ans)
どうやらJOI本選で似たような問題が出題されていたようです。
振り返り
ノーペナ60分で6完できたので良かったと思います。
A～Dあたりをもう少し早く解けるとよかったなとは思いました。
