😽

【python】100日後に緑コーダーになるためのABC215 A,B,C,D問題【16日目】

2021/12/04に公開約2,200字

はじめに

100日後に緑コーダーになるためにAtcoder Beginner Contest215の解説を行います。
今回はA ~ D問題です。
使用言語はpythonです。
ACコードだけでなく出題者の意図や考察過程も記述しています。
気になるところや要望があればお気軽にコメントください。
それでは解説です。

対象読者

灰・茶コーダー

A - Your First Judge

https://atcoder.jp/contests/abc215/tasks/abc215_a

解法

完全一致判定

出題者の意図

文字列の受け取り
if文が使えるか

コード

S = input()

if S == 'Hello,World!':
    print('Yes')
else:
    print('No')

B - log2(N)

https://atcoder.jp/contests/abc215/tasks/abc215_b

解法

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

https://atcoder.jp/contests/abc215/tasks/abc215_c

解法

順列全探索

出題者の意図

計算量から全探索しても大丈夫か見積もれるか

考察

制約が1≤S≤8であるため計算量は高々O(40320)なので全探索しても問題なし。まずはこれに気付くことが大事
リストから順列を生成するために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

https://atcoder.jp/contests/abc215/tasks/abc215_d

解法

1~Mまでの数字からAの素因数の倍数を削除していく

出題者の意図

素因数分解できるか
重複する数を1回だけのシミュレートで計算量を削除できるか

考察

問題文からkはAの全てに対して互いに素であることがわかる
愚直に1~Mまで探索していくと計算量が間に合わない
考え方を変えて、答えはAに含まれる素因数の倍数以外であるといえる
Ai全てについて素因数分解していき、それをsetに格納して計算量を削減していく
(素因数分解のライブラリをもっておくと本番中に楽だと思います)

コード

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

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