AtCoder Beginner Contest 171 参戦記

20分でE問題まで終わって、これは初の全完!?と思ったが、Fの問題文を見た瞬間に無理だーってなって、232位から700番台まで下がっていくのを80分眺めることになった.

ABC171A - αlphabet

1分半で突破. 書くだけ.

A = input()

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

ABC171B - Mix Juice

1分半で突破. 書くだけ. B問題で sort が出てくるのは珍しいのでは?

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

p.sort()
print(sum(p[:K]))

ABC171C - One Quadrillion and One Dalmatians

5分半で突破. 過去にEXCEL列名と数字の双方向の変換を書いたことがあったので、それを引っ張り出してきて Python に落とした. 微妙に26進数でもない辺りがいやらしいというか.

N = int(input())

t = []
while N > 0:
    N -= 1
    t.append(chr(N % 26 + ord('a')))
    N //= 26
print(''.join(t[::-1]))

ABC171D - Replacing

6分で突破. 先週の ABC170E - Count Median を思い出した. 現在値を引いて、新値を足すという操作をループするのが似てる. 合計値をループごとに計算すると O(NQ) になってしまうが、引いて足すというつじつま合わせをすることによって計算量が O(N+Q) になって解ける.

from sys import stdin
readline = stdin.readline

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

t = [0] * (10 ** 5 + 1)
s = sum(A)
for a in A:
    t[a] += 1

for _ in range(Q):
    B, C = map(int, readline().split())
    s -= B * t[B]
    s += C * t[B]
    t[C] += t[B]
    t[B] = 0
    print(s)

ABC171E - Red Scarf

5分で突破. 一目簡単すぎて、誤読かと一瞬思った. xor の特性からして、自分以外の全ての xor と自分を含めた全ての xor を xor すれば自分が出てくるのは分かる. そして、a を全て xor すれば自分を含めた全ての xor が出来るのも分かる.

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

t = 0
for e in a:
    t ^= e

print(*[e ^ t for e in a])

ABC171F - Strivore

全然わかりません. 本当にありがとうございました. 入力例の oof に o を一つ挿入するのでも、3つダブるのだが、このダブリをどう除去するのかが全然思いつかない.

追記: 解説動画通りに実装しました. 何も考えずに投稿して TLE になって、あるぇ? ってなりましたが、定数倍が重い O(NlogN) なのでありえる話でした. PyPy で再投して AC. しかし、abc でも aaa でも実は一緒なのですという解説を聞いた瞬間の mjd 感はすごかった. この問題から得た経験値は高かったと思う.

K = int(input())
S = input()

m = 1000000007


def make_factorial_table(n):
    result = [0] * (n + 1)
    result[0] = 1
    for i in range(1, n + 1):
        result[i] = result[i - 1] * i % m
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m


fac = make_factorial_table(len(S) - 1 + K)

result = 0
for i in range(K + 1):
    result += pow(26, i, m) * mcomb(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, m)
    result %= m
print(result)

追々記: テーブルを作るのを止めたら Python でもギリギリ通りました. pow(n, -1, m) を pow(n, m - 2, m) にすると通らなくなりますが…….

K = int(input())
S = input()

m = 1000000007

result = 0
l = len(S)
t = pow(26, K, m)
u = pow(26, -1, m) * 25 % m
for i in range(K + 1):
    # result += pow(26, K - i, m) * mcomb(len(S) - 1 + i, i) * pow(25, i, m)
    result = (result + t) % m
    t = (t * u) % m * (l + i) % m * pow(i + 1, -1, m) % m
print(result)