AtCoder Beginner Contest 215
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でした。
横着せずに、エラトステネスの要領で考えて1つ1つ素因数分解→未出の素因数のみ倍数を削除しましょう
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を考えました
ですが既出の文字をどのように管理すればよいかわからず、ACできませんでした...
解法としては集合をbitで管理するbitDPを用いればよいとのことで、以下のdpを考えます。
これにより、既にbitが立っているかを参照することで、既出の文字を確認できます!
ただbitが立っていても最後の文字と連結することで塊となれることに注意しましょう。
Author And Source
この問題について(AtCoder Beginner Contest 215), 我々は、より多くの情報をここで見つけました https://zenn.dev/ohnuma/articles/dab02af0189079著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol