🗂

AtCoder ARC113 個人的メモ

2 min read

所感

abc3完
highest更新
arc113score

A - A*B*C

変数がA,B,C3つある
変数を2つにしたいのでABC\leqq KAB\leqq \lfloor K/C\rfloor(\leqq K/C)に変形する
これでCを全探索しつつ各Cの値でABO(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の余剰を取った値を用いればおk

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

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

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)