📘

AtCoder Beginner Contest 215

2022/03/30に公開約3,600字

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を考えました

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

ですが既出の文字をどのように管理すればよいかわからず、ACできませんでした...
解法としては集合をbitで管理するbitDPを用いればよいとのことで、以下のdpを考えます。

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

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

Discussion

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