ABC329 A~D,F
A問題 Spread
これはいい感じにやるだけです。
自分のPythonのコード
s=list(input()) print(s[0],end='') for i in range(1,len(s)): print(f" {s[i]}",end='')
B問題 Next
うーんこれもやるだけですね。
ぼくは、数列Aをリストで受け取った後、Set型に変換して、重複をなくし、その後またリストにもどしてからソートし、上から二番目の数字を出力させることにしました。
Pythonの自分のコード
n=int(input()) a=sorted(list(set(list(map(int,input().split()))))) print(a[len(a)-2])
C問題 Count xxx
これは、一種類の文字からなる部分文字列を全て格納するSet型などを作って、全部入れた後重複がない要素数を出力すれば答えが出ます
…しかし、この方法だとSet型に格納するために部分文字列を格納しておく変数が大変なことになります（語彙力消滅）
マジで説明下手くそなんですけど、例えばPythonなどを使う時、まずaが一個続いてたら変数sにaを追加しよう。で、それをSet型にぶち込む
またaが続いてたらsにaを接続してあげてまたそれをSet型にぶちこむ…
みたいな方法が思いつくかも知れませんが、Pythonの文字列型の連結には確かO(N)かかるはずなのでaがたくさんつながっているときなどはTLEになってしまうんです。
…つたわったかどうかよくわからないのですが、とにかく安直な実装だとTLEになるわけです。
ぼくはその部分文字列を構成する文字に個数の数字を文字列型に変換したものを連結してSet型にぶちこむことにしました。これで解決です！（た、たぶん…）
例
"aaa"
→"a3"
"ccccc"
→"c5"
自分のPythonのコード
n=int(input()) s=list(input()) irane=set() hako=s[0] count=1 for i in range(1,len(s)): if not hako+str(count) in irane: irane.add(hako+str(count)) if hako[0]==s[i]: count+=1 else: hako=s[i] count=1 irane.add(hako+str(count)) print(len(irane))
D問題 Election Quick Report
それぞれの人の得票数を格納する配列をつくります。
で、最初に一番得票数が多い人の番号と、個数を変数に格納しておきます。
それで投票された人の番号を最初から見ていって、それぞれの人の得票数を格納する配列を更新していきます。
一回更新するたびに、更新した人の得票数がさっきまで一番得票数が多い人よりも多いかを確認して、もし多くなっていたら一番得票数が多い人を更新します。そして、更新した場合も更新しなかった場合も一番得票数が多い人を格納した変数を毎回出力します。
これでAC
自分のPythonのコード
n,m=map(int,input().split()) a=list(map(int,input().split())) amount=[0]*n saidai=1 for i in range(m): hako=a[i] amount[hako-1]+=1 if amount[hako-1]>amount[saidai-1]: saidai=hako elif amount[hako-1]==amount[saidai-1] and hako<saidai: saidai=hako print(saidai)
E問題
あの、コンテスト中に解けませんでした。
たぶん最初に文字列Tと一致している文字列Sの部分を確認して、そこからBFSみたいにしていけばいいんじゃないすかね。（解いてない）
F問題 Colored Ball
マージテクっていうやつを使うみたいです。
簡単に説明すると、箱aから箱bにボールを移すときに、箱に入っているボールの数が少ない方から多い方に移すということです。こうすることによって計算量が減ります（ボールの移動する数が減るから）。
そして、そのようにした時にもし箱aから箱bにボールを移すはずが、箱bから箱aにうつしてしまった…となったら、次から箱aは箱bのことね！箱bは箱aのことね！みたいにすればおけです。
Pythonの自分のACコード
n,q=map(int,input().split()) a=list(map(int,input().split())) count=0 irane=set() irane2=set() num=[0]*n for i in range(n): if not a[i] in irane: irane.add(a[i]) else: irane2.add(a[i]) count+=1 num[a[i]-1]+=1 amount=[[]*1 for i in range(n)] for i in range(n): if a[i] in irane2: amount[i].append(0) amount[i].append(set([a[i]])) else: amount[i].append(1) amount[i].append(set()) check=0 for i in range(q): a,b=map(int,input().split()) hako=len(amount[a-1][1])+len(amount[b-1][1]) amount[b-1][0]+=amount[a-1][0] amount[a-1][0]=0 if len(amount[a-1][1])==len(amount[b-1][1]): x=amount[a-1][1] y=amount[b-1][1] elif len(amount[a-1][1])<len(amount[b-1][1]): x=amount[a-1][1] y=amount[b-1][1] else: x=amount[b-1][1] y=amount[a-1][1] x=list(x) z=y for ipp in range(len(x)): if x[ipp] in y: num[x[ipp]-1]-=1 if num[x[ipp]-1]==0: amount[b-1][0]+=1 z.remove(x[ipp]) else: z.add(x[ipp]) amount[b-1][1]=z amount[a-1][1]=set() print(len(amount[b-1][1])+amount[b-1][0]) count-=(hako-(len(amount[b-1][1])+amount[b-1][0])) if count==0: iti=i check=1 break if check==0: exit() for i in range(len(amount)): amount[i][0]+=len(amount[i][1]) amount[i][1]=[] for i in range(iti+1,q): a,b=map(int,input().split()) amount[b-1][0]+=amount[a-1][0] amount[a-1][0]=0 print(amount[b-1][0])
