ABC171

NISHIO Hirokazu [Translate]
ABC171
5問解いたけど、まだ茶色です
atcoder
A　大文字か小文字か判断する問題、開始63秒
pythonfrom string import ascii_lowercase
s = input()
if s[0] in ascii_lowercase:
    print("a")
else:
    print("A")
B、N個の数値のうち、小さい方のK個を足し合わせる問題、100秒
pythonN, K = map(int, input().split())
PS = list(map(int, input().split()))
PS.sort()
print(sum(PS[:K]))

C　数値をExcel的な変則26進法で表現する問題。
この問題、観測範囲の人が軒並みD問題より時間を喰われている。罠。
いかにもハマりやすそうなので、doctestでテストケース書きながら3桁まで書き下ろして、それからwhileでまとめました。13分。
pythondef solve(N):
    q = N
    ret = ""
    while True:
        q, r = divmod(q - 1, 26)
        ret = ascii_lowercase[r] + ret
        if q == 0:
            print(ret)
            return
コード全体はこちら https://atcoder.jp/contests/abc171/submissions/14549017
開発過程を詳しく書いた テストドリブンで変形26進法の実装


D、10万個の数値があって、10万回「ある数値を別の数値に置換」をして、そのたびに総和を出力する問題
最初にぜんぶの数の個数をカウントして、総和を求めて、後は更新していくだけ。5分。
pythoncount = [0] * (10 ** 5 + 10)

def main():
    N = int(input())
    AS = map(int, input().split())
    sum = 0
    for a in AS:
        count[a] += 1
        sum += a
    Q = int(input())
    for q in range(Q):
        B, C = map(int, input().split())
        sum += (C - B) * count[B]
        count[C] += count[B]
        count[B] = 0
        print(sum)

E、最大20万個の数の「自分以外のxor」が渡されて、元の数を当てる問題。
初手「あれ？これ入力をそのまま返せばいいのでは？」と思ってダメ元でサブミットしたらやっぱりダメでした。結局N=2, 3, その他、で場合分けしたけど必要はなかったっぽい。
解が一意でない可能性があるので、正しい解であるかどうかのテストコードを書いて、N=4のテストケースを2進表記してじっくり眺めて、辻褄のあう式を捻り出し、正しい解になってることを確認してサブミット。
グダグダしてるのをそのまま載せると下記。前半のループで正しい答えのつもりだったのだけど間違ってて、正しい答えと見比べて、間違ってるところだけビットを反転してる。無理やりです。42分。二進表記
python"""
input
0b00000000000000000000000010100
0b00000000000000000000000001011
0b00000000000000000000000001001
0b00000000000000000000000011000

output
0b00000000000000000000000011010
0b00000000000000000000000000101
0b00000000000000000000000000111
0b00000000000000000000000010110

myanswer
0b00000000000000000000000000000
0b00000000000000000000000011111
0b00000000000000000000000011101
0b00000000000000000000000001100
"""
# for a in AS:
#     print(f"{a:#031b}")
r = [0] * N
for i in range(1, N):
    r[i] = r[i - 1] ^ AS[i - 1] ^ AS[i]

# for a in r:
#     print(f"{a:#031b}")

rest = reduce(xor, r[1:])
d = AS[0] ^ rest
for i in range(N):
    r[i] ^= d

print(*r)
# check
# total = reduce(xor, r)
# for i in range(N):
#     print(total ^ r[i] == AS[i])
reduceがfunctoolsに移動してるの知らなかった。

もっと簡潔に書いてる人のコードを見てみよう。ACで一番短い人のコードを…
python_,a=open(x:=0)
*a,=map(int,a.split())
for i in a:x^=i
for i in a:print(x^i)
https://atcoder.jp/contests/abc171/submissions/14588050
こ、これは…ゴルフだ…
まず3.8から導入されたセイウチ演算子でxに0を入れつつopen(0)している。これはファイルデスクリプタ指定でのopenで、0は標準入力だ。
開かれたファイルはPythonでは行単位のイテレータになるので、アンパック代入で入力の2行目がaに入る。
mapの結果はイテレータなので、スターで受けることで評価を強制してリストに変えている。これをしないと3行目のforでイテレータを食いつぶして4行目のforが回らない。
3行目で全体のxorを取って、4行目でそれとAiとのxorを出力している。これ改行区切りなので問題の「空白区切りで出力せよ」の条件をパスするのは意外。

これを踏まえて僕的に書くとこんな感じ
pythonfrom functools import reduce
from operator import xor

_N = int(input())
AS = list(map(int, input().split()))
total = reduce(xor, AS)
print(*[a ^ total for a in AS])

データ構造を勉強したのに全然出てない！
Fは解き直して、解けてから解説を書く。
ABC171_F