LoginSignup
6
4

More than 1 year has passed since last update.

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

Last updated at Posted at 2022-05-24

ABC252(AtCoder Beginner Contest 252) A~D問題の解説記事です。
灰色~茶色コーダーの方向けに解説しています。

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

更新時はツイッターにて通知します。
https://twitter.com/AtCoder4

A - ASCII code Dif:7

入力が97なら「a」、98なら「b」と条件分岐を全て書けば解けます。
文字列を出力するときはprint("a")と「""」(ダブルクオーテーション)をつけることに気をつけてください。
(【提出1】)

ちょっとめんどくさいなーと思った人は「python 文字コード 変換」で検索してみましょう。文字コードから文字へ変換する方法が見つかります。
コンテスト中でも検索して知らないことを調べるのは非常に有効な方法です。

chr(文字コード)と書くことで「文字コード」→「文字」へ変換ができます。
(【提出2】)

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

【提出1】

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

# Nが97ならば
if N==97:
    # 「a」を出力
    print("a")
# Nが98ならば
elif N==98:
    # 「b」を出力
    print("b")
elif N==99:
    print("c")
elif N==100:
    print("d")
elif N==101:
    print("e")
elif N==102:
    print("f")
elif N==103:
    print("g")
elif N==104:
    print("h")
elif N==105:
    print("i")
elif N==106:
    print("j")
elif N==107:
    print("k")
elif N==108:
    print("l")
elif N==109:
    print("m")
elif N==110:
    print("n")
elif N==111:
    print("o")
elif N==112:
    print("p")
elif N==113:
    print("q")
elif N==114:
    print("r")
elif N==115:
    print("s")
elif N==116:
    print("t")
elif N==117:
    print("u")
elif N==118:
    print("v")
elif N==119:
    print("w")
elif N==120:
    print("x")
elif N==121:
    print("y")
elif N==122:
    print("z")

【提出2】

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

# 文字コード→文字へ変換して出力
print(chr(N))

B - Takahashi's Failure Dif:42

高橋くんが食べる可能性があるのは美味しさが最大の食品、つまりAのうち最大値であるものです。
まずAの最大値を確認し、A[B1],A[B2],...イコールAの最大値になっているか確認しましょう。
一つでもイコールになっているものがあればそれを食べてしまう可能性があるので「Yes」、そうでなければ「No」を出力します。
途中で終了する場合はexit()と書きます。

pythonでは0インデックス、すなわち配列が0番目から始まります。そのため実装ではA[B[i]]ではなくA[B[i]-1]とBの入力からひとつずらさなければならないことに注意してください。

【提出】

# 入力の受け取り
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

# Aの最大値
Amax=max(A)

# i=0~(K-1)
for i in range(K):
    # A[B[i]-1]=(Aの最大値)ならば
    if A[B[i]-1]==Amax:
        # 「Yes」を出力
        print("Yes")
        # 終了
        exit()

# 「No」を出力
print("No")

C - Slot Strategy Dif:441

0を揃える場合、1を揃える場合、...、9を揃える場合と全パターンについてかかる時間を考えます。
例として以下の入力を考えましょう。

4
0123456789
1023456789
2103456789
2130456789

それぞれの数について何秒時点で表示されるか確認しましょう。
例えば「0」は1番目のリールで0秒、2番目のリールで1秒、3番目のリールで2秒、4番目のリールで3秒時点で表示されます。
「1」は1番目のリールで1秒、2番目のリールで0秒、3番目のリールで1秒、4番目のリールで1秒時点で表示されます。

それぞれについて表示される秒数を記録していきます。
0:[0,1,2,3]
1:[1,0,1,1]
2:[2,2,0,0]
...

「0を揃える場合」
0:[0,1,2,3]ですから、0秒、1秒、2秒、3秒時点でリールをそれぞれ止めれば揃います。よって3秒で揃えることができます。

「1を揃える場合」
1:[1,0,1,1]です。まず0秒時点で2番目のリールを止めます。1秒時点では1番目、3番目、4番目のリールが「1」を表示していますが一度に止められるのは1つです。
1番目のリールを1秒時点で止めた場合、2,3番目のリールが次に「1」を表示するのは10秒後、すなわち11秒時点です。
11秒時点で2番目のリールを止めた場合、3番目のリールが次に「1」を表示するのは10秒後、すなわち21秒時点です。

このように考えると出現する秒数が複数ある場合は(出現回数-1)*10を足していけばよいということがわかります。
1:[1,0,1,1]ですが2番目の「1」には(2-1)*10=10、3番目の「1」には(3-1)*10=20を足します。
1:[1,0,1,1]

1:[1,0,11,21]

この形に修正すれば全てのリールを揃えるまでにかかる時間というのは表示される秒数の最大値を取れば良いということがわかります。
1:[1,0,11,21]は最大値が21なので、「1」を揃えるには21秒かかるというわけです。

同様の処理を「2」,「3」,...,「9」についても行い、最小秒数を探します。

【提出】

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

# 「0」~「9」の表示秒数記録リスト
# 0:[0,1,2,3]⇔Time[0]=[0,1,2,3] というように記録する
Time=[[] for i in range(10)]

# 各数の出現回数を数えるリスト
# C[1][2]=3なら「1」の表示秒数に2が3回表示された という意味
Count=[[0]*10 for i in range(10)]

# N回
for i in range(N):
    # 入力の受け取り
    S=input()
    
    # x=0~9
    for x in range(10):
        # Sのx文字目を整数へ変換
        Sint=int(S[x])

        # 出現回数をプラス1
        Count[Sint][x]+=1
        # 表示秒数を記録
        # (出現回数-1)*10をプラスする
        Time[Sint].append(x+(Count[Sint][x]-1)*10)

# 答え
# 初期値は大きめの数にしておく
ans=10**15

# i=0~9
for i in range(10):
    # 「i」を揃えるための秒数
    # ⇔Time[i]の最大
    # これまでの答えより小さければ更新
    ans=min(ans,max(Time[i]))

# 答えを出力
print(ans)

D - Distinct Trio Dif:884

要するにAから相異なる3つの要素を選ぶ方法は何通りあるか?という問題です。
相異なる3つの要素ですから大小関係がつきます。選んだ3つの要素をAi,Aj,Akとし、Ai<Aj<Akを満たすようにしましょう。
Ajを決めてしまえばAi,Akとして選べるのは以下の条件を満たすものになります。
Ai:Ajより小さい要素
Ak:Ajより大きい要素
任意の数xについてxより小さい要素がAにいくつあるか記録するリストがあればこれらはすぐに(O(1))で計算できます。
あとはAjを全探索すれば終わりです。

任意の数xについてxより小さい要素がAにいくつあるか記録するリストは以下の手順で作ります。
(1)各数の出現回数を記録したリスト(Count)を作る 例:Count[2]=5ならAに「2」が5個ある
(2)i=0,1,2,..の順でCount[i+1]+=Count[i]と加算していく

【提出】

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))

# 出現回数の確認リスト
Count=[0]*(10**6)

# i=0~(N-1)
for i in range(N):
    # 出現回数をカウント
    Count[A[i]]+=1
 
# i=0~(10^6-2)
for i in range(10**6-1):
    # 一つ前の数を足していく
    Count[i+1]+=Count[i]

# 上記の処理でCount[x]=「Aにあるxより小さい要素の数」となる

# 答え
ans=0

# j=0~(N-1)
for j in range(N):
    # (Ajより小さい要素の数)*(Ajより大きい要素の数)
    ans+=Count[A[j]-1]*(N-Count[A[j]])

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

6
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
4