【AtCoder】ABC215をPython3で解説（ABCD）

ABC215のA-D問題の解説。

A - Your First Judge

解説

条件分岐の問題。
問題文のとおりにifを書いてあげるとAC。

コード

s = input()

if s == 'Hello,World!':
    print('AC')
else:
    print('WA')

B - log2(N)

解説

$2^k \leq N$となる最大の$k$を求める問題。

$k$に1ずつ足していき、$N$を超えたら、break でループを回す。

コード

n = int(input())
k = 0

while True:
    if 2 ** k > n:
        print(k-1)
        break

    k += 1

C - One More aab aba baa

解説

文字列Sの各文字を並べ替えて、作成可能な文字列を辞書順にすべて列挙するというもの。
今回、最大値が$8!$なので、十分全探索できる数である。

Pythonでは、itertools.permutations()というライブラリ関数があるので、これを用いることでかんたんに実装することができる。

コード

from itertools import permutations

s, k = input().split()
k = int(k)-1
s = sorted(list(s))
ans = set()

for w in permutations(s):
    word = ''.join(w)
    ans.add(word)

ans = sorted(list(ans))
print(ans[k])

D - Coprime 2

解説

$gcd(A_i, k) = 1$、つまり、互いに素数になる$k$を求めるという問題。

このとき、$A_i$の最大長が$10^5$なので、普通にやると間に合わないので、工夫が必要だ。

どのようにするかというと、2ステップある。

1. Aに含まれる素因数を全列挙
2. エラトステネスの篩的操作

まず、1についてだが、Aの数列の素因数を全列挙する。全列挙するのは、例えば、Aが3と互いに素であるものを判別したいときに、Aが4, 6, 2とする。このとき、6に3が素因数として含まれているので、これは条件を満たさない。したがって、1つでも何かの倍数となるものは予め取り除いておく必要がある。したがって、これに関するリストを先に作成する。

次に、2についてだが、エラトステネスの篩的操作をする。エラトステネスの篩というのは、例えば、1-100までの数字があったとして、1を除き、2から順番にその倍数を取り除いていき、素数を見つけるというものだ。くわしくはこちらの記事をみていだきたい。

この操作はどのようにしていくかを解説する。まず、okというリストにあらかじめTrueをいれておく。つまり、値がまだリストに存在しているということだ。そしてそこに、先ほど求めた素因数をもちいてひとつずつみていく。m以下の整数で、素因数とその倍数を含むものをひとつずつ取り除いていくと、やがて、それ以外の数字がTrueとしてokに存在することとなる。したがって、これらの整数がAと互いに素となる整数となる。

上記の説明をコードで書き記したものが以下のようになる。コードに解説も書いているので、デバッグなど行いながら少しずつ噛み砕いていただきたい。

コード

n, m = map(int, input().split())
nlist = [False]*100001
alist = map(int, input().split())

for a in alist:
    nlist[a] = True

dlist = []

# A全体の素因数を求める
for i in range(2, len(nlist)): # 2から順番に
    flag = False # flagの設定
    for j in range(i, len(nlist), i):
        if nlist[j]: # もしAのなかにiの倍数のものがあれば
            flag = True # フラグを立てる
    if flag: # Trueであれば、dlistに追加
        dlist.append(i)

ok = [True]*(m+1) # m以下の数値の保存場所

# エラトステネスの篩的操作
for d in dlist:
    for j in range(d, m+1, d): # m以下でdの倍数にあたるもののflagを壊していく
        ok[j] = False

cnt = 0

for i in range(1, m+1): # 出力する数、つまり、okのTrueの数をカウントして出力
    if ok[i]:
        cnt += 1

print(cnt)

for i in range(1, m+1): # okでTrueになっているところを出力
    if ok[i]:
        print(i)

編集後記

こんな解説記事書いていますが、今回に至ってはC問題も解けない阿呆になってました。（）