😸

AtCoder ABC215 個人的メモ

2021/08/22に公開

Python

競技プログラミング

AtCoder

tech

所感

abcd4完

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から順に評価していけばおｋ

公式解説の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)

$1\leq |S|\leq 8$ なので、文字列 $S$ を並べ替えて作ることが可能な文字列は $8!=40320$ 通り。
これぐらいなら全列挙とソートをしても十分高速なので、全列挙してからソートして前から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)

参考

D - Coprime 2

各 $A_i$ の素因数の集合を $S$ とすると、整数 $k$ が $S$ に含まれているかを判定すれば $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_i$ が $s$ の末尾と同じ( $S_i$ のかたまりを大きくする)か $S_i$ が $s$ に含まれない(新しく $S_i$ のかたまりをつくる)場合を加えればおｋ。

これで解は得られそうだが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]$ となる。
ここに各 $bit$ に $i$ 番目のコンテストに出る場合を加算する。

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

遷移の計算量は $bit$ が $2^{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)