ABC202

#はじめに
こんばんは

京都に住んでいる修士2年の大学院生です．
今はまだ修論が本格化していないので，社会人前に基礎情報技術者の資格をとるため，日々勉強しています．意外と範囲が広くて大変だあ，というお気持ちです．CPUやメモリ，ハードディスクのところは覚えることがホント多いですね．
ということで資格の勉強をするほど暇なので，ABC202に参加しました．

今回はこんな感じで割とRateingが上がってくれました．D問題まで解けたのでこれを継続していければうれしいですね．6月中に緑まで上がれたらいいなあ……

以下ABC202のリンクです．[https://atcoder.jp/contests/abc202]

#全体の感想
A,Bは簡単でした（7分間）．C問題は計算量を気にしながらコードを書いていたら，結構時間がかかってしまいました（38分間）．D問題は前から"a"か"b"どちらなのかを決めていけばよいのでは？と思いついたらすぐ解けました．思いついたときは嬉しかったです（35分間）．E問題は，問題文を理解してツリーの深さが分かれば辺の数も分かるなあ，と考えていたら時間切れになりました．

全体的には，D問題で差がついた感じがします．

#各問題の感想
###A問題
さいころの両面の和は7になり，3つの面について考えるので，21-(a+b+c)以上，という感じです．

a,b,c=map(int,input().split())
print(21-(a+b+c))

###B問題
問題文通り実装しました．文字を入れ替えて足していきました．

ただ他の人の記事をみると，どうやら文字列を結合するときに+=で結合するのは計算速度が遅くなるようです．推奨されているのはリストにappendしてから"".join(t)する方がいいみたいです．

s=input()
t=""
for i in range(len(s)-1,-1,-1) :
    if s[i]=="6" :
        t+="9"
    elif s[i]=="9" :
        t+="6"
    else :
        t+=s[i]
print(t)

###C問題
まず，a列についてどの数字が何個あるのかを調べました．
n個の0を含むリスト***cnt=[0,0,.......,0]***を作りました．
そして，cnt[aの要素の数字-1]+=1とすることで個数を数えました．でも、これcollectionsのCounterで数えた方が早いなあと思った笑
（例）
a=[2,2,1,3,5],cnt=[0,0,0,0,0]
a=2　→　cnt=[0,1,0,0,0]
a=2　→　cnt=[0,2,0,0,0]
a=1　→　cnt=[1,2,0,0,0]
a=3　→　cnt=[1,2,1,0,0]
a=5　→　cnt=[1,2,1,0,1]

次に，b列の要素をfor文でまわしていき，取り出した要素がa列に含まれているか確かめました．cnt[bの要素の数字-1]を確認した際，0の場合はcontinue，そうでない場合はc列についてfrom collection import Counterをつかってb列要素を取り出したインデックス番号が何個あるのか調べてCounter(c)=clistとして， **cnt[bの要素の数字-1]*clist[bの要素のインデックス]**で組み合わせを求めました．

計算量的には，これはO(2n)なんですかね
後from collection import Counterと***count()***各々の計算量がいまいち掴めてないので知っている人がいればぜひ教えてほしいです

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

cnt=[0]*n

for i in range(n) :
    cnt[a[i]-1]+=1


clist=Counter(c)
ans=0
for i in range(n) :
    if cnt[b[i]-1]==0 :
        continue
    else :
        ans+=cnt[b[i]-1]*clist[i+1]

print(ans)

###D問題
これは前から順番にaなのかbなのかを決めていきました．
まず1番目の文字について，aを先頭とする文字列の順番は，1 番目から

antt=\frac{(aの個数+bの個数-1)!}{(aの個数-1)!(bの個数)!}

番目となり，bを先頭とする場合はantt+1 番目から

bntt=antt+\frac{(aの個数+bの個数-1)!}{(aの個数)!(bの個数-1)!}

番目となります．
辞書順でbが後に来るのは自明ですから，aを持ってきた場合は1~antt 番目（前半）となり，bを持ってきた場合はantt+1~bntt 番目（後半）となりますね．kがこのどちらに入っているか調べます．前半なら，kはそのままの値を保持して2番目の文字について調べ，後半ならkからanttを引いて2番目の文字について調べていきます．
といった感じで，前半ならkはそのまま，後半ならanttを引くといった感じで，最終的にkの値がanttまたはbnttと一致するまで計算します．
一致したら各々そのインデックスの要素をaまたはbとし，残りの要素はbが連続し，bがなくなれば残りはaを連続させるといった具合に，辞書の中でも一番最後に来る文字列にすればいいだけです．

これならすべてのパターンを考えずにすみ，計算するだけなのでfor文でまわしても最大で***O(60)***になります．

a,b,k=map(int,input().split())
n=a+b

def cmb(n,r) :
    r=min(n-r,r)
    if r==0:
        return 1
    over=reduce(mul,range(n,n-r,-1))
    under=reduce(mul,range(1,r+1))
    return over//under

ans=""
for i in range(n) :
    antt=cmb(n-i-1,a-1)
    bntt=antt+cmb(n-i-1,b-1)
    if k<antt :
        a-=1
        ans+="a"

    elif k==antt :
        ans+=("a"+"b"*b+"a"*(a-1))
        print(ans)
        exit()

    elif antt<k<bntt :
        b-=1
        k-=antt
        ans+="b"

    elif bntt==k :
        ans+=("b"+"b"*(b-1)+"a"*a)
        print(ans)
        exit()

    else :
        continue

###E問題
問題文を読んで，辺の長さは深さから1引けば出てくるので，その途中でUiがあればいいのかな，と考えていたら時間切れになりました．
答えをみたら深さ優先探索みたいですね．この問題は復習してからぜひまた解きたいです．

###F問題
問題文すら読んでないですねえ……
#最後に
今回は，割と全体的に満足いく出来でした．D問題ですんなり解法を思いつけたのが良かったです．しかし，C問題でまだまだ計算量に関する知識が不足しているなと思いました．一度どこかで計算量についてはがっつり勉強したいですね．この調子でいけば，早めに緑までいけるかも……！！

あとそろそろアルゴリズム勉強会第２回を頑張ってのせます……