服を着たゾウに花束を

勉強の記録とか。

AtCoder Beginner Contest 167 振り返り

C - Skill Up

 

N冊の本でM個のスキルをX以上にするための最小コストを求めたい

f:id:terukine:20200625233024p:plain

実装:深さ優先探索

    def func(cost,a,i):
        if min(a) >= X:
            return cost
        elif i == N:
            return MAX
        total_A = [x+y for (x,y) in zip(a,A[i])]
        
        return min(func(cost + C[i],total_A,i+1),func(cost,a,i+1))

全部足し,コストを計算

行き止まりのMAXじゃないほうが選ばれる

 

Submission #13218188 - AtCoder Beginner Contest 167

 

F - Bracket Sequencing

N個の文字列Sを連結して括弧列を作成する

f:id:terukine:20200627230432p:plain

括弧列以外の部分を記録し,

")" の数と"("の数,どちらが多いかで2グループに分ける

先に"("が多いグループを,")"が少ない順に並べ,

その後に")"が多いグループを,"("が多い順に並べる

途中で")"に対応できるほどの"("が並べられなくなったら"No",括弧の数が異なっていても"No"

それ以外を"Yes"とすればよい

 

Submission #14779076 - AtCoder Beginner Contest 167