More than 1 year has passed since last update.

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

Last updated at 2022-10-30Posted at 2022-10-30

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

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

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

A Dif:14

要するにHの中で最も大きい要素は何番目ですか？ということを聞かれています。
これを直接求める方法もなくはないのですが、ちょっとややこしいので、最も大きい要素を探す→そのインデックス番号を探すという方法で解きます。

まずHの中で最も大きい要素を探します。
max(H)
とすることでHの中で最も大きい要素がわかります。これをHmaxとしましょう

次にHmaxのインデックス番号を探します。
H.index(Hmax)
とすることでHのなかでHmaxが何番目かを確認できます。
ただし、pythonは先頭を0番目、次を1番目と数えます。よって問題文で言う番号と1個ずれるので+1しなければならないということに注意してください。

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

【提出】

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

# Hの中で最も大きい要素
Hmax=max(H)

# (Hmaxのインデックス番号+1)を出力
print(H.index(max(H))+1)

B Dif:147

指示通りに計算して出力すればOKです。
余りは「%」で計算します。

【提出】

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

# 計算して出力
print((A*B*C-D*E*F)%998244353)

C Dif:760

正方形は1辺が決まれば他の全ての頂点の座標が決まります。
例えば以下の例を見てみましょう。(実装に合わせて0インデックスで説明します。すなわち左上の座標を(0,0)とします)

A=(1,3)
B=(3,7)
です。このABを正方形の一辺として時計回りに、正方形のABCDを作ります。

Cの行番号=Bの行番号+(A→Bの列方向の増加量)=3+(7-3)=7
Cの列番号=Bの列番号-(A→Bの行方向の増加量)=7-(3-1)=5
Dの行番号=Cの行番号-(C→Bの列方向の増加量)=7-(7-5)=5
Dの列番号=Cの列番号-(B→Cの行方向の増加量)=5-(7-3)=1
これで
C=(7,5)
D=(5,1)
とわかります。
C,Dの座標がマス目の中に入っているかを確認して、全て「#」になっていればカウントします。

この要領でABを全パターン作って同じように確認していきます。
ただし、ABは上、または右上にある(正方形が斜めの場合)辺としたいので、A=(Ar,Ac),B=(Br,Bc)として
Ar≤Br,Ac<Bc
という条件付きで全パターンを作ります。

【提出】

# 座標の情報記録
S=[]

# 9回
for i in range(9):
    # 入力の受け取り
    Si=input()
    # リストへ変換(なくてもOK)
    Si=list(Si)
    # 記録
    S.append(Si)

# 正方形になっている組のカウント
count=0

# Aの行番号：Ar=0~8
for Ar in range(9):
    # Aの列番号：Ac=0~8
    for Ac in range(9):
        # Bの行番号：Br=Ar~8
        for Br in range(Ar,9):
            # Bの列番号：Br=(Ac+1)~8
            for Bc in range(Ac+1,9):
                # (Ar,Ac),(Br,Bc)が「#」ならば
                if S[Ar][Ac]=="#" and S[Br][Bc]=="#":
                    # Bの行番号+(A→Bの列方向の増加量)
                    Cr=Br+(Bc-Ac)
                    # Bの列番号-(A→Bの行方向の増加量)
                    Cc=Bc-(Br-Ar)
                    # Cの行番号-(C→Bの列方向の増加量)
                    Dr=Cr-(Bc-Cc)
                    # Cの列番号-(B→Cの行方向の増加量)
                    Dc=Cc-(Cr-Br)

                    # 全て座標の範囲内に収まっていれば
                    if 0<=Cr<=8 and 0<=Dr<=8 and 0<=Cc<=8 and 0<=Dc<=8:
                        # (Cr,Cc),(Dr,Dc)が「#」ならば
                        if S[Cr][Cc]=="#" and S[Dr][Dc]=="#":
                            # カウント
                            count+=1

# 答えの出力
print(count)

D Dif:606

一見fをそのまま定義すれば解けそうです。が、そのまま計算すると計算回数が莫大になり、失敗します。
そこでメモ化再帰というテクニックを使います。

例えばf(10)を計算してみましょう
f(10)
=f(5)+f(3)
=f(2)+f(1)+f(1)+f(1)
=f(1)+f(0)+f(0)+f(0)+f(0)+f(0)+f(0)+f(0)
=f(0)+f(0)+f(0)+f(0)+f(0)+f(0)+f(0)+f(0)+f(0)
=1+1+1+1+1+1+1+1+1
=9

計算の途中でf(1),f(0)が何度も出てきています。じゃあ毎回いちいち計算しなくても1回計算して結果メモしとけばよくない？というのがメモ化再帰です。
もう少しきちんと説明するとf(1)を一度計算して結果が確定したらそれをどこかに保存しておく→次にf(1)を計算する時は計算をやりなおさず保存した結果を使う、というやり方です。
やり方は簡単で、関数の前に以下の2文を入れておくだけです。

from functools import lru_cache
@lru_cache()

【提出】

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

# メモ化再帰
from functools import lru_cache
@lru_cache()
# fを定義
def f(k):
    # k=0ならば
    if k==0:
        # 1を返す
        return 1
    # そうでなければ
    else:
        # 再帰
        return f(k//2)+f(k//3)

# 計算して出力
print(f(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