ABC281(AtCoder Beginner Contest281) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
更新時はツイッターにて通知します。
https://twitter.com/AtCoder4
A Dif:6
for文で大きい方から小さい方へ処理を行います。
やり方を知らなければ「python カウントダウン」などで検索してみましょう。
for i in range(最初の数,最後の数-1,-1)
と書くことでiに(最初の数)から1つずつ減らしながら代入して処理できます。
ですのでiを順に出力すればOKです。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
N=int(input())
# i=N~0,-1ずつ
for i in range(N,-1,-1):
# iを出力
print(i)
B Dif:66
Yesになる条件を列挙します。
・Sは8文字
・Sの0文字目(先頭)は英大文字
・Sの7文字目(末尾)は英大文字
・Sの1~6文字目は全て数字
・Sの1~6文字目は10000以上999999以下
どれか一つでも成り立たなければNoになります。
つまり
・Sは8文字でない
・Sの0文字目(先頭)が数字
・Sの7文字目(末尾)が数字
・Sの1~6文字目に英大文字が入っている
・Sの1~6文字目は100000未満または999999より大きい
これらの条件を全て確認すればOKです。
文字列の長さはlen(文字列)で確認できます。
数字であるか？は.isnumeric()で確認できます。逆に数字「でない」場合はnotをつければOKです。
数値の大きさはint(文字列)とすることで文字列→数値に変換して確認します。S[1:7]と書くことでSの1文字目~6文字目という意味になります。
【提出】
S=input()
# ・Sは8文字でない
if len(S)!=8:
print("No")
# ・Sの0文字目(先頭)が数字
elif S[0].isnumeric():
print("No")
# ・Sの7文字目(末尾)が数字
elif S[7].isnumeric():
print("No")
# ・Sの1~6文字目に英大文字が入っている
elif not S[1:7].isnumeric():
print("No")
# ・Sの1~6文字目は10000未満または999999より大きい
elif int(S[1:7])<100000 or 999999<int(S[1:7]):
print("No")
# 全て当てはまらなければ
else:
print("Yes")
C Dif:131
愚直にシミュレーションしようとするとTの値が大きすぎてTLEします。
まずT分でプレイリストを何周するか考えましょう。
1週するのにかかる時間は(Aの合計)分ですから、T//(Aの合計)で何周するかを計算できます。
周回した後の残り時間はT-(Aの合計)*(T//(Aの合計))となりますね。
例を見てみましょう。
T：55
A：1 2 3 4
Aの合計は10分です。
残り時間はT-(Aの合計)*(T//(Aの合計))=55-10*(55//10)=5です。
もう一つ。
T：50
A：1 3 5 7
Aの合計は16分です。
残り時間はT-(Aの合計)*(T//(Aの合計))=50-16*(50//16)=2です。
それぞれ残り時間がTを(Aの合計)で割った余りになっていますね。これは偶然ではなく必ずそうなります。
よって残り時間=T%(Aの合計)と計算できます。
これを計算してから改めて曲1で残り時間が0になるか、曲2で残り時間が0になるか、...と計算していけばOKです。
【提出】
# 入力の受け取り
N,T=map(int,input().split())
A=list(map(int,input().split()))
# Tを(Aの合計)で割った余り
T%=sum(A)
# i=0~(N-1)
for i in range(N):
# 曲(i+1)の途中で残り時間が0になったら
# ⇔T-A[i]がマイナスになったら
if T-A[i]<0:
# 答えの出力
print(i+1,T)
# 終了
exit()
# そうでなければ
else:
# 残り時間から曲(i+1)の時間をマイナス
T-=A[i]
D Dif:1031
DPで解きます。
DPとは「ある状態までの答えがわかっていれば→その次の状態の答えも出せる」という手続きを何度も行って最終的な答えを出す方法です。
DPの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。
具体的な手順は以下です。
(1)表を作る
(2)すぐにわかるところを埋める
(3)表の小さい方から答えにたどり着くまで埋める
(4)答えを出力する
例
N：5
K：3
D：3
A：1 3 5 2 4
(1)表を作る
今回作る表は3次元になります。表の名前はdpとします。
「A1~Aiまででx個の和を取った時、余りがdになるものの最大値」
余りはDで割った余りを表します。
初期値は全て-1です。
例えばdp[4][3][2]であれば「A1~A4までで3個の和を取った時、余りが2になるものの最大値」
となります。
A1~A4=[1,3,5,2]から1,5,2の3個を取り出し、和を取ると8になります。8%3=2となりますのでこれが最大値となり、dp[4][3][2]=8となります。
最終的にdp[N][K][0]がわかれば「A1~ANまででK個の和を取った時、余りが0になるものの最大値」となり、これが答えになります。
(2)すぐにわかるところを埋める
各項1個だけ取った時の和はすぐに計算できます。
例えばA1~A1でA1だけを取った場合、A1%D=1%3=1ですからdp[1][1][1]=1となります。
A1~A2でA2だけを取った場合、A2%D=3%3=0ですからdp[2][1][0]=3となります。
A1~A3でA3だけを取った場合、A3%D=5%3=2ですからdp[3][1][2]=5となります。
同様に考えるとA[i][1][Ai%D]=Aiと計算できます。
・・・と、いう方法は実は正確ではないごまかしです。
例えばA[4][1][A4%3]=A[4][1][2]=2となります。
しかしA1~A4で1個だけ取って余り2になる最大値ならA3を取って5となるはずです。
これは必ず正しい(確定の値)が入ったというわけではなく、とりあえず入れていると思ってください。
この後の処理で値が更新されることもあります。
※公式解説のようにdp[0][0][0]=0と初期値を割り当てる方法もあります。こちらのほうがスマートですが、直感的に分かりづらいところがあるので今回は上記の方法を採用しています。
(2)すぐにわかるところを埋める
i=1の場合を考えましょう。
i=1では「A1~A1まででx個の和を取った時、余りがdになるものの最大値」となります。
すでにdp[1][1][1]は埋まっており、その他の部分は埋めようがありません。
i=2の場合はどうなるでしょうか。
i=2では「A1~A2まででx個の和を取った時、余りがdになるものの最大値」となります。
まず1個取る場合を考えましょう。
A2を取らなければA1=1
A2を取ればA2=3
になります。
それぞれ余りが1,0ですから
dp[2][1][1]=1
dp[2][1][0]=3
となります。
2個取る場合はA1,A2両方を取る他ありません。
A1+A2=4で余りは1ですから
dp[2][2][1]=4
となります。
以上を表に埋めます。
次にi=3を考えます。
まず1個取る場合、
A3を取らなければA1~A2で1個取った場合の値、すなわちdp[2][1][d]の値をそのまま持ってくることになります。
A3を取ればA3=5で余りは2なのでdp[3][1][2]=5となります。
式にすると
A3を取らない場合：dp[3][1][d]=dp[2][1][d]
A3を取る場合：dp[3][1][A[3]%D]=A3
となります。これらの大きい方を埋めるというイメージです。
次に2個取る場合を考えましょう。
A3を取らなければA1~A2で2個取った場合、dp[2][2][d]の値をそのまま持ってくることになります。
すなわち
dp[3][2][0]=dp[2][2][0]=なし
dp[3][2][1]=dp[2][2][1]=4
dp[3][2][2]=dp[2][2][2]=なし
となります。
A3を取る場合は取った合計数が2個になるわけなので、「A1~A2ですでに1個取っている状態」+A3という形になり、dp[2][1][d]+A3となります。
dp[2][1][0]+A3=3+5=8(余り2)
dp[2][1][1]+A3=1+5=6(余り0)
dp[2][1][2]+A3 はdp[2][1][2]に値が入っていないのでスルーです。
上2つは余りで割り振りし、それぞれdp[3][2][2]=8,dp[3][2][0]=6となります。
3個取る場合はどうでしょうか。
2個の場合と同様に考えると
A3を取らなければA1~A2で3個取った場合、になるのですがdp[2][3][d]は値が入っていません。(A1~A2で3個取るのはそもそも無理ですね)
A3を取る場合は取った合計数が3個になるわけなので、「A1~A2ですでに2個取っている状態」+A3という形になり、dp[2][2][d]+A3となります。
dp[2][2][0]+A3 はdp[2][2][0]に値が入っていないのでスルー
dp[2][2][1]+A3=4+5=9(余り0)
dp[2][2][2]+A3 はdp[2][2][2]に値が入っていないのでスルー
よってdp[3][3][0]=9となります。
ここまでの話を一般化しましょう。
・Aiを取らない場合
dp[i][k][d]=dp[i-1][k][d]
・Aiを取る場合
※dp[i-1][k-1][d]に値が入っている場合
dp[i][k][(d+A[i])%D]=dp[i-1][k-1][d]+A[i]
ただし、どちらもすでに入っている値の方が大きければ更新しません。よって以下のようになります。
・Aiを取らない場合
dp[i][k][d]=max(dp[i][k][d],dp[i-1][k][d])
・Aiを取る場合
※dp[i-1][k-1][d]に値が入っている場合
dp[i][k][(d+A[i])%D]=max(dp[i][k][(d+A[i])%D],dp[i-1][k-1][d]+A[i])
これで表を埋めていきます。
(4)答えを出力する
表を全て埋めると、i=5の部分は以下のようになります。
答えは「A1~A5までで3個の和を取った時、余りが0になるものの最大値」すなわちdp[N][K][0]=dp[5][3][0]なので12になります。
【提出】
# 入力の受け取り
N,K,D=map(int,input().split())
# A[0]を0で埋めて番号をずらしておく(1インデックスにする)
A=[0]+list(map(int,input().split()))
# (1)表を作る
dp=[[[-1]*D for i in range(K+1)] for j in range(N+1)]
# (2)すぐにわかるところを埋める
# i=1~N
for i in range(1,N+1):
# A1~AiまででAiだけ1個取った場合
dp[i][1][A[i]%D]=A[i]
# (3)表の小さい方から答えにたどり着くまで埋める
# i=2~N
for i in range(2,N+1):
# x=1~i または 1~K
for x in range(1,min(i+1,K+1)):
# d=0~(D-1)
for d in range(D):
# ・Aiを取らない場合
dp[i][x][d]=max(dp[i][x][d],dp[i-1][x][d])
# ・Aiを取る場合
if dp[i-1][x-1][d]!=-1:
dp[i][x][(d+A[i])%D]=max(dp[i][x][(d+A[i])%D],dp[i-1][x-1][d]+A[i])
# (4)答えを出力する
print(dp[N][K][0])
【広告】
『AtCoder 最速で緑になる 基礎・典型50問詳細解説』
ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP
【booth(pdf)】
https://booth.pm/ja/items/4102300
冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843
『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