はじめに
初心者がAtCoderの問題についてまとめています．
もし誤りがありましたら，コメントをお願いします．
B - lon2(N)
問題
正整数$N$が与えられ，$2^k \leqq N$となる最大の整数$k$を求める.
制約
$N$は$1 \leqq N \leqq 10^{18}$を満たす整数．
ポイント
この問題は難しくはないが，$log$を用いて計算するより，整数のまま計算したほうが良い．
解答
n = int(input())
k = 0
while n // 2:
n = n // 2
k += 1
print(k)
C - One More aab aba baa
問題
文字列$S$の各文字列を並べ替えて作ることが可能な文字列を順序式に全て列挙したとき，前から$K$番目にくる文字列を求めよ
制約
- $1 \leqq |S| \leqq 8$
- $S$は英小文字のみからなる
- $S$の各文字を並べ替えてできる文字列は$K$種類以上存在する
ポイント
Pythonには全ての組み合わせを求めるitertoolsがある．これを用いることにより，比較的に簡単に求めることができる．
解答
import itertools
s, k = tuple(input().split())
k = int(k)
s_list = sorted(set(itertools.permutations(s)))
ans = ''.join(s_list[k-1])
print(ans)
D - Coprime 2
問題
長さ$N$の正整数$A=(A_1,A_2,...,A_N)$が与えられ，以下の条件を満たす$1$以上$M$以下の整数$k$を求めよ．
- 全ての$1 \leqq i \leqq N$を満たす整数$i$について，$gcd(A_i, k)=1$である．
制約
- 入力は全て整数
- $1 \leqq N, M \leqq 10^5$
- $1 \leqq A_i \leqq 10^5$
ポイント
まず，$gcd(A_i, k)=1$というのは，最大公約数が$1$ということである．つまり，$A$のリストの中の約数を全て求めて，重複を削除すれば答えに辿り着く．しかし，D問題から計算量が重要となる．そのため，全ての場合を当たるという計算方法ではうまくいかない．
次の順に求める．
- $A$のリストにある数は答えにならない
- 素数だけを取り出し，$A$の約数であるかを確認
- 使えない素数を用いてその倍数を答えから除外
コードに示すと以下のようになる．
解答
N, M = map(int, input().split())
A = list(map(int, input().split()))
# どこの数まで求めるか
maxA = max(max(A), M)
# 答えの候補
k = [True] * (maxA+1)
# 素数のみTrue
isprime = [True] * (maxA+1)
# 使えない素数を保持
prime = []
# Aのリストにある数は答えにならない
for i in A:
k[i] = False
for i in range(2, maxA+1):
# 素数のみ調べる
if not isprime[i]:
continue
for j in range(i*2, maxA+1, i):
# jはiの倍数だから素数ではない
isprime[j] = False
# k[j]にAのリストの数が含まれていたらk[i]使えない素数
k[i] = k[i] and k[j]
if not k[i]:
prime.append(i)
# 使えない素数の倍数を削除
for p in prime:
for j in range(2*p, maxA+1, p):
k[j] = k[j] and k[p]
# 答えを作成
ans = [1]
for i in range(2, M+1):
if k[i]:
ans.append(i)
# 答えを表示
print(len(ans))
for i in ans:
print(i)
まとめ
これから週に1回このような感じでまとめていけたらいいと思ってます．
誤りやコードに関して修正した方がいい点があれば，コメントお願いします．
参考記事
- AtCoder
- itertoosの使い方
- tupleから文字列
- D問題の解答
- Qiitaの記事の書き方