モノグサプログラミングコンテスト2022(ABC249) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
モノグサ株式会社について
本コンテストはモノグサ株式会社様が主催されています。
モノグサ株式会社様は「解いて憶える」記憶アプリ『Monoxer(モノグサ)』の開発と運営等をされています。
興味のある方は採用ページを御覧ください。
A - Jogging
ABCのA問題は10回に1回くらいやたら難しい問題が出ます。
今回がそのやたら難しい回なので、今回解けなかった人も落ち込まずに競技プログラミングを続けてください。
高橋くんと青木くんがどこまで進めるか実際にシミュレーションしてみましょう。
残り時間をtimeとしてtimeが0以下になるまで進んでみます。
例として以下の入力を考えます。
A：3
B：4
C：5
X：10
つまり高橋くんは「3秒間秒速4メートルで歩き、5秒間休む」を繰り返し、時間が10秒の場合です。
3≤10(=残り時間)なので最初の3秒はフルに使って3*4=12メートル進むことができます。
そこから5秒休みます。
合計で3+5=8秒使い、残りは10-8=2秒です。
距離：12メートル
残り時間：2秒
まだ時間があるので進めます
残り時間2秒で2<3なので2秒だけ進んで、2*4=8メートル追加します。
進んだ合計距離は12+8=20メートルです。
これで残り時間は0になるので終了です。
距離：20メートル
残り時間：0秒
よって高橋くんは20メートル進めます。
一般化しましょう。以下の手順で高橋くんの進んだ距離を確認できます。
・0<(残り時間)である間
・A≤(残り時間)ならば
(高橋くんの進んだ距離)にA*Bをプラス
(残り時間)からA+Cをマイナス
・(残り時間)<Aならば
(高橋くんの進んだ距離)に(残り時間)*Bをプラス
(残り時間)=0とする
同様にして青木くんの進んだ距離も確認し、比較すればOKです。
「・0<(残り時間)である間」はwhileを使って
while 0<time:
と書きます。
答えが「Takahashi」「Aoki」「Draw」のどれになるかは進んだ距離のパターンについてifを使って確認します。
例えば「Takahashi」を出力するときは文字列であるため、
print("Takahashi")
と「""」(ダブルクオーテーション)が必要であることに注意してください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
A,B,C,D,E,F,X=map(int,input().split())
# 残り時間
Time=X
# 高橋くんの進んだ距離
Taka=0
# ・0<(残り時間)である間
while 0<Time:
# ・A≤(残り時間)ならば
if A<=Time:
# (高橋くんの進んだ距離)にA*Bをプラス
Taka+=A*B
# (残り時間)からA+Cをマイナス
Time-=A+C
# ・(残り時間)<Aならば
else:
# (高橋くんの進んだ距離)に(残り時間)*Bをプラス
Taka+=Time*B
# (残り時間)=0とする
Time=0
# 残り時間
Time=X
# 青木くんの進んだ距離
Aoki=0
# ・0<(残り時間)である間
while 0<Time:
# ・D≤(残り時間)ならば
if D<=Time:
# (青木くんの進んだ距離)にD*Eをプラス
Aoki+=D*E
# (残り時間)からD+Fをマイナス
Time-=D+F
# ・(残り時間)<Dならば
else:
# (青木くんの進んだ距離)に(残り時間)*Eをプラス
Aoki+=Time*E
# (残り時間)=0とする
Time=0
# (青木くんが進んだ距離)<(高橋くんが進んだ距離)の場合
if Aoki<Taka:
# 「Takahashi」を出力
print("Takahashi")
# (高橋くんが進んだ距離)<(青木くんが進んだ距離)の場合
elif Taka<Aoki:
# 「Aoki」を出力
print("Aoki")
# (青木くんが進んだ距離)=(高橋くんが進んだ距離)の場合
else:
# 「Draw」を出力
print("Draw")
B - Perfect String
Sがそれぞれの条件を満たしているか順に確認します。
・英大文字が文字列の中に現れる
・英小文字が文字列の中に現れる
ある文字が大文字か？はisupperで確認します。
(文字).isupper()と書くと、(文字)が大文字の場合「True」が返ってきます。
Sの文字を1文字ずつxに入れるときはfor x in S:と書けます。
よってSのそれぞれの文字について大文字か？は以下のように書けば確認できます。
for x in S:
if x.isupper()==True:
「大文字が存在するか？」を確認する変数を用意しておき、大文字があればTrueにする、という形にすればOKです。
小文字も同様にします。(大文字でない=小文字)
・全ての文字が相異なる
これは全ての文字の組について同じ文字がないか？を確認すれば良いです。
以下、Sの文字数をNとします。
Sの左端を0文字目、1個左を1文字目,...として、以下のように組を作って確認していきます。
(Sの0文字目)と(Sの1文字目)
(Sの0文字目)と(Sの2文字目)
(Sの0文字目)と(Sの3文字目)
...
(Sの1文字目)と(Sの2文字目)
(Sの1文字目)と(Sの3文字目)
...
(Sのi文字目)と(Sのk文字目)
...
(Sの(N-2)文字目)と(Sの(N-1)文字目)
以下のように2重ループを書くと順番に組を作れます。
for i in range(N):
for k in range(i+1,N):
これで以下の順に代入しながら処理ができます。
(i,k)
(0,1)
(0,2)
(0,3)
...
(1,2)
(1,3)
...
(N-2,N-1)
非常によく使う書き方なので覚えましょう。
大文字小文字同様、「重複が存在するか？」を管理する変数を作っておき、重複があればTrueにします。
最後に「大文字がある」「小文字がある」「重複がない」場合に「Yes」、そうでない場合に「No」を出力して終わりです。
【提出】
# 入力の受け取り
S=input()
# 「大文字が存在するか？」を管理する変数
OmoziExist=False
# 「小文字が存在するか？」を管理する変数
KomoziExist=False
# Sの各文字=x
for x in S:
# xが大文字なら
if x.isupper()==True:
# 「大文字が存在するか？」をTrueに
OmoziExist=True
# そうでない場合(xが小文字)
else:
# 「小文字が存在するか？」をTrueに
KomoziExist=True
# 「重複が存在するか？」を管理する変数
Tyohuku=False
# Sの文字数
N=len(S)
# i=0~(N-1)
for i in range(N):
# k=(i+1)~(N-1)
for k in range(i+1,N):
# (Sのi文字目)=(Sのk文字目)
if S[i]==S[k]:
# 「重複が存在するか？」をTrueに
Tyohuku=True
# 「大文字がある」「小文字がある」「重複がない」
if OmoziExist==True and KomoziExist==True and Tyohuku==False:
# 「Yes」を出力
print("Yes")
# そうでない場合
else:
# 「No」を出力
print("No")
C - Just K
なにやら問題文がややこしいですね。こういうときはとりあえず入力例1と出力例1を見てみましょう。
abi
bc
acg
を選んだ場合、a,b,cがちょうど2個の文字列に含まれます、とのことです。
各文字がいくつの文字列に含まれるか、個数を数えてみましょう。
a：2個(abi,acg)
b：2個(abi,bc)
c：2個(bc,acg)
g：1個(acg)
i：1個(abi)
確かにa,b,cのみちょうどk=2個の文字列に含まれています。
Nは最大で15個です。文字列の選び方はそれぞれについて「選ぶ」「選ばない」の2択です。
よって選び方のパターン数は「全て選ばない」を含め2^15=32768通りしかありません。
これなら全部の選び方を試してもTLEしなさそうです。
どの文字列を選ぶかはbit全探索を使って決めていきます。
bit全探索がよくわからない人は以下を確認してください。
Bit全探索について
取る、取らない など2択を全パターン試す場合に使用します。
例えば6個の選択についてならば6桁の2進数を対応させてそれぞれを確認します。
2進数が101001ならば
0個目(右から1桁目)=1→取る
1個目(右から2桁目)=0→取らない
2個目(右から3桁目)=0→取らない
3個目(右から4桁目)=1→取る
4個目(右から5桁目)=0→取らない
5個目(右から6桁目)=1→取る
というように対応付けが行なえます。
2進数の(000000)~(111111)(N桁)までループを回すときは以下のように書くと良いです。
for bitnum in range(1<<N):
1<<Nはシフト演算で、1を左にN個シフト=2進数の100...0(0がN個)=2^Nを表します。
上記のように書くことでbitnum=(000000)~(111111)(N桁)と代入して順に確認ができます。
右からx桁目(右端は0桁目)が0か1かは以下のように書くことで確認できます。
if bitnum>>x & 1==1:
bitnumを右にxシフトさせたあと1とアンド演算しています。
結果が
0ならばx桁目は0
1ならばx桁目は1
であることがわかります。
※if bitnum>>x and 1==1: と書かないよう注意！！
例えば101001(=10進数の41)の右から3桁目(右から4つ目)を確認する場合
101001>>3=101であり、
101 & 1 =1
となりますから、右から3桁目は1とわかります。
bit全探索の解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。
シフト演算、アンド演算についてより詳細に解説しています。
本文では各文字列について
「0」→選ばない
「1」→選ぶ
として全パターンの選び方を作っていきます。
文字を選んだあとは各文字についていくつの文字列に含まれているか確認していきましょう。
a,b,c,...,zについて確認していくので、まずはこれらの文字をforで作ります。
chr(文字コード)と書くことで対応した文字を作ることができます。
文字コードは「a」=chr(97),「b」=chr(98)、...,「z」=chr(122)と連番になっているので、以下のように書くことでAlphabetに順に英小文字を作ることができます。
for code in range(97,123):
Alphabet=chr(code)
作ったAphabetが選ばれた文字列の中にいくつ含まれるか確認し、ちょうどk個の文字列に含まれるならカウントします。
【提出】
# 入力の受け取り
N,K=map(int,input().split())
# Sを格納するリスト
S_list=[]
# i=0~(N-1)
for i in range(N):
# 入力の受け取り
S=input()
# リストへ格納
S_list.append(S)
# 答え
ans=0
# bitnum=(000...0)~(111...1)(2進数)
for bitnum in range(1<<N):
# 暫定答え
ans_tmp=0
# 選ばれた文字列の格納リスト
Choosed=[]
# shift=0~(N-1)
for shift in range(N):
# (bitnumをshift個右シフト) & 1 =1ならば
if bitnum>>shift & 1:
# 文字列を選ぶ
# ⇔(Shift)番目の文字列をChoosedに格納
Choosed.append(S_list[shift])
# code=97~122
for code in range(97,123):
# Alphabet=「a」「b」...「z」
Alphabet=chr(code)
# Alphabetが含まれる文字列の数をカウント
InCount=0
# T=Choosedに含まれる文字列を順に格納
for T in Choosed:
# TにAlphabetが含まれるなら
if Alphabet in T:
# カウントする
InCount+=1
# カウント=Kならば
if InCount==K:
# Alphabetが選んだ文字列のうちちょうどK個に含まれる
ans_tmp+=1
# ans_tmpのほうが大きければansを更新
ans=max(ans_tmp,ans)
# 答えを出力
print(ans)
D - Index Trio
式変形すると
Ai=Aj*Akとなります。
例として以下の入力を考えます。
A：6 4 2 2 2 3 3
まずAに1,2,3,...がいくつ含まれるか確認しましょう。
「1」：0個
「2」：3個
「3」：2個
「4」：1個
「5」：0個
「6」：1個
次にA1,A2,A3,...について順に2つの積で表した形を考えます。
A1：6
6は1*6と2*3の2つが考えられます。
1*6は「1」が0個なので作りようがありません。
2*3は2が3個、3が2個あるので3*2=6通り作ることができます。
具体的には以下の6通りです。
(Ai,Aj,Ak)=(A1,A3,A6),(A1,A3,A7),(A1,A4,A6),(A1,A4,A7),(A1,A5,A6),(A1,A5,A7)
が、6＝3*2も考えられるので6通り*2=12通りとなります。
((A1,A3,A6)があるなら(A1,A6,A3)もOK→それぞれのAj,Akをひっくり返して2倍になる)
A2：4
4は1*4と2*2の2つが考えられます。
1*4は「1」が0個なので作りようがありません。
2*2は2が3個あるので3*3=9通り作ることができます。
具体的には以下の9通りです。
(Ai,Aj,Ak)=(A2,A3,A3),(A2,A3,A4),(A2,A3,A5),(A2,A4,A3),(A2,A4,A4),(A2,A4,A5),(A2,A5,A3),(A2,A5,A4),(A2,A5,A5)
この場合はAj,Akをひっくり返して、という手は使えないので2倍にはなりません。
各Aiについて2つの積に分解するにはAj=1,2,3,...で試し割りしていきます。
割り切れたらAk=Ai//Ajとできます。
Ajは1~√Aiまでの範囲で試し割りすればOKです。
例えば16ならばAj=1,2,3,4まで試し割りします。
Aj=1：1*16
Aj=2：2*8
Aj=3：割り切れない
Aj=4：4*4
これ以降、Aj=5,6,7,...については上記と順序が逆になるだけで試す必要がないです。
(例えばAj=8のとき8*2になりますが、2*8の形ですでに計算しているから不要ということです)
Aiを2つの積に分解する計算量は√Nとなり、これをN回行うので全体の計算量はO(N√N)となります。
最大で10^7回程度の計算量となり、pypyなら間に合います。
【提出】
# pypyで提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# 1,2,3,..がいくつ含まれるかカウントするリスト
count=[0]*10**6
# i=0~(N-1)
for i in range(N):
# 1,2,3,..がいくつ含まれるかカウント
count[A[i]]+=1
# 答え
ans=0
# i=0~(N-1)
for i in range(N):
# Aj=1,2,3,...で試し割り
Aj=1
# Aj≤√A[i]⇔Aj^2≤A[i]の間
while Aj**2<=A[i]:
# 割り切れたら
if A[i]%Aj==0:
# Akを確認
Ak=A[i]//Aj
# Aj=Akならば
if Aj==Ak:
# (Ajの個数)*(Akの個数)
ans+=count[Aj]*count[Ak]
# Aj≠Akならば
else:
# (Ajの個数)*(Akの個数)*2
# AjとAkを入れ替えできるため2倍する
ans+=count[Aj]*count[Ak]*2
# 次のAjへ
Aj+=1
# 答えを出力
print(ans)
【広告】
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/gp/product/B09C3TPQYV/
【booth(pdf)】
https://sano192.booth.pm/items/3179185
1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf
『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV
【booth(pdf)】
https://booth.pm/ja/items/3698647
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/
【booth(pdf)】
https://sano192.booth.pm/items/3698668
『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』
ABC226~250、ARC129~139 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC129~139の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS
【booth(pdf)】
https://sano192.booth.pm/items/4025713
ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF
【booth(pdf)】
https://sano192.booth.pm/items/4025737
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！ 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb
【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW
【booth(pdf】
https://sano192.booth.pm/items/3785312