ABC215(AtCoder Beginner Contest 215) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下
A - Your First Judge
入力を受け取り、"Hello,World!"と一致するかをif文で判定すればよいです。
pythonでは等しいという条件について「=」ではなく「==」と2つイコールを書くことに注意してください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
S=input()
# Hello,World!に等しいなら
if S=="Hello,World!":
# ACを出力
print("AC")
# そうでないならば
else:
# WAを出力
print("WA")
B - log2(N)
2^kは2,4,8,16,32,...とすごい速さで大きくなります。
そのためk=0,1,2,3,...の場合の2^kをひたすら計算し、Nを超えた直前のkを出力すれば良いです。
なおNは最大で10^18ですが10^18<2^60なのでkは最大でも60まで計算すればよいです。
が、ギリギリを狙うとなにか勘違いがあったときに失敗しやすいのでてきとうに大きなところまで探索するのがよいです。(下記のコードではk=999まで探索しています)
別のやりかたとして不等式を直接計算した人もいると思います。
\\2^k \leq N
\\k \leq log_2N
数学的には正しいのですがlogの計算には少数が発生します。コンピュータで少数を計算するときは誤差が発生する場合があり、色々と面倒です。整数だけで計算できるならそちらを意識的に使うようにしましょう。
【提出】
# 入力の受け取り
N=int(input())
# k=0~999まで
for k in range(1000):
# もしN<2^kならば
if N<2**k:
# 一つ前のkが答え
print(k-1)
# 終了
exit()
C - One More aab aba baa
一見難しそうですが、制約が1≤|S|≤8と非常に小さいです。
Sの各文字を並び替えてできる文字というのは最大でも8文字の並び変え、すなわち8!=40320個しかありません。
であれば全部のパターンを作り、並び替え、K番目の文字を出力してしまえば終わりです。
どうやって全パターンを作るかですが、itertoolsを使います。
今欲しいのは例えばSが3文字(abc)の場合
Sの0文字目+Sの1文字目+Sの2文字目：abc
Sの0文字目+Sの2文字目+Sの1文字目：acb
Sの1文字目+Sの0文字目+Sの2文字目：bac
Sの1文字目+Sの2文字目+Sの0文字目：bca
Sの2文字目+Sの0文字目+Sの1文字目：cab
Sの2文字目+Sの1文字目+Sの0文字目：cba
この6通りとなります。
itertoolsはpythonの標準ライブラリで、このように順列や組み合わせの全パターンを列挙するときに便利なツールです。
と言われてもよくわからないと思いますから、以下のコードを実行してみてください。
import itertools
for seq in itertools.permutations(range(3)):
print(seq)
【出力結果】
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)
なんといい感じに順列を作ってくれています。
あとはこれを使ってSの○文字目+Sの△文字目+Sの×文字目...と作っていけばよいです。
ただし作った文字が重複しないように、リストではなくセットに入れるようにしてください。
(リストは重複OK、セットは重複NGです)
その後リストに変換してソートすれば後は出力するだけです。
【提出】
# 入力の受け取り(Kも文字列として)
S,K=map(str, input().split())
# Kを整数に変換
K=int(K)
# 作れる文字を格納するセット(リストだと重複するものも入ってしまうためセットを使う)
S_set=set()
# itertoolsをインポート
import itertools
# seq=(0,1,2),(0, 2, 1),(1, 0, 2),(1, 2, 0),...
for seq in itertools.permutations(range(len(S))):
# 作った文字列を記録する変数
S_tmp=""
# seqを使って文字を作成
# 例：seq=(2,0,1)ならS_tmp=Sの2文字目+Sの0文字目+Sの1文字目
for i in seq:
S_tmp+=S[i]
# できた文字をS_setに格納(setへの追加はappendではなくaddであることに注意)
S_set.add(S_tmp)
# ソートするためにリストへ変換
S_list=list(S_set)
# 辞書順にソート
S_list.sort()
# K-1番目の要素を出力
print(S_list[K-1])
itertoolsは他にも組み合わせや直積などを作れます。
以下をメモしておいてコンテスト中にコピペできるようにしておきましょう。
import itertools
# 順列
#(1,2,3),(1,3,2),(2,1,3),(2,3,1),...,(3,2,1)
for seq in itertools.permutations(range(1,4)):
# 重複なしの組み合わせ
# (1,2,3),(1,2,4),...,(7,8,9)
for seq in itertools.combinations(range(1,10),3):
# 重複ありの組み合わせ
#(1,1,1),(1,1,2),...,(9,9,9)
for seq in itertools.combinations_with_replacement(range(1,10),3):
# 直積
#(1,1),(1,2),(1,3),(2,1),(2,2),...,(3,3)
for seq in itertools.product(range(1,4),range(1,4)):
D - Coprime 2
Aの各要素の素因数分解→得られた素因数を使ってエラトステネスの篩(もどき)
という方法で解くことができます。
具体的な手順は以下です。
(1)Aの各要素を素因数分解し、どの素数が含まれるか確認
(2)1～Mまで答えの候補を用意
(3)(1)で得られた素因数の倍数を全て答え候補から消す
(4)残った答え候補を出力
入力例1を使って考えます。
A：6 1 5
まずこれらを全て素因数分解します。
6=2*3
1=1
5=5
得られた素因数は
2,3,5
の3つです。
ということはまず2,3,5は答えにならないことがわかると思います。
さらに2の倍数、3の倍数、5の倍数も答えになりません。
(例えば9(=3の倍数)はgcd(6,9)=3となるため答えにならないです)
つまり1～Mまでの整数について、2の倍数、3の倍数、5の倍数を順に消していき、消されずに残ったものが答えというわけです。
(同じようなやり方で素数を探す方法を『エラトステネスの篩』といいます)
ゆえにこの問題を解くために必要なのは以下です。
(1)素因数分解の実装と計算量の把握
(2)エラトステネスの篩の実装と計算量の把握
(1)素因数分解の実装と計算量の把握
素因数分解は1から順に試し割りをし、割り切れたものを素因数として記録、という方法を使います。
xを素因数分解する場合は1～√xまでの試し割りを行うため、計算量はO(√x)です。
「例」x=1260を素因数分解する場合
i=2<=√1260なので試し割りを開始。
i=2：1260/2＝630(素因数に2を追加)
i=2<=√630なので試し割りを続ける。
i=2：630/2＝315(素因数に2を追加)
i=2<=√315なので試し割りを続ける。
i=2：315は2で割れない→次のi=3へ。
i=3<=√315なので試し割りを続ける。
i=3：315/3＝105(素因数に3を追加)
i=3<=√105なので試し割りを続ける。
i=3：105/3＝35(素因数に3を追加)
i=3<=√35なので試し割りを続ける。
i=3：35は3で割れない→次のi=4へ。
i=4<=√35なので試し割りを続ける。
i=4：35は4で割れない→次のi=5へ。
i=5<=√35なので試し割りを続ける。
i=5：35/5＝7(素因数に5を追加)
√7=2.64...<i=5となるため、ここで試し割りが終わります。
最後に残った7を素因数として追加します。
結果：1260=22335*7
コードにすると以下のようになります。
試し割りはi<√xの間行うのですが、ルートの計算は少数で誤差が出てしまうのでi*i<xと変換しています。
# 素因数分解
def prime_factorize(x):
# もしx=1ならば
if x==1:
# 1を返す
return [1]
# 素因数を格納するリスト
prime_list=[]
# i=2,3,4,...で試し割り
i=2
# i<=√xすなわちi*i<=xの範囲で試し割り
while i*i<=x:
# もしiで割り切れたら
if x%i==0:
# iを素因数に追加
prime_list.append(i)
# xをiで割る
x//=i
# iで割り切れなかったら
else:
# 次のiへ
i+=1
# 試し割りが終わった時xが1でなければ
if x!=1:
# 素因数にxを追加
prime_list.append(x)
# 素因数のリストを返す
return prime_list
なぜ試し割りが√xまでで良いのか、については別に知らなくても困ることはないのですが一応説明を記載します。ここは興味がなければ飛ばしても構いません。
【試し割りが√xまでで良い理由】
背理法を使って説明する。
i=1,2,3,...と試し割りを行い続け、√Nを超えたところで割り切れる数xが現れたとする。すなわち
√N<x
Nはxで割り切れたわけだから
N=x*(何か)
と表せる。
そしてこの(何か)は少なくとも√Nよりは大きくなければならない。ここに至るまでのi=1,2,3,...,√Nで
試し割りをしているからだ。
ゆえに
√N<(何か)
以上より
√N<x...(1)
√N<(何か)...(2)
N=x*(何か)...(3)
となることがわかった。
しかし(1)、(2)の両辺をそれぞれ掛け算すると
√N√N<x(何か)
N<x*(何か)
となり、これは(3)に矛盾する。ゆえにxはそもそも存在しない。
(2)エラトステネスの篩(もどき)の実装と計算量の把握
素因数を得られたらその倍数を全て答え候補から外していきます。
Aの要素を全て素因数分解した結果、2,3,7,11があったとします。
まず答え候補を1～Mまで用意し、
2の倍数：2,4,6,...
3の倍数：3,6,9...
7の倍数：7,14,21,...
11の倍数：11,22,33...
を順に答え候補から外していくというわけです。
計算量はどうなるか、ですがこれは最大でもO(MlogM)となります。
(上記例のケースではM/2+M/3+7/M+M/11となります)
M/2+M/3+M/4+...<MlogMとなる、という有名な話があり、そのため計算量はO(MlogM)以下となります。
詳しく知りたい人は「調和級数 log」とかでググると出てきます。
※数学警察のために言っておくと上記の式は厳密には間違いですが、結論は変わらないので気にしなくていいです。
以上を踏まえ、
(1)素因数分解：O(N√N)
(2)エラトステネスの篩(もどき)：O(MlogM)
で、全体の計算量は(N√N+MlogM)となりました。
1<=N,M<=10^5なのでTLEしないか心配ですね。実際pythonで提出するとTLEします。
こういった場合は言語にpypyを選択して提出してください。pypyは計算内容によりますが2sec以内に10^8回程度まで計算可能です。
【提出】
# 提出はpypyで行う
# 素因数分解
def prime_factorize(x):
# もしx=1ならば
if x==1:
# 1を返す
return [1]
# 素因数を格納するリスト
prime_list=[]
# i=2,3,4,...で試し割り
i=2
# i<=√xすなわちi*i<=xの範囲で試し割り
while i*i<=x:
# もしiで割り切れたら
if x%i==0:
# iを素因数に追加
prime_list.append(i)
# xをiで割る
x//=i
# iで割り切れなかったら
else:
# 次のiへ
i+=1
# 試し割りが終わった時xが1でなければ
if x!=1:
# 素因数にxを追加
prime_list.append(x)
# 素因数のリストを返す
return prime_list
# 入力の受け取り
N,M=map(int, input().split())
A=list(map(int, input().split()))
# 素因数を格納するセット(重複した素数をいれないため、リストでなくセットにする)
prime_set=set()
# Aの各要素について
for x in A:
# もし1ならば
if x==1:
# 次の要素へ
continue
# prime_x=xの素因数リスト
prime_x=prime_factorize(x)
# xの素因数をprime_setに追加
for p in prime_x:
prime_set.add(p)
# ans_judge[x]=1なら答え、=0なら答えでない
ans_judge=[1]*(M+1)
# prime_set=Aの要素が持つ素数(p)について
for p in prime_set:
# p*1,p*2,p*3,...,p*k,...は答えでない→ans_judge[p*k]=0とする
# p*kがMを超えるまで
k=1
while p*k<=M:
ans_judge[p*k]=0
k+=1
# 答えの格納用リスト
ans=[]
# 1～Mまで
for i in range(1,M+1):
# ans_judge[i]=1ならiは答え
if ans_judge[i]==1:
ans.append(i)
# 答えの個数を出力
print(len(ans))
# 答えを出力
for i in ans:
print(i)
【広告】
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
1～24問目まではサンプルとして無料公開しています
『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！ 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
【kindle】
【booth(pdf】