【Atcoder解法検討】ABC301 A~D Python

A - Overall Winner

問題ページ : A - Overall Winner

考察

文字列S中の"A"及び"T"の数をかぞえ、異なるなら大きい方、同じであるなら最後の勝者でない方、を出力。

コード

N = int(input())
S = input()

A, T = 0, 0
for i in range(N):
    if S[i] == "A":
        A += 1
    else:
        T += 1

if A > T:
    print("A")
elif A < T:
    print("T")
elif A == T and S[-1] == "T":
    print("A")
elif A == T and S[-1] == "A":
    print("T")

B - Fill the Gaps

問題ページ : B - Fill the Gaps

考察

愚直実装で計算量的にはOK。ただし、操作毎に数列$A$を処理すると$index$の扱い等処理が面倒なので、$A[i]$と$A[i+1]$の間に挿入する数列を$B[i]$（空集合の場合もある）として求め最後にマージします。

コード

N = int(input())
A = list(map(int, input().split()))

B = [ [] for _ in range(N-1)]
for i in range(N-1):
    if A[i] < A[i+1]:
        B[i] = list(range(A[i]+1,A[i+1]))
    elif A[i] > A[i+1]:
        B[i] = reversed(list(range(A[i+1]+1,A[i])))

ans = []
for i in range(N-1):
    ans += [A[i]]
    ans += B[i]
ans += [A[N-1]]

print(*ans)

C - AtCoder Cards

問題ページ : C - AtCoder Cards

考察

並び変えて一致するか否かを判定するのに、分布（各文字が何文字あるか）だけみれば良いのは鉄則です。
"atcoder"以外の文字はSとTで各文字数が一致している必要があります。
"atcoer"に含まれる文字は各文字数の違いが"@"の数で吸収できるかで判定します。

コード

S = input()
T = input()

L =list("atcoder")
LL = list("abcdefghijklmnopqrstuvwxyz")
scnt = [0] * 26
tcnt = [0] * 26
sat = 0
tat = 0

for s in S:
    if s == "@":
        sat += 1
    else:
        scnt[ord(s)-97] += 1

for t in T:
    if t == "@":
        tat += 1
    else:
        tcnt[ord(t)-97] += 1

flag = True
for l in LL:
    if l not in L and scnt[ord(l)-97] != tcnt[ord(l)-97]:
        flag = False
    elif l in L and scnt[ord(l)-97] > tcnt[ord(l)-97]:
        tat -= scnt[ord(l)-97] - tcnt[ord(l)-97]
    elif l in L and tcnt[ord(l)-97] > scnt[ord(l)-97]:
        sat -= tcnt[ord(l)-97] - scnt[ord(l)-97]

if sat <0  or tat <0 or sat != tat:
    flag = False

if flag:
    print("Yes")
else:
    print("No")

D - Bitmask

問題ページ : D - Bitmask

考察

「N以下」という大小判定が必要な問題は最上位の桁(bit)から処理していきます。着目している"?"を1にして、それ以外の未決定の"?"を0にしたものがN以下か判定します。N以下であれば1を入れていき、そうでなければ0を入れていきます。0を入れてもN以下にならないケースもあるのですがこれは最後に判定すれば十分です。

コード

S = list(input())
N = int(input())
num = len(S)
pos = []

for i in range(num):
    if S[i] == "?":
        pos.append(i)
        S[i] = "0"

for p in pos:
    T = S.copy()
    T[p] = "1"
    if int("".join(T), 2) <= N:
        S[p] = "1"

ans = int("".join(S),2)
if ans <= N:
    print(ans)
else:
    print(-1)

青色diff以上は後日挑戦