デンソークリエイトプログラミングコンテスト2022 Winter(ABC280) A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest280) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

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

デンソークリエイト様について

会社説明動画

A Dif:12

S1に「#」がいくつあるか
S2に「#」がいくつあるか
...
を確認して足していきます。

H回文字列を受け取ると考えます。
for i in range(H)とすることでH回の繰り返し処理ができます。これでH回の受け取りを行いましょう。
文字列.count(文字)とすることで文字列に「文字」がいくつ含まれるかを確認できます。カウントした数を答えに足していき、最後に出力を行います。

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

【提出】

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

# 答え
ans=0

# H回
for i in range(H):
    # 入力の受け取り
    S=input()
    # Sに含まれる「#」の数をカウントして足す
    ans+=S.count("#")

# 答えの出力
print(ans)

B Dif:22

S1=A1
S2=A1+A2
S3=A1+A2+A3
S4=A1+A2+A3+A4
...
から
A1=S1
A2=S2-A1
A3=S3-(A1+A2)
A4=S4-(A1+A2+A3)
...
と計算できます。

ただしpythonではリストの先頭が0番目となり、A1=A[0],A2=A[1],...となります。
よって
A[0]=S[0]
A[1]=S[1]-A[0]
A[2]=S[2]-(A[0]+A[1])
A[3]=S[3]-(A[0]+A[1]+A[2])
...
となります。

A[0]~A[i-1]までの和はsum(A[:i])とすることで求めることができます。
よって一般には
A[i]=S[i]-sum(A[:i])と計算できます。
単純に全てのA[i]を計算して数列を作ればOKです。

【提出】

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

# Aを作り、A[0]を埋める
A=[S[0]]

# i=1~(N-1)
for i in range(1,N):
    # 計算してAへ追加
    A.append(S[i]-sum(A[:i]))

# 答えの出力(「*」をつけるとカッコなしで出力)
print(*A)

C Dif:64

Sの1文字目とTの1文字目
Sの2文字目とTの2文字目
Sの3文字目とTの3文字目
...
と順に確認していき文字が違う部分が答えです。

厄介なのはSの末尾に文字が挿入されたパターンです。
例えば
S=abcd
T=abcdz
だった場合、同様に確認していくと
Sの5文字目とTの5文字目が違う
となるのですが、Sの5文字目は存在しないため、エラーになってしまいます。

そこで予めSの末尾にアルファベット以外の文字(「?」等)を付け加えて文字数を合わせておきます。
こうすればエラーにならずに処理ができます。

pythonは0インデックス、すなわち先頭を0文字目と数えるので、答えを出力するときはプラス1してずらす必要があることに注意しましょう。

【提出】

# 入力の受け取り
S=input()
T=input()

# 末尾に「?」を追加
S=S+"?"

# i=0~(「S」の文字数-1)
for i in range(len(S)):
    # Sのi文字目≠Tのi文字目
    if S[i]!=T[i]:
        # (i+1)を出力
        print(i+1)
        # 終了
        exit()

D Dif:880

K=3600を例として考えます。
まず素因数分解してみると
3600=2^4*3^2*5^2
となります。
すなわち
N!がKの倍数となる⇔N!は因数に少なくとも2を4個、3を2個、5を2個持っている
ということがわかります。

因数に2を4個持つにはNが最低いくつになっていないといけないか考えます。
2!なら2が1個あります。
4!なら2と4(=2*2)で2が3個あります。
6!なら2と4(=2*2)と6(=2*3)で2が4個あります。
すなわち最低でもN=6以上でなければならないことがわかります。

同様に考えると3を2個持つためにはN=6以上、5を2個持つためにはN=10以上でなければならないとわかります。
このうち一番大きいのは10なので答えはN=10となります。

これを実装する方法を考えます。
まずKの素因数分解について、やり方がわからない人は以下を読んで下さい。

素因数分解のやり方
素因数分解はi=2,3,4,...でひたすら試し割りを行い、割り切れたらN=N//iと置き換えを行います。これを√N<iとなるまでひたすら続けます。
このやり方は計算量がO(√N)となります。
「例」
N=1260
i=2≤√1260なので試し割りを開始
i=2：1260//2＝630(素因数に2を追加)
i=2≤√630なので試し割りを続ける
i=2：630//2＝315(素因数に2を追加)
i=2≤√315なので試し割りを続ける
i=2：315は2で割れない→次のi=3へ
i=3≤√315なので試し割りを続ける
i=3：315//3＝105(素因数に3を追加)
i=3≤√105なので試し割りを続ける
i=3：105//3＝35(素因数に3を追加)
i=3≤√35なので試し割りを続ける
i=3：35は3で割れない→次のi=4へ
i=4≤√35なので試し割りを続ける
i=4：35は4で割れない→次のi=5へ
i=5≤√35なので試し割りを続ける
i=5：35//5＝7(素因数に5を追加)
√7=2.64...<i=5となったので、試し割りが終わりです。
最後に残った7を素因数として追加します。結果として1260=2*2*3*3*5*7が得られます。

実装ではPrimeFactorizeという関数を作って上記操作を行っています。
自分で実装できるようになるのが一番ですが、慣れないうちは丸々コピペで使ってもよいでしょう。

素因数分解ができたら素因数の種類ごとに処理を行います。
素因数のリストをPとして、重複を消すためにsetにしてしまうと良いでしょう。

ある素因数xがc個ある場合(すなわちKを素因数分解したときにx^cが因数にある場合)について、
x*1
x*2
x*3
...
と順にxがいくつあるかを確認してcからマイナスしていきます。
cが0個になったらNが最低でもいくつ以上であるかがわかります。

例えば例K=3600ではx=2がc=4個ありました。
2*1=2は2が1個ある→c=4-1=3
2*2=4は2が2個ある→c=3-2=1
2*3=6は2が1個ある→c=1-1=0
6の時点でc=0になったのでN=6以上が必要であるとわかります。

同じ処理を全ての種類の素因数について行い、答えを出します。

【提出】

# Nの素因数分解
# N=1の場合は空のリストを返す
def PrimeFactorize(N):
    # もしN=1ならば
    if N==1:
        # 空のリストを返す
        return []        
    # 素因数を格納するリスト
    p=[]
    # i=2,3,4,...で試し割り
    i=2
    # i≤√Nすなわちi**2≤Nの範囲で試し割り
    while i**2<=N:
        # もしiで割り切れたら
        if N%i==0:
            # iを素因数に追加
            p.append(i)
            # Nをiで割る
            N//=i
        # iで割り切れなかったら
        else:
            # 次のiへ
            i+=1
    # 試し割りが終わった時Nが1でなければ
    if N!=1:
        # 素因数にNを追加
        p.append(N)
    # 素因数のリストを返す
    return p

# 入力の受け取り
K=int(input())
# Kを素因数分解したリスト
P=PrimeFactorize(K)
# Pをsetへ展開(重複を消して素因数の種類を確認)
Pset=set(P)

# 答え
N=0
# x：Psetの各要素を順に格納
for x in Pset:
    # xがKにいくつ含まれるか(x^cがKの因数)
    c=P.count(x)

    # i=1~999(=てきとうな大きめの数)
    for i in range(1,1000):
        # x*iの値を記録
        Num=x*i
        # Numにいくつxがあるかを確認する
        # Numがxで割り切れる間⇔余りが0である間
        while Num%x==0:
            # xで割る
            Num//=x
            # cを1減らす
            c-=1

        # cが0以下になったら
        if c<=0:
            # 今までの答えより大きければ更新    
            N=max(N,x*i)
            # 次の因数xへ
            break

# 答えの出力
print(N)

【広告】

『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