AtCoder Beginner Contest 128

A / Apple Pie

単位換算してやるだけ。

def solve(A: int, P: int):
    print(int((3*A+P)/2))
    return

B / Guidebook

SとPを組み合わせて、昇順と降順にソートして(SP)、SPのもとの要素がどこにあったかを照らし合わせる。 この問題では複数の配列を組み合わせてソートする方法を学ぶことができた。

def solve(N: int, S: "List[str]", P: "List[int]"):
    # ソートのためにSPを合体
    SP =[]
    for i in range(N):
        SP.append([S[i],P[i]])

    # 都市名は昇順にし、同じ年の場合は降順でソートする 
    t = sorted(SP, key=lambda x:(x[0],-x[1]))

    ans = []
    for x in t:
        for j in range(N):
            x1,x2 = x
            if(x1 == S[j] and x2 == P[j]):
                ans.append(j+1)

    for i in ans:
        print(i)
    return

C / Switches

(on,off)の直積をN個で作って、全部を試す。 初心者ゆえ全探索をするのに組み合わせの「直積」という考え方を知ることができたのが一番の収穫。

def main():
    N,M = map(int,input().split())
    from collections import defaultdict
    d = defaultdict()
    for i in range(M):
        l = list(map(int,input().split()))
        d[i] = l[1:]

    p = list(map(int,input().split()))

    ans = 0
    import itertools
    s = ('on', 'off')
    for i in itertools.product(s, repeat=N):
        anst = 0
        for k,v in d.items():
            if(len([x for x in v if(i[x-1] == 'on')])%2 == p[k]):
                anst += 1

        if(anst == M):
            ans += 1
    
    print(ans)

D / equeue

dfsかな???

E,F

AtCoder Beginner Contest 126

A / Changing a Character

Python なので指定された番号の文字をlower()するだけ。

def solve(N: int, K: int, S: str):
    sl = list(S)

    sl[K-1] = sl[K-1].lower()

    print(''.join(sl))
    return

B / YYMM or MMYY

前半二文字と後半二文字で区切って、それぞれの部分で[1,12], 0 or [13,99]判定をする。

def solve(S: str):
    p1 = int(S[:2])
    p2 = int(S[2:])

    if(0 < p1 <= 12 and 0 < p2 <= 12):
        print('AMBIGUOUS')
    elif(0 < p1 <= 12 and (p2 == 0 or p2 > 12)):
        print('MMYY')
    elif((p1 == 0 or p1 > 12) and 0 < p2 <= 12):
        print('YYMM')
    else:
        print('NA')

    return

C / Dice and Coin

方針は、全部のサイコロの場合の確率を求めて、全部足しあげる。 1~Nまでのそれぞれのサイコロが出た場合の勝率は以下の通り。


\frac{1}{N} * \frac{1}{2}^t \\\
t = \log_2(\frac{K}{i})
def solve(N: int, K: int):
    ans = .0
    for i in range(1,N+1):
        if(i <= K):
            t = math.ceil(math.log2(K/i))
            ans += (1/N) * (1/2) ** t
        else:
            ans += 1/N

    print(ans)
    
    return

D / Even Relation

グラフが作れなくて終わり。

E / 1 or 2

Union-Find木は、自分ではちゃんと練習していたつもりでいたので、溶けなかったのはだいぶ悔しい。 この問題は、与えられる魔法を考慮したときに、「カードをめくる回数を一番少なくするにはどうしたらよいか?」を考える問題。 与えられるZは捨てて、XとYだけで、Union-Find木を構成すると、その連結成分が答え。

def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)

    for i in range(M):
        uf.union(X[i],Y[i])
    
    # 連結成分の数が答え
    print(uf.num_graph())

    return

F

ちょっと見てない

diverta 2019 Programming Contest

解答

A / Consecutive Integers

"連続した"値なのでN-(K-1)で良い。

B / RGB Boxes

全探索だが、3重ループは間に合いそうにないので、RとGは全部みて、Bは条件に合うか(非負であることとR,Gを使った残りを割り切れるか=(r,g,b)でちょうどNの組を作れるか)をチェックすればいける。

def solve(R: int, G: int, B: int, N: int):
    ans = 0
    for i in range(0, N+1, R):
        for j in range(0, N+1, G):
            x = N - i - j
            if(0 <= x and x%B == 0):
                ans += 1

    print(ans)
    return

参考(類題)

atcoder.jp

 

C / AB Substrings

追記)
下記の方針1について分岐が不足していたためWAだった。
ただ、WAのコードを見ると、共通部分と分岐先の計算の整理ができていなかったと思う。 解法としては、

  1. 共通部分として、max(0,x-1)とmin(a,b)を計算する。
  2. x >0 and (a > 0 or b > 0)の場合のみ+1する。(これはx > 1でaかbのどちらかが1以上であるとき、BxxA(カウントはx)の片方が'AB'になってくれるため)

↓@eijitさんに詳しく解説してもらった。

追記おわり)

ジャッジが詰まって、最後の結果はわからずACならずだったが、以下とった戦略である。

  1. 文字列をつなぐところで新しく'AB'になりうるのは「xxA」、「Bxx」、「BxxA」のみである。「xxA」と「Bxx」、「BxxA」はカウント-1で新規に’AB'を作れるので、それを数え上げる。
  2. すべての部分文字列でi.count('AC')
def solve(N: int, s: "List[str]"):
    x = 0; a = 0; b = 0
    ans2 = 0
    for i in s:
        ans2 += i.count('AB')
        if(i[0] == 'B' and i[-1] == 'A'):
            x += 1
        elif(i[-1] == 'A'):
            a += 1
        elif(i[0] == 'B'):
            b += 1
    
    #####    AC2   ####
    ans1 = max(0,x-1) + min(a,b)
    if((a > 0 or b >0) and x > 0):
        ans1 += 1
    
    print(ans1+ans2)
    
    return

D~F

わかんないわかんないわかんない

 

AtCoder Grand Contest 023 / A - Zero-Sum Ranges

解法

  1. 入力配列の累積和を作る(A(n) -> s(n+1))。
  2. 累積和の値について同じ値を集計する。※累積和のうち{i \lt j}について{s_i = s_j}となる区間は累積和が0になる。

  3. (Pythonの場合) collectionsにあるCounterで累積和の同じ数を集計する。

  4.  {s_i} (n個)の中で2個選ぶ組み合わせの総数を、すべての登場した数について数えあげる( k個の中で n個を選ぶ組み合わせは \frac{k(k-1)}{2}

import sys
from collections import Counter

def solve(N: int, A: "List[int]"):
    s = [0]*(N+1)

    for i in range(N):
        s[i+1] = s[i] + A[i]

    # print(s[:10])

    c = Counter(s)

    ans = 0
    for k,v in c.items():
        ans += v*(v-1)//2

    print(ans)
    
    return

参考

解説AC @drkenさんの神解説

qiita.com

AtCoder Beginner Contest 084 / D - 2017-like Number

解法

  1. エラトステネスのふるいで、制約条件である100000までの素数表を作る (myo)
  2. 1で作成した素数表をもとに、2017に似た数 表を作る (r2017)
  3. r2017_ の累積和を取る (rodd)__
  4. Qのクエリに rodd[$ r_{i+1} $] - rodd[ $l_i$ ] で答えていく。
def eratos(n :int):
    # initialize
    isprime = [True] * (n+1)
    isprime[0] = isprime[1] = False

    for i in range(2, int(math.sqrt(n)+1)):
        if(isprime[i]):
            j = i+i
            while(j <= n):
                isprime[j] = False
                j = j+i

    return isprime

def solve(Q: int, l: "List[int]", r: "List[int]"):
    myo = eratos(100000)
    rodd = [0]*100001

    r2017 = [False]*100001
    for i in range(1,100001):
        if(i%2 == 0):
            continue
        elif(myo[i] and myo[int((i+1)/2)]):
            r2017[i] = True

    for i in range(2,100001):
        rodd[i] = rodd[i-1] +(1 if r2017[i-1] else 0)

    ans = [0]*Q
    for i in range(Q):
        ans[i] = rodd[r[i]+1] - rodd[l[i]]

    for i in ans:
        print(i)

    return

参考

@drkenさんの神解説

qiita.com

AtCoder Beginner Contest 114 / C - 755

Reiwa一発目から解説ACで悔しい(ビクンビクン

方針は以下。

  1. 制約条件のため、1~Nの全件調査は間に合わない。
  2. '753'のいずれかを含む値を 準753数 と定義して、これを全列挙する。

    • 停止条件:sが入力Nに達すること
    • 動作1:まず現在与えられている値の753数判定をする。
    • 動作2:その後、その結果とは関係なく、今の桁数+1の753数を作ってdfs。
  3. 優勝
def dfs(s :str, n: int):
    if(int(s) > n):
        return 0
    ret = 1 if all(s.count(c) for c in '753') else 0
    for c in '753':
        ret += dfs(s+c, n)
    return ret


def solve(N: int):
     # 0を入れないと、if(int(s) > n)で引掛かる
    print(dfs('0',N))