LoginSignup
3
2

More than 1 year has passed since last update.

@sano192

パナソニックグループプログラミングコンテスト2022(ABC273) A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

Last updated at Posted at 2022-10-19

パナソニックグループプログラミングコンテスト2022(AtCoder Beginner Contest 273)　A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

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

パナソニックグループ様について

A Dif:11

fがどのような値になるか計算してみましょう。
f(0)=1
f(1)=1*f(0)=1
f(2)=2*f(1)=2
f(3)=3*f(2)=6
...
これは階乗ですね。すなわちf(x)=x!となっています。
pythonではmathライブラリのfactorialで階乗が計算できます。

まず
import math
と書きます。これでmathライブラリの機能が使えます。

math.factorial(x)
とすればx!が計算できます。

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

【提出】

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

# mathライブラリのインポート
import math

# N!を出力
print(math.factorial(N))

B Dif:178

要するに小さい方の位から順番に四捨五入しろということです。
以下の手順で解きます。
(1)Xを各桁ごとにリストへ展開
(2)小さい方の桁から
　・Xが5以上なら
　　次の桁へプラス1
　その桁は0にする
(3)繰り上がりの計算
　・Xが10以上なら
　　次の桁へプラス1
　その桁はマイナス10する

例として以下を考えます。
X：19735
K：3
Xを1文字ずつリストへ展開します。
X=[1,9,7,3,5]
最も小さい桁はX[4]=5です。これは5以上なので次の桁へプラス1(X[3]+1=4)してから0にします。
X=[1,9,7,4,0]
次の桁はX[3]=4です。これは5未満なので単に0にします。
X=[1,9,7,0,0]
次の桁はX[2]=7です。これは5以上なので次の桁へプラス1(X[1]+9=10)してから0にします。
X=[1,10,0,0,0]
これで四捨五入の処理は完了です。次に繰り上がりの処理をします。
X[1]=10になっていますから、X[0]にプラス1して、X[1]からマイナス10します。
X=[2,0,0,0,0]

後はXを全てくっつければ答えは20000とわかります。

実装ではいくつかポイントがあります。
・Xを一桁ずつリストへ展開するため、文字列として受け取ります。
・(Xの桁数)<Kならば答えは明らかに0になります。これは例外として処理します。
・Xをリストへ展開した後、先頭に[0]の要素を付け足して置きます。これは最も大きい桁で繰り上がりが発生した場合でもインデックスエラーにならないようにするためです。
・桁の小さい方から処理するため、forで大きい方から順に処理を行います。
　for i in range(最初の数,最後の数-1.-1)とすることで、i=(最初の数)~(最後の数)とマイナス1ずつしながら処理できます。

【提出】

# 入力の受け取り(文字列として)
X,K=map(str,input().split())
K=int(K)

# (Xの桁数)<Kならば
if len(X)<K:
    # 0を出力
    print(0)
    # 終了
    exit()

# N=Xの長さ
N=len(X)

# Xを1文字ずつリストへ展開
X=list(X)

# i=0~(N-1)
for i in range(N):
    # 文字列→整数へ変換
    X[i]=int(X[i])

# 桁数が増えたときのために先頭に[0]を追加する
X=[0]+X

# i=N~(N-K+1) -1ずつ
for i in range(N,N-K,-1):
    # 5≤X[i]ならば
    if 5<=X[i]:
        # 次の桁へプラス1
        X[i-1]+=1
    # X[i]を0にする
    X[i]=0

# 繰り上がりの計算
# i=N~1 -1ずつ
for i in range(N,0,-1):
    # 10≤X[i]ならば
    if 10<=X[i]:
        # 次の桁へプラス1
        X[i-1]+=1
        # X[i]からマイナス10
        X[i]-=10  

# 答え
ans=""

# i=0~N
for i in range(N+1):
    # 整数→文字列へ変換してansへくっつける
    ans+=str(X[i])

# 整数へ変換
ans=int(ans)

# 答えの出力
print(ans)

C Dif:370

とりあえずAをソートしましょう。
Aの各要素より大きい要素の種類数を確認するには重複の入らないsetを使うと便利です。
まずAの要素を全てsetに入れて、Aの小さい方から順にsetから削除→残った種類数を数えるとしていきます。
例えばA=[1,2,3,4,5,5]だった場合、Aをsetに入れたものをAsとするとAs=(1,2,3,4,5)となります。
A[0]=1なのでAsから1を削除するとAs=(2,3,4,5)なのでA[0]=1より大きな要素の種類数は4種類とわかります。
A[1]=2なのでAsから2を削除するとAs=(3,4,5)なのでA[1]=2より大きな要素の種類数は3種類とわかります。
...
というような感じで順に種類数を数えながらカウントしていきます。

【提出】

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

# Aを小さい順にソート
A.sort()
# Aの要素をセットへ入れ直す(重複除去)
As=set(A)

# 各種類数ごとのカウント
Count=[0]*N

# i=0~(N-1)
for i in range(N):
    # A[i]がAsに含まれていれば
    if A[i] in As:
        # Asから除去
        As.remove(A[i])
    # A[i]より大きい要素は(len(As))種類ある
    # カウントする
    Count[len(As)]+=1
    
# i=0~(N-1)
for i in range(N):
    # 答えの出力
    print(Count[i])

D Dif:1119

例えばd="R"の場合、右側の壁マスのうち一番近いものがどこにあるかということが重要になります。
今いるマスから右にl(エル)進むまでに壁マスがあればそこまで、なければl(エル)右へ進むということになります。
よって各行ごとに壁マスのある列番号を記録し、二分探索で最も近い壁を探します。

例えば今いるマスが(2,2)で、2行目の壁マスがある列は1,4,5,9だったとします。
この場合二分探索を行うと今いる列番号2は1と4の間にあることがわかるので、右に2以上進んでも壁にぶつかって(2,3)までしか進めません。

壁マスは最大10^9であるため、MLE(メモリ制限超過)しないよう行ごと、列ごとに連想配列で記録します。
そもそも二分探索を書いたことがない、連想配列が何か知らないという人にはこの問題はかなり難易度が高いので、他の問題を解いて実力をつけてから再挑戦することをおすすめします。

連想配列について確認、練習する場合はABC261Cがおすすめです。
【問題】
https://atcoder.jp/contests/abc261/tasks/abc261_c

【解説】
https://qiita.com/sano192/items/4ced90c15b839efa6890#c---newfolder1dif179

二分探索について練習する場合はABC231Cがおすすめです。
【問題】
https://atcoder.jp/contests/abc231/tasks/abc231_c

【解説】
https://qiita.com/sano192/items/2b2656202b767109387e#c---counting-2

【動画】

pythonでは間に合わないのでpypyで提出します。

【提出】

# pypyで提出

# 入力の受け取り
H,W,rs,cs=map(int,input().split())
N=int(input())

# defaultdictのインポート
from collections import defaultdict

# 各行ごとの壁マスの列を記録
# 初期値は空のリスト
KabeDR=defaultdict(list)
# 各列ごとの壁マスの行を記録
KabeDC=defaultdict(list)

# [行,列]の順に記録するリスト
RC=[]
# [列,行]の順に記録するリスト
CR=[]

# N回
for i in range(N):
    # 入力の受け取り
    r,c=map(int,input().split())
    # 記録
    RC.append([r,c])
    CR.append([c,r])

# 行の小さい順にソート
RC.sort()
# 列の小さい順にソート
CR.sort()

# r,c：RCの各要素を順に格納
for r,c in RC:
    # 列cのr行目に壁がある
    # ソートしているから行番号の小さい順に記録ができる
    KabeDC[c].append(r)

# 行も同様
for c,r in CR:
    KabeDR[r].append(c)

# 右方向への二分探索
# 今いるマスから右方向で最も近い壁マスの列番号を返す
def NibutanR(NowR,NowC):
    # 長さが0⇔今いる行に壁マスがない場合
    if len(KabeDR[NowR])==0:
        # 一番近い壁の列番号は(W+1)
        return W+1
    # 長さが1以上　かつ　最も大きい(右側にある)壁マスの列番号<今いるマスの列番号
    elif KabeDR[NowR][-1]<NowC:
        # 一番近い壁の列番号は(W+1)
        return W+1
    # 長さが1以上　かつ　今いるマスの列番号<最も小さい(左側にある)壁マスの列番号
    elif NowC<KabeDR[NowR][0]:
        # 一番近い壁の列番号はKabeDR[NowR][0](最も小さい壁マスの列番号)
        return KabeDR[NowR][0]
    
    # 探索範囲の決定
    # 左
    l=0
    # 右
    r=len(KabeDR[NowR])-1

    # 1<(右-左)である間
    while 1<r-l:
        # 中央
        c=(l+r)//2

        # 中央の壁マスの列番号<今いるマスの列番号
        if KabeDR[NowR][c]<NowC:
            # 左=中央と更新
            l=c
        # そうでない場合(今いるマスの列番号<中央の壁マスの列番号)
        else:
            # 右=中央と更新
            r=c
    
    # 今いるマスから右方向で最も近い壁マスの列番号を返す
    return KabeDR[NowR][r]

# 左方向への二分探索
# 今いるマスから左方向で最も近い壁マスの列番号を返す
def NibutanL(NowR,NowC):
    if len(KabeDR[NowR])==0:
        # 一番近い壁の列番号は0
        return 0
    # 長さが1以上　かつ　今いるマスの列番号<最も小さい(左側にある)壁マスの列番号
    elif NowC<KabeDR[NowR][0]:
        # 一番近い壁の列番号は0
        return 0
    # 長さが1以上　かつ　最も大きい(右側にある)壁マスの列番号<今いるマスの列番号
    elif KabeDR[NowR][-1]<NowC:
        # 一番近い壁の列番号はKabeDR[NowR][-1](最も大きい壁マスの列番号)
        return KabeDR[NowR][-1]
    
    # 探索範囲の決定
    # 左
    l=0
    # 右
    r=len(KabeDR[NowR])-1

    # 1<(右-左)である間
    while 1<r-l:
        # 中央
        c=(l+r)//2

        # 中央の壁マスの列番号<今いるマスの列番号
        if KabeDR[NowR][c]<NowC:
            # 左=中央と更新
            l=c
        # そうでない場合(今いるマスの列番号<中央の壁マスの列番号)
        else:
            # 右=中央と更新
            r=c
    
    # 今いるマスから左方向で最も近い壁マスの列番号を返す
    return KabeDR[NowR][l]

# 下方向への二分探索
# 今いるマスから右方向で最も近い壁マスの行番号を返す
def NibutanD(NowR,NowC):
    # 長さが0⇔今いる行に壁マスがない場合
    if len(KabeDC[NowC])==0:
        # 一番近い壁の行番号は(H+1)
        return H+1
    # 長さが1以上　かつ　最も大きい(下側にある)壁マスの行番号<今いる行
    elif KabeDC[NowC][-1]<NowR:
        # 一番近い壁の行番号は(H+1)
        return H+1
    # 長さが1以上　かつ　今いるマスの行番号<最も小さい(上側にある)壁マスの行番号
    elif NowR<KabeDC[NowC][0]:
        # 一番近い壁の列番号はKabeDC[NowC][0](最も小さい壁マスの行番号)
        return KabeDC[NowC][0]    
    
    # 探索範囲の決定
    # 左
    l=0
    # 右
    r=len(KabeDC[NowC])-1

    # 1<(右-左)である間
    while 1<r-l:
        # 中央
        c=(l+r)//2

        # 中央の壁マスの行番号<今いるマスの行番号
        if KabeDC[NowC][c]<NowR:
            # 左=中央と更新
            l=c
        # そうでない場合(今いるマスの行番号<中央の壁マスの行番号)
        else:
            # 右=中央と更新
            r=c
    
    # 今いるマスから右方向で最も近い壁マスの行番号を返す
    return KabeDC[NowC][r]

# 上方向への二分探索
# 今いるマスから上方向で最も近い壁マスの行番号を返す
def NibutanU(NowR,NowC):
    # 長さが0⇔今いる行に壁マスがない場合
    if len(KabeDC[NowC])==0:
        # 一番近い壁の行番号は0
        return 0
    # 長さが1以上　かつ　今いるマスの行番号<最も小さい(上側にある)壁マスの行番号
    elif NowR<KabeDC[NowC][0]:
        # 一番近い壁の行番号は0
        return 0
    # 長さが1以上　かつ　最も大きい(下側にある)壁マスの行番号<今いるマスの行番号
    elif KabeDC[NowC][-1]<NowR:
        # 一番近い壁の行番号はKabeDC[NowC][-1](最も大きい壁マスの行番号)
        return KabeDC[NowC][-1]

    # 探索範囲の決定
    # 左
    l=0
    # 右
    r=len(KabeDC[NowC])-1

    # 1<(右-左)である間
    while 1<r-l:
        # 中央
        c=(l+r)//2

        # 中央の壁マスの行番号<今いるマスの行番号
        if KabeDC[NowC][c]<NowR:
            # 左=中央と更新
            l=c
        # そうでない場合(今いるマスの行番号<中央の壁マスの行番号)
        else:
            # 右=中央と更新
            r=c
    
    # 今いるマスから上方向で最も近い壁マスの行番号を返す
    return KabeDC[NowC][l]

# 今いる行、列
NowR,NowC=rs,cs

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

# Q回
for i in range(Q):
    # 入力の受け取り
    d,l=map(str,input().split())
    # 整数へ変換
    l=int(l)

    # 右へ進む場合
    if d=="R":
        # 今いるマスから右方向で最も近い壁マスの列番号
        KabeC=NibutanR(NowR,NowC)
        # l右へ進んだ時の列番号<壁マスの列番号なら
        if NowC+l<KabeC:
            # 進む
            NowC+=l
        # そうでなければ
        else:
            # 壁マスの手前まで進む
            NowC=KabeC-1
    
    # 左へ進む場合
    elif d=="L":
        # 今いるマスから左方向で最も近い壁マスの列番号
        KabeC=NibutanL(NowR,NowC)
        # 壁マスの列番号<l左へ進んだ時の列番号なら
        if KabeC<NowC-l:
            # 進む
            NowC-=l
        # そうでなければ
        else:
            # 壁マスの手前まで進む
            NowC=KabeC+1

    # 下方向へ進む場合
    elif d=="D":
        # 今いるマスから下方向で最も近い壁マスの行番号
        KabeR=NibutanD(NowR,NowC)
        # l下へ進んだ時の行番号<壁マスの行番号なら
        if NowR+l<KabeR:
            # 進む
            NowR+=l
        # そうでなければ
        else:
            # 壁マスの手前まで進む
            NowR=KabeR-1

    # 上方向へ進む場合
    elif d=="U":
        # 今いるマスから上方向で最も近い壁マスの行番号
        KabeR=NibutanU(NowR,NowC)
        # 壁マスの行番号<l上へ進んだ時の行番号なら
        if KabeR<NowR-l:
            # 進む
            NowR-=l
        # そうでなければ
        else:
            # 壁マスの手前まで進む
            NowR=KabeR+1

    # 今いるマスを出力
    print(NowR,NowC)

【広告】

『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

3
2
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
Sign upLogin
3
2