12 min readAtCoder
【備忘録】AtCoder Beginner Contest 215 A~D問題
AtCoder Beginner Contest 215のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。
- そもそもAtCoderとは?
- 「AtCoder Beginner Contest 215」
- A -> Your First Judge
- B -> log2(N)
- C -> One More aab aba baa
- D -> Coprime 2
- 参考文献
執筆者 - おすすめの記事3選
そもそもAtCoderとは?
AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。
今回は 「AtCoder Beginner Contest 215」のプログラミングコンテストへ参加しました。
「AtCoder Beginner Contest 215」
コンテスト情報
- コンテスト時間 : 100分
- レーティング更新対象 : 0 - 1999
配点
| 問題 | 点数 |
|---|---|
| A | 100 |
| B | 200 |
| C | 300 |
| D | 400 |
| E | 500 |
| F | 500 |
| G | 600 |
| H | 600 |
ルール
- コンテスト中に問題に正解すると点数を獲得できます。
- 順位は総合得点で決定します。
- 同点の場合は提出時間の早い人が上の順位になります。
- 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)
このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。
A -> Your First Judge
問題文
文字列Sが与えられるので、この文字列がHello,World!と完全に一致するならAC、そうでないならWAと出力してください。
「完全に一致する」とは? : 文字列AとBが完全に一致するとは、文字列AとBの長さが等しく、かつ全ての1 ≤ i ≤ 絶対値Aを満たす整数iについてAの先頭からi文字目とBの先頭からi文字目とが(英大文字か小文字かも含めて)一致することを指します。
制約
- 1 ≤ 絶対値S ≤ 15
- Sは英大小文字
,,!のみからなる
入力
入力は以下の形式で標準入力から与えられる。
1S出力
答えを出力せよ。
本問題は、AtCoder株式会社で作成された、A - Your First Judge問題を参照しております。
Contest中に考えたこと
- if文を用いて
Hello,World!の文字列と一致する場合はAC、そうでない場合はWAと返すようにプログラムを書くとうまくいきそう。
解答
1# 標準入力を受け付ける。
2S = input()
3
4# Hello,World!の文字列と一致する場合
5if S == 'Hello,World!':
6 print('AC')
7# Hello,World!の文字列と一致しない場合
8else:
9 print('WA')B -> log2(N)
問題文
正整数Nが与えられるので、2のk乗 ≤ Nとなる最大の整数kを求めてください。
制約
- Nは1 ≤ N ≤ 10の18乗を満たす整数である
入力
入力は以下の形式で標準入力から与えられる。
1N出力
答えを整数として出力せよ。
本問題は、AtCoder株式会社で作成された、B - log2(N)問題を参照しております。
Contest中に考えたこと
- N = 1の時は0を返すようにする。
- N != 1の場合は、while文を回す。
- 0 ≤ N - (2のk乗)を満たす場合に、1ループごとにkの値を+1していく。
- 0 ≤ N - (2のk乗)を満たさない場合に、while文を抜ける。
- kの値を出力する。
解答
1# 標準入力を受け付ける。
2# python3系のintには、数字の最大値の上限がないため、bitに関して考える必要はない。
3# python3系のintについて : https://note.nkmk.me/python-int-max-value/
4N = int(input())
5
6# N = 1の時は0を返すようにする。
7if N == 1:
8 print(0)
9else:
10 count = 0
11 # N != 1の場合は、while文を回す。
12 while True:
13 # pow : べき乗を行う関数
14 # powについて : https://docs.python.org/ja/3/library/functions.html#pow
15 if 0 <= (N - pow(2, count)):
16 count = count + 1
17 else:
18 break
19 # -1するのは、breakするときのcount(k)の値が格納されているため。
20 print(count - 1)C -> One More aab aba baa
問題文
文字列Sの各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前からK番目にくる文字列を求めてください。
「各文字を並べ替えて作ることが可能な文字列」とは? : 「文字列Aが文字列Bの各文字を並べ替えて作ることが可能な文字列である」とは、任意の文字が文字列Aと文字列Bに同数含まれるということを指します。 ⏩ 要するに文字列Aが与えられて、文字列Aの各文字を並び替えて、文字列Bや文字列Cを作れるならば、文字列A, 文字列B, 文字列Cは「同数の同じ各文字で形成される」ことを伝えている。
制約
- 1 ≤ 絶対値S ≤ 8
- Sは英小文字のみからなる
- Sの各文字を並べ替えてできる文字列はK種類以上存在する
入力
入力は以下の形式で標準入力から与えられる。
1S K出力
答えを出力せよ。
本問題は、AtCoder株式会社で作成された、C - One More aab aba baa問題を参照しております。
Contest中に考えたこと
- 与えられた文字列を各文字へ分解する。
- 各文字を並び替えて辞書順で文字列を作成するために、各文字の順序を辞書順に並べ替えておく。
- 並び替えたときに生成される文字列が、既に重複している可能性を考える。
- プログラム作成中で終了した。。
解答
1# 文字列の並び替え(順列列挙)を行う関数
2def permutations(start, end=[]):
3 # 文字列が生成された場合
4 if len(start) == 0:
5 arr.append("".join(end))
6 else:
7 for i in range(len(start)):
8 # abcの文字列の場合。
9 # aの文字列を固定して、bc, cbの並び替えを行う。
10 # 次にbの文字列を固定して、ac, caの並び替えを行う。
11 # 最後にcの文字列を固定して、ab, baの並び替えを行う。
12 # 参考 : https://www.delftstack.com/ja/howto/python/how-to-generate-all-permutations-of-a-list-in-python/
13 permutations(start[:i] + start[i+1:], end + start[i:i+1])
14
15# 標準入力を受け付ける。
16S, K = input().split()
17
18# 文字列をlist型へ変更し、各文字1つ1つを格納する。
19# 参考 : https://qiita.com/cress_cc/items/5600be0416a0be72ecfb#perl%E3%81%A8python%E3%81%AE%E6%AF%94%E8%BC%83
20S = list(S)
21
22# 文字列の長さを格納する。
23Slen = len(S)
24
25# 各文字を入れ替えて生成される、文字列を格納する。
26arr = []
27
28# 文字列の(順列列挙)を行う関数
29permutations(S)
30
31# 重複削除を行う。
32# 参考 : https://note.nkmk.me/python-list-unique-duplicate/
33arr = list(set(arr))
34# 文字列を辞書順へ並び替える。
35arr.sort()
36
37# K番目の文字列を出力する。
38print(arr[int(K) - 1])D -> Coprime 2
問題文
長さNの正整数列A=(A1, A2, …,AN)が与えられるので、以下の条件を満たす1以上M以下の整数kを全て求めてください。
全ての1 ≤ i ≤ Nを満たす整数iについて、gcd(Ai, k) = 1である。
制約
- 入力は全て整数
- 1 ≤ N, M ≤ 10の5乗
- 1 ≤ Ai ≤ 10の5乗
入力
入力は以下の形式で標準入力から与えられる。
1N M
2A1 A2 … AN
出力
1行目に、出力する整数の数xを出力せよ。続くx行に、答えとなる整数を小さい方から順に1行に1つずつ出力せよ。
本問題は、AtCoder株式会社で作成された、D - Coprime 2問題を参照しております。
要点
- GCD : 最大公約数。2つ以上の整数について、共通する約数の中でもっとも大きな値。
- 約数 : ある整数を割り切れることができる数。
- Ai = kの場合、Ai = k = 1の場合以外、答えに当てはまらない。 ⏩ Ai, kの値自身が最大公約数になるため。
- Aiの素因数となるk(Aiが8の場合にkが2)は、答えに当てはまらない。 ⏩ 少なくとも素因数の値以上が最大公約数になるため。
- 上述で見つけた素因数の値を2倍, 3倍, ... N倍したkの値は、答えに当てはまらない。 ⏩ 少なくとも素因数の値以上が最大公約数になるため。
解答
1# 標準入力を受け付ける。
2N, M = map(int, input().split())
3A = list(map(int, input().split()))
4
5# AのリストとMの値の最大値を洗い出す。
6# 答えとしてとりうる値を絞るため。
7maxA = max(max(A), M)
8
9# 各index = kの値(答え)とし、kの値(答え)として採用すべきかを(True or False)で表す。
10# 初期値としてTrue(採用すべき)を格納する。
11# ※ indexの0番目, 1番目の値は利用しない。
12k = [True] * (maxA + 1)
13# 素数かどうかを判定するために利用する。
14# ※ indexの0番目, 1番目の値は利用しない。
15isprime = [True] * (maxA + 1)
16# Aの素因数(使えない素数)を格納する。
17# 素因数とは? : Aを整数で割ることのできる素数。
18prime = []
19
20# kの値がAiの値だった場合を考える。
21# k = Aiとなるため、gcd(k, k) = 1の場合のみ、成立する事になる。
22# k = 1以外は、1よりも大きい最大公約数を取得するため、Aの要素は不採用にする。
23for a in A:
24 k[a] = False
25
26# 素数の判定を行う。
27# 素因数となる値を探すため。
28# 2からrangeを回しているのは、indexの0番目, 1番目の値は利用しないため。
29for i in range(2, maxA + 1):
30 # 不採用になる素因数を探すだけなので、素数にならないfor文に関しては、continueを行う。
31 if not isprime[i]:
32 continue
33 # エラトステネスのふるいとは? : https://club.informatix.co.jp/?p=13457
34 for j in range(i * 2, maxA + 1, i):
35 # 素数に当てはまらないものをFalseとする。
36 isprime[j] = False
37 # 先ほど不採用にした値を利用して、素因数になる場合は、不採用にする。
38 # (例) : 先ほど不採用にした値が8の場合、素因数2が不採用に含まれるようになる。
39 k[i] = k[i] and k[j]
40 if not k[i]:
41 prime.append(i)
42
43# 使えない素数pに対して、 pの倍数をかけて不採用にする。
44for p in prime:
45 for j in range(p * 2, M + 1, p):
46 k[j] = k[j] and k[p]
47
48# 使える数をansに入れる。
49# 1は必ず答えになるので初期化しておく。
50ans = [1]
51for i in range(2, M + 1):
52 if k[i]:
53 ans.append(i)
54
55# 出力
56print(len(ans))
57for i in ans:
58 print(i)2021年8月21日時点のレート画像
参考文献
- レーティングとは?
- AtCoderのプログラミングコンテストのルール
- AtCoder株式会社について
- pow関数について
- python3系のintについて
- 約数とは?
- 最大公約数とは?
- 素因数とは?
- エラトステネスのふるいとは?
- Atcoder 215に関するコードまとめ