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

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

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

https://qiita.com/sano192/items/54accd04df62242b70f0

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

# A Dif:14

https://atcoder.jp/contests/abc275/tasks/abc275_a

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

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

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

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

https://qiita.com/sano192/items/6361ed72106cb6dd5843#1-%E5%85%A5%E5%8A%9B%E3%81%A8%E5%87%BA%E5%8A%9B-abc205-a-dif6

**【提出】**

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

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

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

# B Dif:147

https://atcoder.jp/contests/abc275/tasks/abc275_b

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

**【提出】**

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

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

https://atcoder.jp/contests/abc275/tasks/abc275_c

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

![ABC275_C_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/700383/191c8abe-9cfe-2a33-a524-a4c457a20e77.png)

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
という条件付きで全パターンを作ります。

**【提出】**

```python:
# 座標の情報記録
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

https://atcoder.jp/contests/abc275/tasks/abc275_d

一見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文を入れておくだけです。

```python:
from functools import lru_cache
@lru_cache()
```

**【提出】**

```python:
# 入力の受け取り
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

## 『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
**値段：300円(Kindle Unlimited対象)**

<iframe width="560" height="315" src="https://www.youtube.com/embed/J_uaNYRuuZU" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

**【kindle】**
https://www.amazon.co.jp/dp/B09XLM42MW

**【booth(pdf】**
https://sano192.booth.pm/items/3785312