AtCoder Beginner Contest 097/AtCoder Regular Contest 097

はい。
https://atcoder.jp/contests/abc097
https://atcoder.jp/contests/arc097

A - Colorful Transceivers

Python3

a,b,c,d=map(int,input().split())
print("Yes" if abs(a-c)<=d or (abs(a-b)<=d and abs(b-c)<=d) else "No")

a,cで直接か、a,bしてb,cか両方を確認する。

B - Exponential

Python3

x=int(input())
ans=chk=1
for i in range(x):
    for j in range(2,11):
        chk=i**j
        if chk<=x: ans=max(ans,chk)
    
print(ans)

よくわかってなくて最初は2乗しか見てなくて落ちた。多分、23で8になったりするのに2乗しか見てないと余裕で落ちるはず。何乗までみればいいか、TLEしないかとかは特に根拠もなく2〜10乗までチェックにして一応AC、これはこれでありでしょう。

C - K-th Substring

Python3

s=input()
k=int(input())
n=len(s)
d=set()
for i in range(n):
    #for j in range(i,n):
    for j in range(i,min(n,i+5)):
        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])

当初のアプローチでは部分点だけ取ってTLE。文字列色々取り出すのに実は5文字より長い文字列取り出す必要はないので多重ループの内側は for j in range(i,min(n,i+5)) にする。これでTLE解消します。うーん、、、悔しいですね。

D - Equals

PyPy3

class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par =[int(i) for i in range(size)]
        self.grp =size
 
    def find(self, x):
        if x==self.par[x]: return x
 
        self.par[x]=self.find(self.par[x])
        return self.par[x]
 
    def same(self, x, y): 
        return self.find(x)==self.find(y)
 
    def unite(self, x, y): 
        x,y=self.find(x),self.find(y)
        if x==y:
            return
 
        self.grp-=1
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
 
    def group_num(self):
        return self.grp
 
 
n,m=map(int, input().split())
p=[int(i) for i in input().split()]
uf=UnionFind(n+1)
 
for i in range(m):
    x,y=map(int, input().split())
    uf.unite(x,y)
 
ans=chk=0
for a,i in enumerate(p):
    if uf.same(p[a],a+1): ans+=1
print(ans)

m個のx,yのペアをそれぞれの数(頂点)に対する辺ということにして同じグループ内なら移動出来るのかな、、証明も反例もないけど出来るかな。少なくとも違うグループには絶対に移動できないな。UnionFindで辺を見ていって同じグループならi番目の位置に移動可能ということでサンプル合うし試しに提出するか、でAC出ました。公式解説でもUnionFind使って同じ連結成分内かどうかで判定するように書いてあるっぽいのでここでは証明は書きませんけどUnionFind使えばいいっぽいです。