ABC220(AtCoder Beginner Contest 220) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
A - Find Multiple
今回のA問題は「やや難」です。
普段のA問題はもっと簡単なので、今回A問題が解けなかった人も落ち込まずに競技プログラミングを続けてください。
公式解説の方法でも解けますが思いつくのが難しいです。
A～Bまでの数について順に「Cの倍数か」=「Cで割った余りが0か」を確認すればOKです。
A～Bまで確認するときは以下のように書きます。
for x in range(A,B+1):
上記のように書くことでx=A～Bまで順に処理ができます。
range(A,B)ではなく、range(A,B+1)であることに注意してください。
xをCで割った余りは
x%C
で確認できます。
これが0かどうか、if文で判定します。
x%C=0ならばxを出力して終了します。
プログラムを途中で終了するときは
exit()
と書きます。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
A,B,C=map(int, input().split())
# x=A～Bまで
for x in range(A,B+1):
# xがCの倍数=xをCで割った余りが0の場合
if x%C==0:
# xを出力
print(x)
# プログラムを終了
exit()
# A~BまででCの倍数がなければここに到達する
# -1を出力
print(-1)
B - Base K
K進数で書かれた数を10進数へ変換するには
右からi桁目×Kのi乗
を計算して足し算します。
例として3進法の「201」を10進数へ変換しましょう。
右から0桁目=1：1×3^0=1×1=1
右から1桁目=0：0×3^1=0×3=0
右から2桁目=2：2×3^2=2×9=18
よって1+0+18=19となります。
なぜこのように計算できるかは「3進数の定義より」としか言いようがないのですが、詳しく知りたい人は以下のページが比較的わかりやすいかと思います。
理屈がしっかりわかっていなくてもこの問題を解くことはできますので、興味がある人だけ読んでください。
実装についてはK進数→10進数へ変換する関数を作ると楽です。
関数の内容は以下です。
(1)x(文字列)を受け取る
(2)右端から各桁の数を確認するため、反転する
(x[::-1]と書くことで反転できます)
(3)xの右から順にi桁目×(k^i)を計算して足す
(4)結果を返す
関数ができたらA,Bを10進数へ変換して掛け算するだけです。
【提出】
# 入力の受け取り
K=int(input())
# A,Bは文字列として受け取り
A,B=map(str, input().split())
# 10進法へ変換する関数
def convert_ten(x):
# xを反転
x=x[::-1]
# 結果の格納用
result=0
# i=0～(xの桁数)
for i in range(len(x)):
# xのi桁目*(K^i) intでxのi桁目を整数へ変換
result+=int(x[i])*(K**i)
# 結果を返す
return result
# A,Bを10進法へ変換
A_ten=convert_ten(A)
B_ten=convert_ten(B)
# 答えの出力
print(A_ten*B_ten)
C - Long Sequence
まず「Aの塊が最低いくつ必要か」考えましょう。
これは「X÷(Aの合計)の商」で計算できます。
さらに(「X÷(Aの合計)の商」)個Aを足した合計は(Aの合計)×「X÷(Aの合計)の商」となることがわかります。
Aの中身はN個なので、BのN×(「X÷(Aの合計)の商」)項目までの合計が(Aの合計)×「X÷(Aの合計)の商」となることがわかるわけです。
あとはXを超えるまでAの値を順に足していけばよいです。
具体例で考えましょう。
「例」
N：3
A：1 2 3
X：20
Aの合計は1+2+3=6です
「X÷(Aの合計)の商」=20÷6=3となりますから、まずAの塊が3つ必要であることがわかります。
A3つの合計は(1+2+3)+(1+2+3)+(1+2+3)=18です。
ここまでの項数はN×「X÷(Aの合計)の商」=3×3=9です。つまりBの9項目までの和が18です。
あとはXを超えるまでAの要素を順に足し算していくだけです。
Bの10項目(+A[0])：18+1=19
Bの11項目(+A[1])：19+2=21
11項目でX(=20)を超えたので、答えは11となります。
【提出】
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
X=int(input())
# Aの合計
A_sum=sum(A)
# XをA_sumで割った商
syou=X//A_sum
# k：N×商
k=N*syou
# B_sum：Aの合計×商
B_sum=A_sum*syou
# i=0~N-1まで
for i in range(N):
# B_sumにA[i]を足す
B_sum+=A[i]
# kにプラス1
k+=1
# X<B_sumになったら
if X<B_sum:
# 答えを出力
print(k)
# 終了
exit()
D - FG operation
それぞれの操作が終わった時、左端の数として0~9がいくつありうるか管理します。
具体例で説明します。
N：5
A：0 1 2 3 4
まず左端にある数の個数を管理する配列を作ります。
count=[0,0,0,0,0,0,0,0,0,0]
最初は左端に0がひとつあります。ゆえにcount[0]は1です。
count=[1,0,0,0,0,0,0,0,0,0]
左端からの2つ、x=A[0]=0とy=A[1]=1でそれぞれ足し算、掛け算を行います。
(x+y)%10=(0+1)%10=1
(x×y)%10=(0×1)%10=0
これでA[0]とA[1]に関する操作の終了時点で左端にありうるのは1が1つ、0が1つであることがわかります。これをまたcountに記録します。
count=[1,1,0,0,0,0,0,0,0,0]
次にy=A[2]=2としてまた操作を行います。
xは左端の数なので、左端にありうる数の数をcountから確認します。xとしてありうるのは
0が1個
1が1個
です。
x=0の場合
(x+y)%10=(0+2)%10=2
(x×y)%10=(0×2)%10=0
x=1の場合
(x+y)%10=(1+2)%10=3
(x×y)%10=(1×2)%10=2
ゆえにA[2]までの操作終了時点で左端にありうるのは
0が1個
2が2個
3が1個
です。countに記録します。
count=[1,0,2,1,0,0,0,0,0,0]
y=A[3]=3としてまた操作を行います。
例によってx、つまり左端にありうる数の数をcountから確認します。
xとしてありうるのは
0が1個
2が2個
3が1個
です。
x=0の場合
(x+y)%10=(0+3)%10=3
(x×y)%10=(0×3)%10=0
x=2の場合
(x+y)%10=(2+3)%10=5
(x×y)%10=(2×3)%10=6
x=3の場合
(x+y)%10=(3+3)%10=6
(x×y)%10=(3×3)%10=9
気をつけるべきなのはx=2のパターンが「2個」存在することです。
x=2の場合からは5,6が出ていますがこれは2個分として数えます。
ゆえにA[3]までの操作終了時点で左端にありうるのは
0が1個
3が1個
5が2個(1×2)
6が3個(1×2+1)
9が1個
となります。
またcountに記録します。
count=[1,0,0,1,0,2,3,0,0,1]
このように左端にありうる数を数えていけば最終的にcountが答えになります。
実装ではx=0~9とy=A[i]の計算結果を確認し、count[x]の個数だけ左端にありうる数として数えるという操作を繰り返し行えば良いです。
【提出】
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# 余りの定義
mod=998244353
# 左端に0～9がいくつあるかカウントする配列
count=[0]*10
# A[0]が1個ある
count[A[0]]=1
# i=1~N-1まで
for i in range(1,N):
# 新しいカウント用配列
new_count=[0]*10
# y=0～9まで
for x in range(10):
y=A[i]
# x+yの結果
plus=(x+y)%10
# x*yの結果
times=(x*y)%10
# count[x]の個数だけ新しいカウントに追加
new_count[plus]+=count[x]
new_count[times]+=count[x]
# 余りを取る
new_count[plus]%=mod
new_count[times]%=mod
# countに更新
count=new_count
# 答えの出力
for x in count:
print(x)
【広告】
『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】