😽
【python】100日後に緑コーダーになるためのABC215 A,B,C,D問題【16日目】
はじめに
100日後に緑コーダーになるためにAtcoder Beginner Contest215の解説を行います。
今回はA ~ D問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。
対象読者
灰・茶コーダー
A - Your First Judge
解法
完全一致判定
出題者の意図
文字列の受け取り
if文が使えるか
コード
S = input()
if S == 'Hello,World!':
print('Yes')
else:
print('No')
B - log2(N)
解法
2^kをシミュレートして判定
出題者の意図
logの誤差を考慮して累乗で判定できるか
考察
logや図形の傾きなどで小数が発生する場合は、累乗や掛け算を使ってなるべく整数になるようにしよう
コード
N = int(input())
for k in range(61):
if 2**k > N:
print(k-1)
exit()
C - One More aab aba baa
解法
順列全探索
出題者の意図
計算量から全探索しても大丈夫か見積もれるか
考察
制約が
リストから順列を生成するためにpermutationsを使おう
これで方針はOK
与えられたSは辞書順に並んでいないことがあるためsort
重複を許して順列を生成してしまっているので、setで管理して未登場の文字列ならカウントしていく
カウントがKになったら答えを出力
コード
from itertools import permutations
S,K = map(str,input().split())
S = list(S)
S.sort()
K = int(K)
dict = set()
cnt = 0
for l in permutations(S,len(S)):
if l not in dict:
cnt+=1
dict.add(l)
if cnt == K:
print(''.join(l))
exit()
D - Coprime 2
解法
1~Mまでの数字からAの素因数の倍数を削除していく
出題者の意図
素因数分解できるか
重複する数を1回だけのシミュレートで計算量を削除できるか
考察
問題文からkはAの全てに対して互いに素であることがわかる
愚直に1~Mまで探索していくと計算量が間に合わない
考え方を変えて、答えはAに含まれる素因数の倍数以外であるといえる
（素因数分解のライブラリをもっておくと本番中に楽だと思います）
コード
N,M = map(int,input().split())
A = list(map(int,input().split()))
####素因数分解####
def prime_factorize(n):
a = set()
while n % 2 == 0:
a.add(2)
n //= 2
f = 3
while f * f <= n:
if n % f == 0:
a.add(f)
n //= f
else:
f += 2
if n != 1:
a.add(n)
return a
########
divisors = set()
for a in A:
for b in prime_factorize(a):
divisors.add(b)
L = [True]*(M+1)
for d in divisors:
for dd in range(d,M+1,d):
L[dd] = False
ans = []
for i in range(1,M+1):
if L[i] :
ans.append(i)
print(len(ans))
for s in ans:
print(s)
Discussion