📘

2022/03/30に公開

# A - Your First Judge

import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

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

if __name__ == '__main__':
main()


# B - log2(N)

import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
n = int(input())
t,ans = 1, 0
while t*2<=n:
ans += 1
t *= 2
print(ans)

if __name__ == '__main__':
main()


60乗程度なので、nを超えない範囲で2の階乗を考えればokです

# C - One More aab aba baa

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
s,k = input().split()
lst = list(set(list(itertools.permutations(s))))
lst = [''.join(t) for t in lst]
lst = sorted(lst)
print(lst[int(k)-1])

if __name__ == '__main__':
main()


Sは8文字以下と短いので、その並べ方は8!=40320程度と少ないことに着目します。
よって候補となるユニークな文字列を辞書順でソートしてK番目を参照すれば十分です。
pythonではitertoolsという便利なライブラリがあるので色々と便利です!

# D - Coprime 2

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def prime_decomposition(n):
i = 2
tank = []
while i * i <= n:
while n%i == 0:
n /= i
tank.append(i)
i += 1
if n > 1:
tank.append(int(n))
return tank

def main():
n,m = map(int, inputs().split())
a = list(map(int, inputs().split()))
ans = [True]*(m+1)
ans[0] = False
used = set()
for x in a:
p = prime_decomposition(x)
for y in p:
if y in used:
continue
else:
i = 1
while y*i<=m:
ans[y*i] = False
i += 1
used.add(y)
print(sum(ans))
for i in range(1, m+1):
if ans[i]:
print(i)

if __name__ == '__main__':
main()


osa_k法によってaで考慮される素因数をまとめて出すとTLEでした。

# E - Chain Contestant

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
mod = 998244353
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
n = int(input())
s = input()
idx = { c:i for i,c in enumerate('ABCDEFGHIJ') }
dp = [[[0]*10 for _ in range(pow(2,10))] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
c = idx[s[i]]
for j in range(pow(2,10)):
for k in range(10):
# i番目に不参加の場合
dp[i+1][j][k] += dp[i][j][k]
dp[i+1][j][k] %= mod

# i番目に参加する場合
# 既に参加済みかつ最後の文字と異なる場合では、文字s[i]が塊となっていない
if j&(1<<c) and k!=c:
continue
else:
nx = j | (1<<c)
dp[i+1][nx][c] += dp[i][j][k]
dp[i+1][nx][c] %= mod
ans = 0
for i in range(1,pow(2,10)):
ans += sum(dp[-1][i])
print(ans%mod)

if __name__ == '__main__':
main()


dp[i][j] := i文字目まで見たとき、最後の文字がs[j]の総数

ですが既出の文字をどのように管理すればよいかわからず、ACできませんでした...

dp[i][j][k] := i文字目まで見たとき、集合jは既に使用しており、最後の文字がs[j]の総数

これにより、既にbitが立っているかを参照することで、既出の文字を確認できます！
ただbitが立っていても最後の文字と連結することで塊となれることに注意しましょう。

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