僕の推し炭化水素はアセチレンです
理由はないです。
こんにちは、あじゃじゃです。それではABC394振り返り、やっていきましょう！
A.22222
文字列内の"2"の数を数えましょう。
print("2"*input().count("2"))B.cat
文字列の長さをキーとしてソートしてそのままつなげます。
n=int(input())
s=[input()for _ in range(n)]
s.sort(key=lambda x:len(x))
print("".join(s))C.Debug
難しいと思いました。(灰diffだけど)
問題文をちゃんと読むと要はWWWWWAのような文字列をACCCCCのような文字列に変換してねということらしい。
そういうことなら一度与えられた文字列をランレングス圧縮したら解けると思ったのでそうしました。
from itertools import groupby
def RLE(s):
group=groupby(s)
res=[]
for k,v in group:
res.append([k,len(list(v))])
return res
s=input()
S=RLE(s)
ans=[]
n=len(S)
used=set()
for i in range(n):
if i<n-1 and S[i][0]=="W" and S[i+1][0]=="A":
ans.append("A")
ans.append("C"*(S[i][1]))
S[i+1][1]-=1
else:
ans.append(S[i][0]*S[i][1])
print("".join(ans))余りにも遠回りで情けないな～という気持ちになりました。
D.Colorful Bracket Sequence
簡単じゃないか？スタックやるだけ。
s=input()
lis=[")",">","]"]
stack=[]
for si in s:
if si in lis:
if len(stack)and stack[-1]+si in ["()","<>","[]"]:
stack.pop()
else:
exit(print("No"))
else:
stack.append(si)
if len(stack):
print("No")
else:
print("Yes")茶diff、作るの難しいんだろうな…
E.Palindromic Shortest Path
時々現れる回文問題でかなり難しいと思います。これが水色中位とは恐れ入りました。みんな賢い。
どうにかして回文から回文に遷移させたいので回文の性質を考えると、abaという回文の両端にcを足したcabacも回文になるというものがあります。つまり(i,j)間に回文になる経路があるならiに向かって伸びる経路とjから伸びる経路のうち同じ文字であるペアをとることで新しい回分を為す経路が作れるということが分かります。
ここまでわかれば後は簡単で、有効辺を逆向きに取ったグラフを持って置き、拡張グラフ上でBFSをしてやるといいです。
from collections import deque,defaultdict
n=int(input())
C=[input()for _ in range(n)]
inf=1<<60
g=defaultdict(lambda:[[]for _ in range(n)])
G=defaultdict(lambda:[[]for _ in range(n)])
for i in range(n):
for j in range(n):
if C[i][j]=="-":
continue
g[C[i][j]][i].append(j)
G[C[i][j]][j].append(i)
dist=[[inf]*n for _ in range(n)]
q=deque()
for i in range(n):
for j in range(n):
if i==j or C[i][j]!="-":dist[i][j]=int(i!=j);q.append((i,j))
while q:
x,y=q.popleft()
d=dist[x][y]
for c in g:
for i in G[c][x]:
for j in g[c][y]:
if dist[i][j]>d+2:
dist[i][j]=d+2
q.append((i,j))
for i in range(n):
for j in range(n):
if dist[i][j]==inf:dist[i][j]=-1
for d in dist:
print(*d)こうみるとbfsのなかがワーシャルフロイドっぽいね。
F.Alkane
本番は全方位木dpを書いて通しました。
これに至るまでの流れを書きます。
まず私は次数が4以上の頂点同士をつないでる辺のみをつないだ森を考えその連結成分それぞれについて木dpをしたらよいと考えて以下のコードを書きました。
n=int(input())
g=[[]for _ in range(n)]
for _ in range(n-1):
a,b=map(lambda x:int(x)-1,input().split())
g[a].append(b)
g[b].append(a)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
start=-1
for i in range(n):
if len(g[i])>=4:
start=i;break
if start==-1:
exit(print(start))
import sys
sys.setrecursionlimit(10**6)
visited=set()
def dfs(now,prev=-1):
cnt=[]
visited.add(now)
for v in g[now]:
if len(g[v])<4:continue
if v==prev:continue
cnt.append(dfs(v,now))
res=1
cnt.sort(reverse=True)
for i in range(min(len(cnt),3+int(prev==-1))):
res+=cnt[i]
return res
m=1
for start in range(n):
if len(g[start])>=4 and start not in visited:
m=max(m,dfs(start))
print(3*m+2)しかし残念ながらこれは49AC10WAが出ます。
なぜなら各連結成分について親として選んだ頂点をかならず採用してしまうからです。もしその頂点を採用しないような点集合が最適である場合、これでは間違った回答を出力してしまいます。
ただ、このコードは親が最適な点集合の要素なのであれば正しい答えを出していると考えられます。なぜなら49ケース通ってるからです。(適当)
じゃあすべての候補を親にして考えれば正しくなるはずです。木について親を取り直して差分計算をするアルゴリズム(？)と言えばなんでしょうか。そうです。全方位木dpです。というわけで熱烈実装タイムです。
熱烈実装の結果が以下です。
n=int(input())
g=[[]for _ in range(n)]
for _ in range(n-1):
a,b=map(lambda x:int(x)-1,input().split())
g[a].append(b)
g[b].append(a)
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
#アルカングラフがあるか
start=-1
for i in range(n):
if len(g[i])>=4:
start=i;break
if start==-1:
exit(print(start))
import sys
sys.setrecursionlimit(10**6)
cache=[0]*n
#親から葉に向かうやつ
def dfs_down(now,prev=-1):
cnt=[]
for v in g[now]:
if len(g[v])<4:continue
if v==prev:continue
cnt.append(dfs_down(v,now))
res=1
cnt.sort(reverse=True)
for i in range(min(len(cnt),3+int(prev==-1))):
res+=cnt[i]
cache[now]=res
return res
#根の取り直し
def dfs_up(now,prev=-1,val=-1):
lim=3+int(prev==-1)
lis=[]
if val>0:lis.append(val)
for v in g[now]:
if v==prev:continue
if len(g[v])<4:continue
lis.append(cache[v])
lis.sort(reverse=True)
best=1+sum(lis[:min(lim,len(lis))])
for v in g[now]:
if v==prev:continue
if len(g[v])<4:continue
tmp=[]
if val>0:tmp.append(val)
for u in g[now]:
if u==v or u==prev:continue
if len(g[u])<4:continue
tmp.append(cache[u])
tmp.sort(reverse=True)
res=1+sum(tmp[:min(3,len(tmp))])
best=max(best,dfs_up(v,now,res))
return best
#各連結成分について一度ずつやる
visited=set()
M=0
for i in range(n):
if len(g[i])<4 or i in visited:continue
cp=[]
stack=[i]
while stack:
cur=stack.pop()
if cur in visited:continue
visited.add(cur)
cp.append(cur)
for u in g[cur]:
if u in visited or len(g[u])<4:
continue
stack.append(u)
r=cp[0]
dfs_down(r)
best=dfs_up(r)
M=max(best,M)
print(3*M+2)説明が面倒なので、Kiriさんの全方位木dpの記事を読みましょう。
総括
緑コーダー、茶コーダー冷遇コンテストで厳しいものがあった気がします。
私は96:11(6)で126:11の6完1634perfで、1282→1323(+49)と2週連続の爆勝ちで瓦を増やすことができました。
いや～にまにましちゃいますね。
マジで関係ないですけどなんか最近順位表に中国人が多い気がします。大AtCoder時代の幕開けなんでしょうか？私も大和魂を持ってコンテストで戦っていきたいです。
それではまた次の記事で。ばいば～～い！！！！
コメント