AtCoder ARC113 個人的メモ

所感

abc3完
highest更新

A - A*B*C

変数が$A,B,C$の$3$つある
変数を$2$つにしたいので$ABC\leqq K$を$AB\leqq \lfloor K/C\rfloor(\leqq K/C)$に変形する
これで$C$を全探索しつつ各$C$の値で$AB$を$O(1)$で求められれば，全体の計算量は$O(K)$となり良さそう
$A,B$の組み合わせは$\lfloor K/C\rfloor$を素因数分解すれば求められる
これを事前に各値において計算しておけば$A,B$の組み合わせは$O(1)$で求められる
$\lfloor K/C\rfloor\leqq K$だから，その範囲で事前計算する

from collections import Counter
from itertools import accumulate


def integer_factorization_list(n: int):
    """
    入力された整数nを素因数分解し，素因数が列挙されたリストで返却
    Parameters
    ----------
    n : int
        素因数分解したい整数
    Returns
    -------
    integer_factorization_list : lst
        [素因数]の形で素因数が列挙された素因数分解結果
    """
    res = []
    for candidate_of_prime in range(2, int(n ** 0.5) + 1):
        while n % candidate_of_prime == 0:
            n //= candidate_of_prime
            res.append(candidate_of_prime)
    if n > 1:
        res.append(n)
    return res


K = int(input())
# K = 2 * 10 ** 5

cumsum = [0]
for a in range(1, K + 1):
    primes = Counter(integer_factorization_list(a))
    res = 1
    for i in primes.values():
        res *= i + 1
    cumsum.append(res)
    # print(a, primes.values())

cumsum = list(accumulate(cumsum))
# print(cumsum)

ans = 0
for c in range(1, K + 1):
    ans += cumsum[K // c]

print(ans)

B - A^B^C

自然数を累乗していくと$1$の位は循環することが分かる
この性質を使えば$A^D(D=B^C)$の$1$の位は求められる
で，$D$を求めたいわけだが，$A$の累乗は一定の周期で循環するので，その周期で$D$の余剰を取った値を用いればおｋ

A, B, C = map(int, input().split())

a_loop = []
res = A
while str(res)[-1] not in a_loop:
    a_loop.append(str(res)[-1])
    res *= A

D = pow(B, C, len(a_loop))

# Dを-1しているのはD mod len(a_loop)とa_loopのインデックスが対応してないから  
ans = a_loop[(D - 1) % len(a_loop)]

print(ans)

C - String Invasion

右端から愚直に操作すれば良さそう
$aabaab$，$aaba$のような場合に注意しつつ実装
詳しい解説は明日書くかも

from collections import Counter
S = input()

ans = 0
between_cnt = Counter(S[-2:])
last = ("", -1)
for i in range(len(S) - 3, -1, -1):
    if S[i] == S[i + 1] and S[i] != S[i + 2]:
        ans += len(S) - (i + 2) - (between_cnt[S[i]] - 1)
        last = S[i]
        # print(ans, between_cnt)
        between_cnt = Counter()
        between_cnt[S[i]] += len(S) - i

    else:
        between_cnt[S[i]] += 1

print(ans)