Atcoder ABC202, 201 振り返り - hirohirohirohirosのブログ

A - Three Dice【AC】

　ある面と反対側の面を足すと7になるので，a, b, cの反対側の数は7-a, 7-b, 7-cとなるので，その和は21-1-b-cとなります．

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

B - 180°【AC】

　決まった文字列の変換は辞書を使うと簡単です．

dic = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}
S = input()[::-1]
print("".join([dic[s] for s in S]))

C - Made Up【AC】

　先に，BとCの変換を行っておきます．a in dic.keys()はO(n)かかると思うのですが実行時間はかなり短いです．辞書型のinはO(n)ではないのでしょうか……？

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [B[int(i)-1] for i in input().split()]

dic_c = {}
for c in C:
    dic_c.setdefault(c, 0)
    dic_c[c] += 1

ans = 0
for a in A:
    if a in dic_c.keys():
        ans += dic_c[a] 

print(ans)

D - aab aba baa【解説AC】

　なかなか難しかったです．まず，C[a][b] = "a"がa個，"b"がb個の文字列としてあり得る総数としたリストを作ります．これはDPを使って解ける基本的な問題です(ただ答えを見ないと分からなかったのでDP対策が必須です……)．
　コアとなる考え方は，a?????とb?????の文字列があった時，辞書順で並び替えると，?にどのような文字を入れても全てのパターンについて，a?????kの時，a???の総数がk個より多いということなので，b???ではなく，a???と確定します．よって，先頭をaにし，それ以降の文字を再帰的に求めます．使えるaの数が1つ減ったのでfind_k(a-1, b, k)とすれば良いです．
　C[a-1][b]<=kの時、a???の総数がk個より少ないと言うことなので，先頭がbだと確定します．同様にそれ以降の文字を再帰的に求めます．使えbの数が1つ減ったのでb-1, kはそのままではいけません．次の文字を求めるとき，そのままだとa???の総数の情報が消えてしまうので，求めるのはk番目ではなく，kからa???の総数を引いた数です．よって，find_k(a, b-1, k-C[a-1][b])となります．
　解説を読んだら理解出来るのですが自力でこれを構築するにはどうしたら良いのか……

A, B, K = map(int, input().split())
C = [[0 for _ in range(B+1)] for _ in range(A+1)]
C[0][0] = 1

for i in range(A+1):
    for j in range(B+1):
        if i > 0:
            C[i][j] += C[i-1][j]
        if j > 0:
            C[i][j] += C[i][j-1]

def find_k (a, b, k):
    if a == 0:
        return b*"b"
    if b == 0:
        return a*"a"
    if k <= C[a - 1][b]:
        return "a" + find_k(a-1, b, k)
    else:
        return "b" + find_k(a, b-1, k-C[a - 1][b])

print(find_k(A, B, K))

A - Tiny Arithmetic Sequence【AC】

　等差数列なのでソートしてやれば，一つの組について調べれば答えが出ます．

a = sorted([int(i) for i in input().split()])
if a[2]-a[1] == a[1]-a[0]:
    print("Yes")
else:
    print("No")

B - Do you know the second highest mountain?【AC】

　文字と数値が混ざったリストも簡単にソートできます．

lis = []
for _ in range(int(input())):
    a, b = input().split()
    lis.append([int(b), a])

lis = sorted(lis)
print(lis[-2][1])

C - Secret Number【AC】

　有り得るパスワードの数は多くても10000個なので，全てのパスワードのパターンについて，Sが成り立つか調べても間に合います．set型を使う事で，複数同じ値が入っても一つとして扱われます．.zfillを使うと文字を簡単に0埋めできます．解き終わってから気付きましたがcould要りませんね……

S = input()
ans = 0
must = set()
can = set()

for s in range(len(S)):
    if S[s] == "o":
        must.add(str(s))
    if S[s] == "?":
        can.add(str(s))

for i in range(10000):
    musted = set()
    could = set()

    passward = str(i).zfill(4)
    for j in passward:
        if j in must:
            musted.add(j)
        if j in can:
            could.add(j)
        if j not in must and j not in can:
            break
    else:
        if must == musted:
            ans += 1

print(ans)