AtCoder beginner Contest 171

A~Dまでを記載します。

##A - αlphabet

pythonだと「isupper（）」を使うことで一瞬で解けます。

Python

A = input()

if A.isupper():
    print('A')
else:
    print('a')

##B - Mix Juice

貪欲法？
金額の最小の商品から最適解の処理をひたすら繰り返します。

Python

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

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

A.sort()

ans=0
for i in range(K):
    ans+=A[i]

print(ans)

##C - One Quadrillion and One Dalmatians

• ぱっと見て、N進数の計算だと閃きます。基準は26文字です。
• 基本的な考え方はN進数の計算処理を適応します。
• 全探索によるO(N)になります。

再起処理の記述にすると綺麗に記載できると思われます。

• 基準値26以下を終了条件にします。
• zの数字のみ個別に対応する必要があります。

26にてzの文字列結合を行います。
その後、26/26=1とし、'a'が表示されることに気付きます。
つまりzの時のみN/26の商の部分から１を引くことで計算が上手く行く事に気づく事ができます。

• z以外の数字はN/26の商で対応できます。

Python

def dfs(num):
    if num<=26:
        return chr(96+num)
    elif num%26==0:
        return dfs(num//26-1)+chr(122)
    else:
        return dfs(num//26)+chr(96+num%26)
 
N = int(input())
 
print(dfs(N))

##D - Replacing

• 全探索だとO(NQ)で最大10億を超えるループになります。
• つまりO(N)の形に処理を変更しなければなりません。
• Aの入力にて渡される要素の個数を計測
• B、CにてAの要素が変更される数だけ合計値を増減する
• NのMAX値が100000なのでmapなどを使用する際には100001の要素を確保しましょう。

Python

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

SUM=0
numbers=[0]*100001
for i in range(N):
    a=A[i]
    numbers[a]+=1
    SUM+=a

B=[0] * Q
C=[0] * Q
for i in range(Q):
    B[i],C[i]  = list(map(int, input().split()))

for i in range(Q):
    b = B[i]
    c = C[i]

    SUM = SUM - b * numbers[b]
    SUM = SUM + c * numbers[b]
    numbers[c] += numbers[b]
    numbers[b] = 0
    print(SUM)

##E - Red Scarf

• 排他的論理和（xor）とは

比較した際に異なるbitなら1を返す回路の事です。
例えば、3が0011、5が0101なら、

a	b	c
0	0	0
0	1	1
1	0	1
1	1	0

0110は6になります。
また、xor回路は同じ値を処理した際、３ ^ 3 = 0となります。
0011と0011は全て同じbit配列になるからです。
このxorを今回の問題にて使用します。

N個の要素があるとして入力からNを受け取ります。
N個の要素にて、i番目以外の要素をxorにて処理した際の値がAiとして入力として受け取る事ができます。

入力された値をA1, A2, A3, ...., Anとした際、
求める値を　X1, X2, X3, ...., Xnと対応するとして

X	A	C
x1	A1	X2 ^ X3 ^ X4
x2	A2	X1 ^ X3 ^ X4
x3	A3	X1 ^ X2 ^ X4
x4	A4	X1 ^ X2 ^ X3

という表ができます。
そして、X1 ^ X1 = 0 を利用し、X1 ^ X1 ^ X1 = X1となる事を思い出してください。

A1 ^ A2 ^ A3 ^ A4 =
(X2 ^ X3 ^ X4) ^ (X1 ^ X3 ^ X4) ^ (X1 ^ X2 ^ X4) ^ (X1 ^ X2 ^ X3) =
（X1 ^ X2 ^ X3 ^ X4）

となります。そして、
（X1 ^ X2 ^ X3 ^ X4） ^ A1 = X1

を求める事ができます。
上記をプログラミングすると、

Python

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

X = 0
for i in range(0, N):
    X = X ^ A[i]

for i in range(0, N):
    print(X ^ A[i], end=' ')

print('')