ABC215 参加記録

• 4完1ペナ 39分でした

A - Your First Judge

完全一致というところに気をつけて実装します。python では == で良いです。

S = input()
if S == 'Hello,World!': print('AC')
else: print('WA')

B - log2(N)

問題タイトルは計算量ですね。 であっても、 側の は くらいで を超えます。従ってそれ以上の数でループさせて確かめれば良いです。

N = int(input())
for k in range(1000):
    if 2**k > N: break
print(k-1)

C - One More aab aba baa

は 8 文字なので、並び替えをしても間に合います。その後、重複を除いて 番目を指せば答えです。計算量は です。

S, K = input().split()
S = list(S)
K = int(K)
permS = list(set(permutations(S, len(S))))
permS.sort()
print(''.join(permS[K-1]))

D - Coprime 2

各 で を満たすには、それぞれの の素因数を が持っていないようにしないといけないです。 を素因数分解して素因数の集合として持ちます。集合の大きさは、最大でも 以下の素数の個数分で 10000 個ほどになります。

あとは を回した際、この素因数の集合で割り切れないことを確認していけば良いです。最悪計算量は になってしまいますが、割り切れないことを確認する際にほとんどの数は 2, 3 個の素因数の集合の要素を見るだけでスキップされるので重くなりません。

提出コード

# 素因数分解
def prime_factorize(n:int) -> list:
    """
    素因数分解を O(\sqrt{n}) で行う

        Parameters:
        -----------
        n: int
            2以上の整数
        
        Returns:
        --------
        a: list
            n の素因数のリスト
        e.g.
            input: 2940
            output: [2, 2, 3, 5, 7, 7]
    """
    assert n > 1, 'assert n > 1'
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    divset = set()
    for a in A:
        if a == 1: continue
        divset.update(set(prime_factorize(a)))
    divlist = list(divset)
    divlist.sort()
    ans = []
    for k in range(1, M+1):
        flag = True
        for p in divlist:
            if k%p == 0:
                flag = False
                break
        if flag: ans.append(k)
    ans.sort()
    print(len(ans))
    print(*ans, sep='\n')


if __name__ == "__main__":
    main()

E - Chain Contestant

bitDP ぽいところまで考えましたが、応用できませんでした。

F - Dist Max 2

これも正直よく見る形かなと思います。後日復習したいと思います。