私は早解きができますが早解きができます。
どうも、お久しぶりです。あじゃじゃです。
じゃあ、ABC393の振り返りをしていきましょう。
A.Poisonous Oyster
やるだけ。コードが長いです。
s1,s2=input().split()
if s1==s2=="fine":
print(4)
elif s1==s2=="sick":
print(1)
elif s1=="sick":
print(2)
else:
print(3)B.A..B..C
全探索。文字の間隔a,と先頭のindexを置いてごちゃごちゃ。三重ループでいいじゃんと言われて膝を打った。
s=input()
n=len(s)
ans=0
for a in range(1,n//2+1):
for i in range(n-2*a):
if s[i]=="A" and s[i+a]=="B" and s[i+2*a]=="C":
ans+=1
print(ans)C.Make it Simple
言われたことをやるだけなんだが、250点でよくないか????
どうしてしまったんだAtCoder!!!!!初心者の文句に日和ったんですか!?(いいえ)
from collections import defaultdict
dd=defaultdict(int)
n,m=map(int,input().split())
ans=0
for _ in range(m):
u,v=map(int,input().split())
if u>v:
v,u=u,v
elif u==v:
ans+=1
continue
if dd[(u,v)]:
ans+=1
else:
dd[(u,v)]=1
print(ans)何をやったって通る―――
D.Swap to Gather
†真ん中に寄せる†。典型90にもありそうなど典型です。
なぜ真ん中に寄せるべきなのかというとそれはよせる場所を固定して0の寄与を考えるとわかります。
証明はしてないですが、コンテスト中はそんな感じで思い出しました。
n=int(input())
s=input()
one=(s.count("1")+1)//2
if one==0:
print(0)
exit()
zero=[0]*n
for i in range(n):
if s[i]=="0":
zero[i]=1
from itertools import accumulate
zero=list(accumulate(zero))
onecnt=0
for i in range(n):
if s[i]=="1":
onecnt+=1
if one==onecnt:
idx=i
ans=0
for i in range(n):
if s[i]=="1":
ans+=abs(zero[i]-zero[idx])
print(ans)これは一瞬難しいなと思ってしまいました。
この辺が似ているかもしれない。実は。
E.GCD of Subset (first challenge)
この辺から普通にしんどくなってくる。(当社比)
さらに制約を読んでいくとN<=1200000となっており明らかにオーダーがびみょい解法を落としにかかっているので、つまりPythonなら普通の解法でも下手な実装をすれば落とす可能性があり…、よし。Fをいったん見よう。
この間三分である。Pythonがうまくなってきた気がするね。（それ必要あるのか？）
F.Prefix LIS Query
Fを早く見ようと思った理由はEが怪しいからというのともう一つ、Fが簡単そうな問題名だったというのがある。
Prefix←文字列系ならhash,そうでなくてもhashでできそう
LIS←セグ木、にぶたん
何でも解けそうである。ということで早めに読んでおきたかったのだ。
問題を読んで意訳すると、「クエリ先読みしてLISを前から求めて」と書いていたのでその通りに実装して、投げてみたらなぜかACと書いていた。
意味不明である。何を問いたかったんだろう？？？？
それはそうとして解法を書くと、
クエリを先に全部読んでおいて、RでソートしLISを求める。
これ以上でも以下でもない。あとはこれを書くだけ。セグ木でもにぶたんでも何でもいいと思う。
n,q=map(int,input().split())
a=list(map(int,input().split()))
Q=[]
for i in range(q):
nxt=list(map(int,input().split()))
nxt.append(i)
Q.append(tupl(nxt))
Q.sort()#クエリ先読みしてRでソート
from bisect import*
now=-1
seq=[]
ans=[0]*q
#LIS求めながらクエリに答える。
for r,x,num in Q:
r-=1
while now<r:
now+=1
pos=bisect_left(seq,a[now])
if len(seq)<=pos:
seq.append(a[now])
else:
seq[pos]=a[now]
query=bisect_right(seq,x)
ans[num]=query
print(*ans,sep="\n")Eがこれでいいんじゃないかなと思った。
E.GCD of Subset (Second challenge)
問題文は
長さ N の数列A=(A1,A2,…,AN) と N以下の正整数 K が与えられます。
i=1,2,…,N について次の問題を解いてください。
・Aiを含むように K 個の要素を Aから選ぶ時それらの最大公約数 (GCD) としてあり得る最大値を求めてください。
実は適切に枝刈っておけば通るんじゃないの～？？？と思って投げたらたくさんのTLE。実装ミスがあったので直して投げたらTLE。
いやな予感はあったのに学習してなかったのでペナを10分もいただいてしまった。情けない。
よし、落ち着いて考え直そう。
大筋としてやりたいのは、
配列Aのなかにdの倍数は何個あるかのリストLを持ってAiの約数aを逆順にみていって初めてL[a]>=Kを満たしたaを出力する。
これだ。
まずは入力を高速化して、受け取る。
愚直にやってしまうと、Ai=Ajみたいなケースがあった時に何度も約数を求めることになりとても無駄なのでAをcnt[a]={Aの中にaがいくつあるか}という配列に変換する。あとは素数列挙の時に行う要領でdの倍数がAの中に何個あるかを調和級数のオーダーで求められそうだ。…あ、約数列挙がO(N√M)じゃなくてO(MlogM)になってるな。これは勝ったんじゃないか？
あとはもう適当にやってしまえばACがもらえる。オーダーはO(N+MlogM)くらいなんだろうか。
ACコードはこんな感じ。
import sys
input_data = sys.stdin.read().split()
it=0
n=int(input_data[it]); it+=1
k=int(input_data[it]); it+=1
a=list(map(int, input_data[it:it+n]))
mx=max(a)
cnt=[0]*(mx+1)
for x in a:
cnt[x]+=1
mt=[0]*(mx+1)
for d in range(1,mx+1):
for j in range(d,mx+1,d):
mt[d]+=cnt[j]
ans=[1]*(mx+1)
for d in range(mx,1,-1):
if mt[d]>=k:
for j in range(d,mx+1,d):
if ans[j]<d:
ans[j]=d
for x in a:print(ans[x])いやこれ絶対Fのほうが簡単だろ、どうなっていやがるこの世の中は.
というかこれで六完ってほんとですか？俺は最強なんじゃないか？
あとがき
いいえ。最強ではありません。順位もめちゃくちゃいい！！！！というわけではないので。
結論から言ってしまえば人類は賢すぎるのでE問題は水diffで、一方で人類はおろかでもあるのでF問題も水diffです。
水diff二問を高速で通したということは・・？そうですね。青perfがでるわけです。
ということでperfは1710でレートは1223→1282(+59)で瓦まであと少しってとこまで来ました。今月中には水下位で足踏みしている友達をぶち抜いてさらなる高みを目指していきたいですね。
それではまた来週～！！！！
コメント