青い、青い空。
空よりもD問題のほうが青くて神だな。ということでお久しぶりです。あじゃじゃです。
今日はABC390がありました。Dが解けなくてブチ切れてる人、解けたけどブチ切れてる人がおり大変楽しくTLを眺めておりました。
それでは解けた問題の解説をしていきます。
A.12435
A150点には嫌な思い出があるので引っ込んでいてほしいなと思っていたら思ったより簡単で助かった。
言われた通りのことを調べればよい。
m=[1,2,3,4,5]
lis=list(map(int,input().split()))
cnt=0
for i in range(4):
lis[i],lis[i+1]=lis[i+1],lis[i]#入れ替える
if lis==m:
print("Yes" )
exit()
lis[i],lis[i+1]=lis[i+1],lis[i]#元に戻す
print("No")どう書いたってかまわない。お好みってやつだ。
B.Geometric Sequence
コンテスト中は浮動小数の誤差を気にしなくても通すことができたみたいだが、これを気にしないと通らないことが大半なので分数が現れないように判定がしたい。
そんな時に中学だか高校の数学で習った等比中項を思い出すと、a,b,cがこの順で等比数列を為すとき
n=int(input())
a=list(map(int,input().split()))
for i in range(n-2):
if a[i]*a[i+2]!=a[i+1]*a[i+1]:
exit(print("No"))
print("Yes")こんな具合だろうか。pythonは記述量が少なくてとっても好き。遅いからクソではあるけど。
C.Paint to make a rectangle
人類は賢い。これ灰色なんだなぁ、まぁやるだけっちゃそうなんだけど。
条件を満たす長方形領域のうち最小のものは黒マスの中で一番左にあるマス、右にあるマス、上にあるマス、下にあるマスをちょうど囲うような長方形なので、iの最大最小、jの最大最小を持ちその内側に白マスがないかをfor 文化なんかで確認してやればいい。
口で説明するのが苦手なのでとりあえず提出コードを貼る。
h,w=map(int,input().split())
s=[input() for _ in range(h)]
cnt=0
minx,miny,maxx,maxy=1001,1001,-1,-1
flg=1
for i in range(h):
for j in range(w):
if s[i][j]!="#":
continue
miny=min(i,miny)
minx=min(j,minx)
maxx=max(maxx,j)
maxy=max(maxy,i)
for i in range(miny,maxy+1):
for j in range(minx,maxx+1):
if s[i][j]==".":
flg=0
if flg:
print("Yes")
else:
print("No")難しそうな問題だけど、当たり前のことを当たり前に書くだけだ。
Cはこういうのでいいんだよな。
D.Stone XOR
Dなのに青diffとなってしまった問題だ。私も解けなかった。
ただ、要求していることは再帰関数を使った全探索であるので普段ライブラリに頼って階乗全探索や組み合わせ全探索をしてきたツケが回ってきたという感じだ。
more_itertoolsのset_permutationなどで通すことができるという話もあり、なぜmoreitertoolsが使えるんじゃないかということすら思いつかなかったのかと大きな心残りが残った。
ただ全員が同じ条件で戦ってる中、青diffの問題をここで出題するなというのはなんかおかしいんじゃないかと思っている。いやそりゃ出ないに越したことはないが。
E.Vitamin Balance
何をしても通るというやつだ。
とりあえず栄養素ごとにdp[栄養素][カロリー]=摂取量の最大というテーブルを持ってナップザックdpのようなことをして、そのうち一つの栄養素をセグ木にのせて、他二つの栄養素については全部探索するとO(X^2logX)時間で解くことができる、気がする。(私は通った。)
ただし、pythonは答えが更新されうるかで枝刈をしないと通らないので注意(2敗)
class SegmentTree:
def __init__(self, a, segfunc, monoid):
self.n = 1 << (len(a) - 1).bit_length()
self.tree = [monoid] * (self.n << 1) # 高速なリスト初期化
self.segfunc = segfunc
self.m = monoid
for i in range(len(a)):
self.tree[self.n + i] = a[i]
for j in range(self.n - 1, 0, -1):
self.tree[j] = self.segfunc(self.tree[j << 1], self.tree[j << 1 | 1])
def update(self, index: int, new_val):
index += self.n
self.tree[index] = new_val
while index > 1:
index >>= 1
self.tree[index] = self.segfunc(self.tree[index << 1], self.tree[index << 1 | 1])
def query(self, l: int, r: int):
l += self.n
r += self.n
ans = self.m
while l < r:
if l & 1:
ans = self.segfunc(ans, self.tree[l])
l += 1
if r & 1:
r -= 1
ans = self.segfunc(ans, self.tree[r])
l >>= 1
r >>= 1
return ans
def get(self, i: int):
return self.tree[self.n + i]
def query_index(self, l: int, r: int, x):
while r > l:
mid = (l + r) // 2
if self.query(l, mid + 1) == x:
r = mid
else:
l = mid + 1
return r
def dbg(self):
print(self.tree)
#区間最大
def op(a,b):
return max(a,b)
n,x=map(int,input().split())
vac=[list(map(int,input().split())) for _ in range(n)]
dp=[[-1 for _ in range(x+1)] for _ in range(3)]
for i in range(3):
dp[i][0]=0
#ナップザックdp
for v,a,c in vac:
v-=1
for j in range(x-c,-1,-1):
if dp[v][j]>=0 and dp[v][j+c]<dp[v][j]+a:
dp[v][j+c]=dp[v][j]+a
for i in range(x+1):
if dp[2][i]==-1:
dp[2][i]=0
#全探索
st=SegmentTree(dp[2],op,-1)
ans=0
for i in range(x+1):
if dp[0][i]>ans:
for j in range(x+1-i):
if dp[1][j]>ans:
tmp=min(dp[0][i],dp[1][j],st.query(0,x+1-i-j))
if ans<tmp:
ans=tmp
print(ans)1099msで通せた。想定解ではないと思う。
コンテスト結果
2ペナ39分A,B,C,Eの４完でパフォーマンスは1490でレートは1153から1191にあがり入水に王手をかけることができた。
次回のコンテストも配点に関わらず解ける問題を着実に解くことを意識して頑張りたい。
おわりに
今日はみんながD問題について怒っていて愉快なTLだった。
難易度予想というのは難しいものだしそもそも「競技」を名乗るならイレギュラーな回での立ち回りなどを練習するのも大切なんじゃないだろうか。コンテストというのは普段競プロerとして精進して覚えた典型知識、身に着けた考察力、コンテストで勝つための立ち回りを披露し高い順位を目指して戦う場であってお勉強をする場ではない。お勉強ならレートのつかない場所でやったらいいんじゃないかと僕は思う。
今日のところはこれで。今週はテスト勉強を頑張ります。それではまた来週。
コメント