AtCoder Beginner Contest 171 ／ Python

• 独学者です。（ 2019 / 9 ～ ）
• AtCoder の問題に Python で取り組んでいます。
• ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントください。

結果

今回あからさまに簡単だったよね。

これで C問題 までしか出来なかったのは引退勧告もの。

今回は猛省してちゃんと復習をしよう。

問題と解答と勉強

atcoder.jp

提出したコード

if input().islower():
    print("a")
else:
    print("A")

atcoder.jp

提出したコード

N, K = map(int, input().split())
p = sorted(list(map(int, input().split())))
 
print(sum(p[:K]))

atcoder.jp

提出したコード

alp = 'abcdefghijklmnopqrstuvwxyz'
N = int(input())
ans = ""
 
while N > 26:
    ans += alp[N%26-1]
    if N%26 != 0:
        N = N // 26
    else:
        N = N // 26 -1

ans += alp[N-1]
 
print(ans[::-1])

atcoder.jp

TLE

N = int(input())
A = list(input().split())
Q = int(input())
 
for _ in range(Q):
    B, C = input().split()
    A = [s.replace(B, C) for s in A]
    print(sum([int(i) for i in A]))

言われてるまんまのやつ。

まぁ通らないよね。

TLE

from collections import defaultdict
 
N = input()
A = list(map(int, input().split())) 

d = defaultdict(int)
for i in A:
    d[i] += 1
 
Q = int(input())
for _ in range(Q):
    B, C = map(int, input().split())
    d[C] += d[B]
    d[B] = 0
    ans = 0
    for i,j in d.items():
        ans += i*j
    print(ans)

多少早くなる。

でも通らない。

だがしかし、方針はこれで合っていたようで。

後で考えた通るやつ

from collections import defaultdict

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

d = defaultdict(int)
for i in A:
    d[i] += 1

ans = sum(A)
 
Q = int(input())

for _ in range(Q):
    B, C = map(int, input().split())
    ans = ans - B*d[B] + C*d[B]
    print(ans)
    d[C] += d[B]
    d[B] = 0

これなら通る。微妙な違いなんだけどねぇ。くそぉ。

defaultdict とか要らない

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
count = [0]*(10**5+1)

for i in A:
  count[i] += 1
 
ans = sum(A)

for i in range(Q):
  B, C = map(int, input().split())
  ans = ans - B*count[B] + C*count[B]
  print(s)
  count[C] += count[B]
  count[B] = 0

これで良かったんね。

と言うか、前回（ABC170）の D問題 と同じよね。

復習していると見せかけて適当にやっているのがバレてしまった。

ちゃんと復習してれば出来るだろうよぉ。

atcoder.jp

E問題 にしては非常に簡単だったっぽいが、

排他的論理和を理解してないと無理。

答え

n = int(input())
a = list(map(int, input().split()))
 
A = 0
for e in a:
    A ^= e
 
for i in range(n):
    if i != 0:
        print(' ', end='')
    print(A^a[i], end='')
print()

めっちゃ簡単。

なんだけど、

何でこれで答えが出るかさっぱりだ。

XOR（排他的論理和）の性質

①　　a ^ b == b ^ a

②　　(a ^ b) ^ c == a ^ (b ^ c)

③　　a ^ x ^ x == a

④　　a ^ x == b ^ x　　<=>　　a == b

⑤　　a != b 　　<=>　　a ^ x != b ^ x

今回の問題は①、②、③の性質で解くようだ。

与えられた数字４つは、

B ^ C ^ D
A ^ C ^ D
A ^ B ^ D
A ^ B ^ C

この４つの排他的論理和をとると。

(B ^ C ^ D) ^ (A ^ C ^ D) ^ (A ^ B ^ D) ^ (A ^ B ^ C)

②の性質より、

B ^ C ^ D ^ A ^ C ^ D ^ A ^ B ^ D ^ A ^ B ^ C

①の性質より、

A ^ A ^ A ^ B ^ B ^ B ^ C ^ C ^ C ^ D ^ D ^ D

③の性質より、

A ^ B ^ C ^ D

となり、この値と与えられた数字４つの排他的論理和をそれぞれとると、

(A ^ B ^ C ^ D) ^ (B ^ C ^ D)　⇒　A
(A ^ B ^ C ^ D) ^ (A ^ C ^ D)　⇒　B
(A ^ B ^ C ^ D) ^ (A ^ B ^ D)　⇒　C
(A ^ B ^ C ^ D) ^ (A ^ B ^ C)　⇒　D


という訳で、答えが出せる。

これ計算法を知ってたら終わりのやつ！

僕は全く知らんかったけど。

4000人もこれ知ってるんか。Atcoder やべぇな。



結局この原理を何に使うのかはわからなかったけど、

少しは排他的論理和についての理解が進んだ。

atcoder.jp

知らん！！