ABC097(バーチャル):水色競プロerの復習
昨日はお休みして、今日はABC097でバーチャルコンテスト。
朝にバチャやってる方々もおられるようですが、出勤時間的に出られないんです。出られる方羨ましい・・
なので夜に一人でやってます。
〇コンテスト名：ABC097
〇配点：不明
〇制限時間100分(A～Dまでの4問の時代のコンテスト)
〇今回の方針
本番のコンテストのつもりで解く
とにかく速く解く
コンテスト開始！
位置a,b,cに人がいる。人同士は距離d以内であれば通信できる。aとcは通信できるか？
勝手に位置関係をa,b,cの順にしてしまいたくなりますね。
テストケースが親切なので気づきますけど。
aとcがd以内、もしくはaとb,bとcがd以内ならOKですね。
a,b,c,d=map(int,input().split()) if abs(a-b)<=d and abs(c-b)<=d: print("Yes") elif abs(a-c)<=d: print("Yes") else: print("No")
2:21 AC
Xが与えられ、X以下の最大のべき乗数を求めよ。
はい簡単
ループを回してiを増やしていきながら、i**2＝Xならi**2を出力i**2>Xなら(i-1)**2を出力すれば、
WA
ちゃんと問題文を読みましょう。
2乗とは限らないんですね。
ただ、Xが1000以下。そして2**10=1024を知っていれば、10乗以上を考える必要がないことがわかります。
Xが1のときは考えるのが面倒なので、例外処理で1を出力してしまいます。
あとは変数ansを用意しておいて、iとjの2重ループを回す。j**iがX以下でansより大きければans=j**i。
X=int(input()) if X==1: print(1) exit() ans=1 for i in range(2,11): for j in range(1001): if j**i<=X: if ans<j**i: ans=j**i print(ans)
8:21 AC 1WA
なにやってんの？
あと、計算量的に余裕なのでやりませんでしたが、10**6オーダーの計算量ならj**iがXを超えた時点でbreakして枝刈りすべきでしょうね。
sの部分文字列に関する問題で辞書順でK番目になる連続する部分文字列(同じ文字列は1つとして数える)を求めよ。
一か八か全探索。dictを用意して、初めと終わりを2重ループさせて全探索。dict内に同じ文字列が無ければ加える。
最後にdictをlistに変換してソート、listのK番目を出力！
TLE
やっぱ無理です。これで通るならB問題より簡単です。
良く見ればKが1～5ととても小さい。
これならlist Lを用意して、部分文字列の初めと終わりを2重ループさせて全探索。
面倒なのでLには空文字””を入れておく。
・部分文字列がLに含まれていないことを確認。
・Lの長さがK以下ならLに部分文字列を加えてソート
・Lの長さがK+1なら、Lの最後と部分文字列の辞書順を比較。
・部分文字列の方が前にくるなら、部分文字列をLに加えて、ソート。
Lの一番後ろを切る。
・部分文字列の方が後にくるならループをbreakして枝刈り。
最後にLの一番後ろを出力
S=input() K=int(input()) L=[""] for s in range(len(S)): for e in range(s,len(S)): if S[s:e+1] in L: continue if len(L)>K: if S[s:e+1]>L[K]: break if S[s:e+1] not in L: if len(L)<=K: L.append(S[s:e+1]) L.sort() else: L.append(S[s:e+1]) L.sort() L=L[:K+1] print(L[-1])
31：27AC 1TLE 2WA
14行目のソートを忘れててテストケースに1つだけ通らず２WA
結局C問題だけで3ペナ。B問題と合わせて4ペナ。
1からNを並べ替えた数列pがある。1～N以下の整数ペアがM個与えられ、ペアの数字は何回でも入れ替えて良い。
左からの順番と整数が一致する箇所を最大いくつにできるか？
unionfindとdictを組み合わせれば良さそうですね。
左からi番目を見ているときは、i番目と整数iの位置が同じグループか否かを判断。
N,M=map(int,input().split()) p=[0]+list(map(int,input().split())) P=[i for i in range(N+1)] S=[1 for i in range(N+1)] def find(a): if a==P[a]: return a else: return find(P[a]) def union(b,c): B=find(b) C=find(c) if S[B]<S[C]: P[B]=P[C] S[C]+=S[B] else: P[C]=P[B] S[B]+=S[C] for i in range(M): x,y=map(int,input().split()) union(x,y) D={} for i in range(1,N+1): D[p[i]]=i ans=0 for i in range(1,N+1): if find(i)==find(D[i]): ans+=1 print(ans)
43:52 AC
結局 43:52全完(4完)4ペナ!!!!
緊張感が足りてませんね。
