ABC339をpythonで解く
問題文は問題 - 日本レジストリサービス(JPRS)プログラミングコンテスト2024(AtCoder Beginner Contest 339)を参照のこと。総評としてはDが難しかったですね。ABC、いっつもDが罠だな。
A
後ろから文字を見ていって、「.」が出てきてからそれより後ろの文字列を出力してexit()
S=input()
N=len(S)
for i in range (N-1,-1,-1):
if S[i]==".":
print(S[i+1:])
exit()
B
現在の高橋君の位置と向き、グリッドの状態を管理して愚直にシミュレーションします。1回の行動による上記の情報の変化はO(1)で計算できるので、余裕でNターン後のグリッドの情報を求められます。
H,W,N=map(int,input().split())
masu=[[0]*W for _ in range (H)]
x=0
y=0
dxdy=[(0,-1),(1,0),(0,1),(-1,0)]
muki=0
for _ in range (N):
if masu[y][x]==0:
masu[y][x]=1
muki+=1
muki%=4
x+=dxdy[muki][0]
y+=dxdy[muki][1]
x%=W
y%=H
else:
masu[y][x]=0
muki-=1
muki%=4
x+=dxdy[muki][0]
y+=dxdy[muki][1]
x%=W
y%=H
for i in masu:
for j in i:
if j==0:
print(".",end="")
else:
print("#",end="")
print()
C
仮に初期状態の乗客を0人として、各停車後の乗客の人数が何人となっているかを確かめてみます。ここで最小の値が負の数となっている場合、初期状態をその値の絶対値の人数だけ足さなければ矛盾が生じ、逆に足していれば矛盾は生じません。つまり、初期状態の乗客の人数として考えられる最小値はこれになります。この値に、「仮に初期状態を0人とした場合の最終停車後の乗客の人数」を足した値が現在のバスの乗客の人数として考えられる最小値になります。
N=int(input())
A=list(map(int,input().split()))
now=0
ninnzuu=[0]
for i in A:
now+=i
ninnzuu.append(now)
hajime=-min(ninnzuu)
ans=hajime+ninnzuu[-1]
print(ans)
D
解説見てみたらN**4解でめっちゃグラフに辺張る感じで解いていました。なるほどね。
E
通常セグ木が必要そう。セグ木を使えれば大したことない問題で、Dより簡単。
N,D=map(int,input().split())
A=list(map(int,input().split()))
def segfunc(x,y):
return max(x,y)
ide_ele = 0
class SegTree:
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
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 add(self,k,x):
k += self.num
self.tree[k] += x
while k>1:
self.tree[k>>1] = self.segfunc(self.tree[k],self.tree[k^1])
k >>= 1
def update(self,k,x):
k += self.num
self.tree[k] = x
while k>1:
self.tree[k>>1] = self.segfunc(self.tree[k],self.tree[k^1])
k >>= 1
def kosuu(self,k):
k += self.num
return self.tree[k]
def query(self,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
deka=max(A)+1
seg = SegTree([0]*deka, segfunc, ide_ele)
for i in A:
sita=max(i-D,1)
ue=min(deka,i+D+1)
now=seg.query(sita,ue)
seg.update(i,now+1)
print(seg.query(1,deka))
F
解説見たら乱打らしい。乱打実装したことなし。
この記事が気に入ったらサポートをしてみませんか?