😸

AtCoder ABC215 個人的メモ

4 min read

所感

abcd4完

https://atcoder.jp/users/m193/history/share/abc215

A - Your First Judge

S = input()

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

B - log2(N)

N=10^{18}でもkは60ぐらいなので、kを0から順に評価していけばおk

公式解説のbit表現を利用した解法は賢いなぁと思った

N = int(input())

ans = 0
while pow(2, ans) <= N:
    ans += 1

print(ans - 1)
bit表現を用いた解法
N = int(input())
print(N.bit_length() - 1)

C - One More aab aba baa

1\leq |S|\leq 8なので、文字列Sを並べ替えて作ることが可能な文字列は8!=40320通り。
これぐらいなら全列挙とソートをしても十分高速なので、全列挙してからソートして前からK番目の文字列を求めればおk。
全列挙にはitertoolsのpermutationsを使うと楽だが、Sに同じ文字が含まれている場合に同じ文字列が重複して出現する。
なので、set()を使って重複を除く必要がある。

from itertools import permutations

S, K = input().split()
K = int(K)

lst = set(permutations(S))
lst = sorted(lst)

ans = "".join(lst[K - 1])

print(ans)
 

参考

https://docs.python.org/ja/3/library/itertools.html#itertools.permutations

D - Coprime 2

A_iの素因数の集合をSとすると、整数kSに含まれているかを判定すればkが問題の条件を満たしているかが分かる。
A_iの素因数の列挙にO(\sqrt{A_i})、各kの判定は1回あたりO(log|S|)で求まるので十分高速に解が求まる。

def integer_factorization_set(n: int) -> list:
    """入力された整数nを素因数分解し,素因数が列挙された集合で返す

    Args:
        n (int): 素因数分解したい整数

    Returns:
        set: 素因数が列挙された素因数分解結果
    """
    res = set()
    for candidate_of_prime in range(2, int(n ** 0.5) + 1):
        while n % candidate_of_prime == 0:
            n //= candidate_of_prime
            res.add(candidate_of_prime)
    if n > 1:
        res.add(n)
    return res


N, M = map(int, input().split())
A = list(map(int, input().split()))  # 整数を入力

seen = set()
for a in A:
    seen |= integer_factorization_set(a)

ans = []
for i in range(1, M + 1):
    tmp_set = integer_factorization_set(i)
    if tmp_set & seen:
        continue
    ans.append(i)

print(len(ans))
print(*ans, sep="\n")

E - Chain Contestant

とりあえず問題を簡単にして計算量を気にせずdpを考えてみる。
コンテストが1種類のみとし、コンテストの種類ごとにひとかたまりにするという条件を無視する。
この場合はdp[i]i番目までのコンテストでのコンテストの選び方の集合とする。
遷移はi-1番目までの選び方の集合に対してi番目のコンテストに出るか出ないかの2つがあるので以下のようになる。

dp[i]=dp[i-1]\lor \sum_{s\in dp[i-1]} s+S[i]

これはコンテストが10種類の場合でも同じdp式と遷移になる(各コンテストは何番目のコンテストなのかで区別されるから)。

コンテストの種類ごとにひとかたまりとなる条件について考える。
この場合は上記と同じdpで遷移の際にi番目のコンテストに参加する場合の内で条件を満すもののみを加えれば良い。
つまり、S_isの末尾と同じ(S_iのかたまりを大きくする)かS_isに含まれない(新しくS_iのかたまりをつくる)場合を加えればおk。

これで解は得られそうだがdpにもつ集合が大きくなりすぎる。
遷移の際に必要な情報はsの末尾の文字とsに既出の文字の2種類のみ。
よって、dp[i][bit][k]を(i番目までのコンテストで、ビット集合で表されるbitのコンテストに出場済みで、最後に出場したコンテストの種類がkとなる場合の数)とする。
すると、i-1からiへの遷移はk=S_iにおいてのみで以下のようになる。

まず、コンテストに出ない場合としてdp[i][bit][k]=dp[i-1][bit][k]となる。
ここに各biti番目のコンテストに出る場合を加算する。

  • bitkが立っている場合
    最後に出場したコンテストがS_iと同じならS_iに出る場合があるのでそれを加算。
    dp[i][bit][k] += dp[i - 1][bit][k]
  • bitkが立っていない場合
    S_iと同じ種類のコンテストに未出場なので、S_iに出場すると新しいかたまりを作ることになる。
    新しいかたまりになるので直前のコンテンストは何でも良い。
    bitkを立てたものをbit'とすると以下のようになる。
    dp[i][bit'][k] += \sum_{j=1}^{10} dp[i - 1][bit][j]

遷移の計算量はbit2^{10}(10はコンテストの種類数)通りでkが10なのでO(10\times 2^{10})となり、全体でO(N\times 10 \times 2^{10})で十分高速となる。

N = int(input())
S = input()
MOD = 998244353
num_contest = 10

pattern_num = pow(2, num_contest)
# dp[i]はdp配列を使いわますことで省略
dp = [[0] * (num_contest) for _ in range(pattern_num)]
dp[0][0] = 1
for i in range(N):
    n_dp = [list(dp[j]) for j in range(pattern_num)]
    s = ord(S[i]) - ord("A")

    for bit in range(pattern_num):
        if bit & (1 << s):
            if n_dp[bit][s]:
                n_dp[bit][s] += dp[bit][s]
                n_dp[bit][s] %= MOD

        else:
            n_dp[bit ^ (1 << s)][s] += sum(dp[bit])
            n_dp[bit ^ (1 << s)][s] %= MOD

    dp = n_dp

ans = sum(sum(row) % MOD for row in dp)
# 初期化したときの1を引く
ans -= 1

print(ans % MOD)

Discussion

ログインするとコメントできます