サイシードプログラミングコンテスト2021 A～D問題の解説記事です。
(AtCoder Beginner Contest 219)
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
株式会社サイシード様について
このプログラミングコンテストは株式会社サイシード様が主催されています。
詳しくは動画をご覧ください。
とりあえずみんな51秒までは見て!!
A - AtCoder Quiz 2
入力を受け取り、入力の内容によって条件分岐し、答えを出力します。
0点以上40点未満：40-X
40点以上70点未満：70-X
70点以上90点未満：90-X
90点以上：エキスパート
「expert」を出力するときは文字列の出力ですから
print(expert)
ではなく
print("expert")
としなければならないことに注意してください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
X=int(input())
# 初級の場合
if 0<=X<40:
# 40-Xを出力
print(40-X)
# 中級の場合
elif 40<=X<70:
# 70-Xを出力
print(70-X)
# 上級の場合
elif 70<=X<90:
# 90-Xを出力
print(90-X)
# エキスパートの場合
else:
# "expert"を出力
print("expert")
B - Maritozzo
Tの文字それぞれについて
1→S1
2→S2
3→S3
と変換するような関数を作れば解けます。
プログラミングにおける関数がわからない、pythonで関数を作る方法がわからないという人は以下のサイトを参考にしてください。
【提出】
# 入力の受け取り
S1=input()
S2=input()
S3=input()
T=input()
# Tのi文字目→S1,S2,S3へ変換する関数
def convert(t):
# i文字目が1ならば
if t=="1":
# S1を返す
return S1
# i文字目が2ならば
elif t=="2":
# S2を返す
return S2
# i文字目が3ならば
elif t=="3":
# S3を返す
return S3
# 答えを格納する変数
ans=""
# i=0~(Tの長さ-1)
for i in range(len(T)):
# 変換後の文字列を末尾へ連結
ans+=convert(T[i])
# 答えの出力
print(ans)
C - Neo-lexicographic Ordering
pythonでは通常のアルファベット順でのソートは簡単に行うことができます。
一度通常のアルファベットへ変換し、ソートしてから元に戻す方法で解くことができます。
例として入力例1の場合
X：bacdefghijklmnopqrstuvwxzy
となっています。
新しいアルファベット→通常のアルファベット
と変換するよう連想配列(辞書)を作ります。(conv_letter)
また、同時に逆向きへ変換できるような連想配列(辞書)も作ります。(inv_letter)
※連想配列がわからない人は以下のサイトを参考にしてください。
【例】入力例1のconv_letter
b→a
a→b
c→c
d→d
...
y→z
それぞれの辞書を使って
通常のアルファベット→新しいアルファベットと変換する関数(conv_name)
新しいアルファベット→通常のアルファベットと変換する関数(inv_name)
を関数としてつくれば実装が楽です。
実装ではchr関数を使っています。
chr関数をよく知らない人は以下を読んでください。
chr関数について
コンピュータで扱う文字には文字コードという番号がついており、pythonでは
文字コード→文字
への変換ができるchrという関数があります。
chr(文字コード番号)=文字
例えば『a』の文字コードは97なので
chr(97)="a"
となります。
a,b,c,...の文字コードは97,98.99,...と連番になっているため、chr(97)="a",chr(98)="b",chr(99)="c",...となります。
【提出】
# 入力の受け取り
X=input()
N=int(input())
# 新しいアルファベット→通常のアルファベット変換(convert)辞書
conv_letter=dict()
# 通常のアルファベット変換→新しいアルファベット(inverse convert)辞書
inv_letter=dict()
# それぞれの文字について変換辞書を作成
for i in range(len(X)):
# chr(97)="a"
# chr(98)="b"
# ...
# Xのi文字目→chr(i+97)
conv_letter[X[i]]=chr(i+97)
# chr(i+97)→Xのi文字目
inv_letter[chr(i+97)]=X[i]
# Sを通常のアルファベットへ変換する関数
def conv_name(S):
# 結果を格納する変数
result=""
# Sのそれぞれの文字について
for i in S:
# 変換してresultの末尾へ結合
result+=conv_letter[i]
# resultを返す
return result
# Sを新しいアルファベットへ変換する関数
def inv_name(S):
# 結果を格納する変数
result=""
# Sのそれぞれの文字について
for i in S:
# 変換してresultの末尾へ結合
result+=inv_letter[i]
# resultを返す
return result
# 通常のアルファベットへ変換後の名前を格納する変数
conv_names=[]
# 入力の受け取り
for i in range(N):
# Sの受け取り
S=input()
# 通常のアルファベットへ変換
conv_S=conv_name(S)
# conv_namesへ追加
conv_names.append(conv_S)
# conv_namesを辞書順へソート
conv_names.sort()
# conv_namesのそれぞれについて
for conv_S in conv_names:
# 新しいアルファベットへ変換
inv_S=inv_name(conv_S)
# 出力
print(inv_S)
D - Strange Lunchbox
DPを使います。
この問題はDPの中でも難しい方で、初めてDP問題を解くという方は先に簡単なDP問題を解いてから挑戦することをおすすめします。
以下は比較的簡単なDP問題です。
ABC211 C：https://atcoder.jp/contests/abc211/tasks/abc211_c
(解説)：https://qiita.com/sano192/items/051207b6607b56cc439e#c---chokudai
EDPC A：https://atcoder.jp/contests/dp/tasks/dp_a
ABC178 D：https://atcoder.jp/contests/abc178/tasks/abc178_d
EDPC D：https://atcoder.jp/contests/dp/tasks/dp_d
ABC153 E：https://atcoder.jp/contests/abc153/tasks/abc153_e
(上記4つの問題は拙著『AtCoder 凡人が『緑』になるための精選50問詳細解説』で詳しく解説しています。詳しくは本ページ最下部「広告」の部分を御覧ください)
DPとは「ある状態までの最適解がわかっていれば→その次の状態の最適解も出せる」という手続きを何度も行って最終的な答えを出す方法です。
具体的な手順は以下です。
(1)表を作る
(2)すぐにわかるところを埋める
(3)表の小さい方から答えにたどり着くまで埋める
(4)答えを出力する
(1)表を作る
三次元の表を作ります。
dp[i][x][y]：「i番目までの弁当を使い、x個のたこ焼きとy個のたいやきを手に入れるために必要な弁当の最小個数」
とします。
最終的な答えは
dp[N][X][Y]：「N番目までの弁当を使い、X個のたこ焼きとY個のたいやきを手に入れるために必要な弁当の最小個数」
となります。
実装では3次元配列を作ります。
以下のように書けば3次元配列が作れます。
(初期値としてinfを入れています)
dp=[[[inf]*(Y+1) for i in range(X+1)] for j in range(N+1)]
(2)すぐにわかるところを埋める
すぐにわかるところはi=0の部分です。
まずdp[0][0][0]から考えましょう。
dp[0][0][0]：「0番目までの弁当を使い、0個のたこ焼きと0個のたいやきを手に入れるために必要な弁当の最小個数」
「0番目の弁当」なんてありません。「0番目の弁当を使う」=「弁当を一つも使わない(買わない)」というです。
弁当を一つも使わなくても0個のたこ焼きと0個のたい焼きを手に入れることは可能です。ゆえに
dp[0][0][0]=0
となります。
他の値の場合は無理です。例えばdp[0][3][3]について
dp[0][3][3]：「0番目までの弁当を使い、3個のたこ焼きと3個のたいやきを手に入れるために必要な弁当の最小個数」
「0番目の弁当を使う」=「弁当を一つも使わない(買わない)」ということですから、弁当を一つも買わずに3個のたこ焼きと3個のたいやきを手に入れることはできません。
実装上はバカでかい数inf(=10^10など)を定義して
dp[0][3][3]=inf
とします。
infが大きすぎると(10^20など)TLEします。
(3)表の小さい方から答えにたどり着くまで埋める
(2)すぐにわかるところを埋める が終わればdp[0][なんとか][なんとか]は全部埋まっています。
これを使ってdp[1][なんとか][なんとか]を埋め、dp[1][なんとか][なんとか]を使ってdp[2][なんとか][なんとか]を埋め...というのを繰り返します。
例として入力例1を考えましょう。
「入力例1」
3
5 6
2 1
3 4
2 3
弁当の種類：3
必要なたこ焼きの数：5
必要なたい焼きの数：6
1番目の弁当：たこ焼き2個,たい焼き1個
2番目の弁当：たこ焼き3個,たい焼き4個
3番目の弁当：たこ焼き2個,たい焼き3個
dp[1][なんとか][なんとか]を考えましょう。
1番目の弁当は
たこ焼き：2個 たいやき：1個 です。
結論から言うと以下のように表が埋まります。
・dp[1][2][1]
dp[1][2][1]=1となっています。
dp[1][2][1]：「1番目までの弁当を使い、2個のたこ焼きと1個のたいやきを手に入れるために必要な弁当の最小個数」
1番目までの弁当を使って2個のたこ焼きと1個のたいやきを手に入れるためには1番目の弁当を買えば良いわけですから、必要な弁当の最小個数は1です。
ゆえにdp[1][2][1]=1となっています。
次にdp[2][なんとか][なんとか]を考えましょう。
2番目の弁当は
たこ焼き：3個 たいやき：4個 です。
結論から言うと以下のように表が埋まります。
・dp[2][3][4]
dp[2][3][4]=1となっています。どのようにして1となったか説明します。
dp[1][0][0]=0：「1番目までの弁当を使い、0個のたこ焼きと0個のたいやきを手に入れるために必要な弁当の最小個数」=0
でした。
dp[1][0][0]の状態から2番目の弁当を買うと以下のように数が変化します。
弁当の個数：0+1
たこ焼きの個数：0+3=3
たい焼きの個数：0+4=4
ゆえに
dp[2][3][4](dp[2][0+3][0+4])=dp[1][0][0]+1=1
となったわけです。
+1の部分が弁当を買った=弁当の個数が1個増えたということを表しています。
・dp[2][5][5]
dp[2][5][5]=2となっています。どのようにして2となったか説明します。
dp[1][2][1]=1：「1番目までの弁当を使い、2個のたこ焼きと1個のたいやきを手に入れるために必要な弁当の最小個数」=1
でした。
dp[1][2][1]の状態2番目の弁当を買うと以下のように数が変化します。
弁当の個数：1+1=2
たこ焼きの個数：2+3=5
たい焼きの個数：1+4=5
ゆえにdp[2][5][5](dp[2][2+3][1+4])=dp[1][2][1]+1=2
となったわけです。
以上が2番目の弁当を買うパターンです。
逆に買わなかった場合も考えましょう。
・dp[2][2][1]
dp[2][2][1]=1となっています。どのようにして1となったか説明します。
dp[1][2][1]=1：「1番目までの弁当を使い、2個のたこ焼きと1個のたいやきを手に入れるために必要な弁当の最小個数」=1
でした。
2番目の弁当を買わなくても1番目の弁当までで2個のたこ焼きと1個のたいやきを手に入れることはできるわけです。
であればわざわざ2番目の弁当を買う必要はありません。ゆえに
dp[2][2][1]=dp[1][2][1]=1
となったわけです。
dp[2][2][1]は「2番目までの弁当を使う」であって「2番目の弁当を使う」ではないことに注意してください。
以上を一般化すると以下のようになります。
i番目の弁当を買う場合
dp[i][x+A][y+A]=dp[i-1][x][y]+1
+1の部分が弁当を買った=弁当の個数が1個増えたということを表しています。
i番目の弁当を買わない場合
dp[i][x][y]=dp[i-1][x][y]
ただし表を埋める際には2つの注意点があります。
(1)すでに表が埋まっている場合は埋めようとしている数と比較して小さければ更新する
たとえばdp[3][1][1]を計算して=3となったとしても、dp[3][1][1]=2が埋まっていれば更新しません。
(2)たこやき、たいやきの個数がX,Yを超えたらX,Yの部分を埋める
例えば3番目の弁当がたこ焼き：100個 たいやき：100個 であった場合、
dp[3][105][105](dp[2][5+100][5+100])=dp[2][5][5]+1
みたいなことになりますがこれは表のサイズを超えています。
この場合はX,Yを超えた時点で=X,Yに変えてしまいます。
(X,Y=5,6なのでdp[3][105][105]→dp[3][5][6]=dp[2][5][5]+1とします)
以上を実装すると以下のようになります。
tako,taiはそれぞれたこ焼きの個数、たい焼きの個数を表しています。
# i番目の弁当を買ったときに手に入れられるたこ焼きの数
# X個を超えたらX個まで
tako_plus=min(tako+A,X)
# i番目の弁当を買ったときに手に入れられるたい焼きの数
# Y個を超えたらY個まで
tai_plus=min(tai+B,Y)
# i番目の弁当を買った場合
# すでに埋まっている数か、
# 「i-1番目までの弁当を使い、tako個のたこ焼きとtai個のたいやきを手に入れる最小個数」+1
# の小さい方
dp[i][tako_plus][tai_plus]=min(dp[i][tako_plus][tai_plus],dp[i-1][tako][tai]+1)
# i番目の弁当を買わない場合
# すでに埋まっている数か、
# 「i-1番目までの弁当を使い、tako個のたこ焼きとtai個のたいやきを手に入れる最小個数」
# の小さい方
dp[i][tako][tai]=min(dp[i][tako][tai],dp[i-1][tako][tai])
まず
注意点(2)たこやき、たいやきの個数がX,Yを超えたらX,Yの部分を埋める
のために
tako_plus=min(tako+A,X)
tai_plus=min(tai+B,Y)
としてたこやきの数+A、たいやきの個数+BがX,Yを超えたらX,Yに変わるようにしています。
i番目の弁当を買う場合は
dp[i][tako_plus][tai_plus]=dp[i-1][tako][tai]+1
となりますが、
注意点(1)すでに表が埋まっている場合は埋めようとしている数と比較して小さければ更新する
がありますから、すでに埋まっている数と比較して小さい方を埋めます。
dp[i][tako_plus][tai_plus]=min(dp[i][tako_plus][tai_plus],dp[i-1][tako][tai]+1)
i番目の弁当を買わない場合は
dp[i][tako][tai]=dp[i-1][tako][tai]
となりますが、
注意点(1)すでに表が埋まっている場合は埋めようとしている数と比較して小さければ更新する
がありますから、すでに埋まっている数と比較して小さい方を埋めます。
dp[i][tako][tai]=min(dp[i][tako][tai],dp[i-1][tako][tai])
あとはi=1~N,tako=0~X,tai=0~Yとして、三重ループでdpを埋めていけばOKです。
最後dp[N][X][Y]が更新されていない場合は-1を出力します。
この問題はpythonだとTLEするためpypyで提出します。
【提出】
# pypyで提出
# 入力の受け取り
N=int(input())
X,Y=map(int, input().split())
# バカでかい数を作っておく(infinity)
inf=10**10
# 表を作る
dp=[[[inf]*(Y+1) for i in range(X+1)] for j in range(N+1)]
# 「0番目までの弁当を使い、0個のたこ焼きと0個のたいやきを手に入れる最小個数」=0
dp[0][0][0]=0
# i=1~N番目の弁当
for i in range(1,N+1):
# 入力の受け取り
A,B=map(int, input().split())
# tako=たこ焼き0～X個まで
for tako in range(X+1):
# tai=たい焼き0~Y個まで
for tai in range(Y+1):
# i番目の弁当を買ったときに手に入れられるたこ焼きの数
# X個を超えたらX個まで
tako_plus=min(tako+A,X)
# i番目の弁当を買ったときに手に入れられるたい焼きの数
# Y個を超えたらY個まで
tai_plus=min(tai+B,Y)
# i番目の弁当を買った場合
# すでに埋まっている数か、
# 「i-1番目までの弁当を使い、tako個のたこ焼きとtai個のたいやきを手に入れる最小個数」+1
# の小さい方
dp[i][tako_plus][tai_plus]=min(dp[i][tako_plus][tai_plus],dp[i-1][tako][tai]+1)
# i番目の弁当を買わない場合
# すでに埋まっている数か、
# 「i-1番目までの弁当を使い、tako個のたこ焼きとtai個のたいやきを手に入れる最小個数」
# の小さい方
dp[i][tako][tai]=min(dp[i][tako][tai],dp[i-1][tako][tai])
# 答え：「N番目までの弁当を使い、X個のたこ焼きとX個のたいやきを手に入れる最小個数」
ans=dp[N][X][Y]
# もし答えがinfだったら(X個以上のたこ焼き、Y個以上のたいやきを手に入れられない場合)
if ans==inf:
# -1を出力
print(-1)
# そうでないならば
else:
# 答えを出力
print(ans)
【広告】
『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】