More than 1 year has passed since last update.

ABC242 A～C問題ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

Last updated at 2022-08-09Posted at 2022-03-06

ABC242(AtCoder Beginner Contest 242)　A～C問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下です。

A - T-shirt

てきとうにA,B,CとXを決めて確率を計算してみましょう。
A=100
B=200
C=50
とします。

・X=10
100位までは確実にシャツがもらえますから、確率は1です。

・X=150
101位～200位の100人の中から、50人が選ばれてTシャツがもらえます。
200-100=100人から50人が選ばれた中にいろはちゃんが入っている確率は50/100=0.5となります

・X=300
201位以降の人はTシャツがもらえません。確率は0です。

以上から以下のように条件分岐すれば良いことがわかります。
・X≤Aの場合　→　確率は1
・A<X≤Bの場合　→　確率はC/(B-A)
・それ以外(B<X)の場合　→　確率は0

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

【提出】

# 入力の受け取り
A,B,C,X=map(int,input().split())

# X≤Aの場合
if X<=A:
    # 確率は1
    print(1)

# A<X≤Bの場合
elif A<X<=B:
    # 確率はC/(B-A)
    print(C/(B-A))

# それ以外(B<X)の場合
else:
    # 確率は0
    print(0)

B - Minimize Ordering

pythonでは文字の入ったリストをソートすると辞書順へ並び替えてくれます。

以下の手順で解きます。
(1)Sを受け取る
(2)Sを1文字ずつリストに格納する
　1文字ずつリストに格納するにはlist(S)と書きます
(3)Sをソートする
　S.sort()と書くことでSをソートできます
(4)リストを結合する
　"".join(S)と書くことでリストを結合し、一つの文字にできます
　ややこしい書き方ですが「python リスト結合」などで検索するとすぐに出てくるのでいちいち覚える必要はありません

【提出】

# (1)Sを受け取る
S=input()

# (2)Sを1文字ずつリストに格納する
S=list(S)

# (3)Sをソートする
S.sort()

# (4)リストを結合する
S="".join(S)

# 答えの出力
print(S)

C - 1111gal password

DPで解きます。

DPとは「ある状態までの答えがわかっていれば→その次の状態の答えも出せる」という手続きを何度も行って最終的な答えを出す方法です。

具体的な手順は以下です。
(1)表を作る
(2)すぐにわかるところを埋める
(3)表の小さい方から答えにたどり着くまで埋める
(4)答えを出力する

DPの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。
https://www.youtube.com/watch?v=gVJ16ThsJYs

N=4を例として考えましょう。

(1)表を作る
今回作る表は「桁数dで末尾がiの整数の個数」とします。
名前はdpとしましょう。

例えばdp[3][2]だと「桁数3で末尾が2の整数の個数」を表します。
112
122
212
222
232
322
332
432
上記8通りが考えられるので
dp[3][2]=8
となります。

(2)すぐにわかるところを埋める
すぐにわかるのはd=1の行、すなわち「桁数1で末尾がiの整数の個数」です。
例えばdp[1][1]というのは「桁数1で末尾が1の整数の個数」となりますが、これは「1」の1個しかありません。
同様にdp[1][2],dp[1][3]もそれぞれ「2」「3」の1個しかありません。
よってdp[1][1]~dp[1][9]は全て1が埋まります。
かっこよく書くと以下のようになります。
・(1≤i≤9) dp[1][i]=1

(3)表の小さい方から答えにたどり着くまで埋める
続いてd=2の行を考えましょう。
dp[2][1]というのは「桁数2で末尾が1の整数の個数」となりますね。これは「11」「21」の2個あります。

dp[2][2]というのはどのように作ればよいでしょうか。
末尾が2になるというのは桁数が1の数のうち、「1」「2」「3」に「2」をくっつけることで出来ます。
「1」に「2」をくっつけると「12」
「2」に「2」をくっつけると「22」
「3」に「2」をくっつけると「32」
よって上の段の「左上」「上」「右上」を足した数分、「桁数2で末尾が2の整数」を作ることができます。

これを式で書くと
dp[2][2]=dp[1][1]+dp[1][2]+dp[1][3]
となります。

他の部分も同様に考えます。
dp[2][3]であれば桁数が1の数のうち、「2」「3」「4」に「3」をくっつけることで出来ます。
式にすると
dp[2][3]=dp[1][2]+dp[1][3]+dp[1][4]

dp[2][4]であれば桁数が1の数のうち、「3」「4」「5」に「4」をくっつけることで出来ます。
式にすると
dp[2][4]=dp[1][3]+dp[1][4]+dp[1][5]

このように上の段の「左上」「上」「右上」を足すとそれぞれの個数を計算できます。

注意が必要なのは末尾が1または9になる場合です。
dp[2][1]だったら桁数が1の数数のうち、「1」「2」に「1」をくっつけることで出来ます。これは「上」「右上」を足すということです。
式にすると
dp[2][1]=dp[1][1]+dp[1][2]
となります。

dp[2][9]だったら桁数が1の数数のうち、「8」「9」に「9」をくっつけることで出来ます。これは「左上」「上」を足すということです。
式にすると
dp[2][9]=dp[1][8]+dp[1][9]
となります。

一般化すると以下のようになります。
(2≤d,i=1) dp[d][i]=dp[d-1][i]+dp[d-1][i+1]
(2≤d,1≤i≤8) dp[d][i]=dp[d-1][i-1]+dp[d-1][i]+dp[d-1][i+1]
(2≤d,i=9) dp[d][i]=dp[d-1][i-1]+dp[d-1][i]

(4)答えを出力する
表を全部埋めると以下のようになります。

4行目は「桁数4で末尾がiの整数の個数」となりますから、4行目を全て足した数が答えの個数です。
13+22+26+27+27+27+26+22+13=203
答えは203個となります。

998244353で割った余りは計算の都度取るようにしましょう。
答えの出力直前にだけ余りを取ると途中の計算で桁数が大きくなりすぎてTLEする可能性があります。

計算量は表を全部埋めるのにN*10回の計算が必要となりますので、最大で10^7回です。
pythonでは間に合わないのでpypyで提出します。

【提出】

# pypyで提出

# 余りの定義
mod=998244353

# 入力の受け取り
N=int(input())

# (1)表を作る
dp=[[0]*10 for i in range(N+1)]

# (2)すぐにわかるところを埋める
# i=1~9
for i in range(1,10):
    # ・(1≤i≤9)
    dp[1][i]=1

# (3)表の小さい方から答えにたどり着くまで埋める
# d=2~N
for d in range(2,N+1):
    # i=1~9
    for i in range(1,10):
        # (2≤d,i=1)
        if i==1:
            dp[d][i]=dp[d-1][i]+dp[d-1][i+1]

        # (2≤d,1≤i≤8)
        elif 2<=i<=8:
            dp[d][i]=dp[d-1][i-1]+dp[d-1][i]+dp[d-1][i+1]

        # (2≤d,i=9)
        else:
            dp[d][i]=dp[d-1][i-1]+dp[d-1][i]

        # 余りを取る
        dp[d][i]%=mod

# (4)答えを出力する
# N行目を全て足す
ans=sum(dp[N])%mod

# 答えの出力
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