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

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

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

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

# A - Four Points

https://atcoder.jp/contests/abc246/tasks/abc246_a

答えの座標を(x4,y4)とします。

まずは図を描いてみましょう。
![ABC246_A_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/700383/22e70368-e358-870d-90da-c1c320a84e50.png)

この図の場合だと
x4=x1
y4=y3
となります。
このときx2=x3、y1=y2となっていることがわかります。

長方形ではx座標、y座標について、2つの組が必ず同じになるわけですから、答えは以下のように計算できます。
x1=x2の場合：x4=x3
x2=x3の場合：x4=x1
x3=x1の場合：x4=x2

y1=y2の場合：y4=y3
y2=y3の場合：y4=y1
y3=y1の場合：y4=y2

これをifで条件分岐して答えを出力します。
print(x4,y4)と書くことで空白区切りで出力できます。

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

https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf

**【提出】**

```python:
# 入力の受け取り
x1,y1=map(int,input().split())
x2,y2=map(int,input().split())
x3,y3=map(int,input().split())

# x1=x2の場合
if x1==x2:
    x4=x3
# x2=x3の場合
elif x2==x3:
    x4=x1
# x3=x1の場合
elif x3==x1:
    x4=x2

# y1=y2の場合
if y1==y2:
    y4=y3
# y2=y3の場合
elif y2==y3:
    y4=y1
# y3=y1の場合
elif y3==y1:
    y4=y2

# 答えの出力
print(x4,y4)
```

# B - B. Get Closer

https://atcoder.jp/contests/abc246/tasks/abc246_b

座標から図を描くと以下のようになります。

![ABC246_B_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/700383/e287888c-df42-1a61-a6e2-8a4ad71def57.png)

内側の水色の三角形と外側の大きな三角形は相似です。
三平方の定理から外側の大きな三角形の斜辺の長さは√(A^2+B^2)ということがわかります。

求めるx,yは比を作って以下のように計算できます。
x:A=1:√(A^2+B^2)⇔x=A/√(A^2+B^2)
y:B=1:√(A^2+B^2)⇔y=B/√(A^2+B^2)

ルートの計算はmathライブラリからインポートして行います。
from math import sqrt
と書くことで、xのルートを
sqrt(x)
と計算できます。(sqrtはsquare rootの意味)

**【提出】**

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

# mathからsqrtをインポート
from math import sqrt

# 計算
x=A/sqrt(A**2+B**2)
y=B/sqrt(A**2+B**2)

# 答えの出力
print(x,y)
```

# C - Coupon

https://atcoder.jp/contests/abc246/tasks/abc246_c

どの商品にクーポンを使うべきか、まず例を考えてみましょう。
X=8のとき、10円の商品と6円の商品どちらにクーポンを使うべきでしょうか。
10円の商品に使う→2円になる(8円マイナス)
6円の商品に使う場合→0円になる(6円マイナス)
となりますので当然10円の商品にクーポンを使うほうがお得です。

具体的にはまずX円以上の商品がX円未満になるまでクーポンを使い、余ったクーポンをX円未満の商品に使う(=0円になる)という順番が最も効率的です。
ところがa円の商品がX円未満になるまでクーポンを一枚ずつ使うようシミュレーションしているとTLEします。

クーポンを一枚ずつでなく、まとめて使いましょう。
a円の商品をX円未満にするには(a//X)枚のクーポンを使えばいいです。
(例：X=5,a=12なら12//5=2枚使うと2円(=X円未満)になる)

各Aの要素について、(Ai//X)枚のクーポンを使います。
次に割引後のAを大きい順に並び替えて、余ったクーポンを使っていきます。

**【提出】**

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

# i=0~(N-1)
for i in range(N):
    # A[i]//X≤Kならば
    if A[i]//X<=K:
        # (A[i]//X)枚クーポンを使う
        K-=A[i]//X
        # 割引する
        A[i]-=(A[i]//X)*X
    # K<A[i]//Xならば(クーポンが足りなくてX円未満にできない場合)
    else:
        # 残りのクーポン(K枚)を全て使う
        A[i]-=K*X
        # クーポンを全て使ったので0枚になる
        K=0
        
# 大きい順に並び替え
A.sort(reverse=True)

# i=0~(N-1)
for i in range(N):
    # クーポンが残っている限り
    if 1<=K:
        # A[i]にクーポンを使う=0円になる
        A[i]=0
        # クーポンを1枚使った
        K-=1
    # クーポンがなくなったら
    else:
        # 終了
        break

# Aの合計=答え
print(sum(A))
```

# D - 2-variable Function

https://atcoder.jp/contests/abc246/tasks/abc246_d

a^3+a^2\*b+a\*b^2+b^3のa,bに数値を代入して実際に値を計算していきます。

まずbは固定されているものとして考えましょう。
f(a)=a^3+a^2\*b+a\*b^2+b^3とすると、この関数は単調増加です。
N≤f(a)となるもののうちで最小の値を探します。
「単調増加/減少で条件を満たすものの最大/最小」といえば二分探索です。

左端：-1(常にf(左端)<N)
右端：10^6+100(常にN≤f(右端)、最初は大きめの数にしておく)

中央=(左端+右端)/2として、
f(中央)<N→左端=中央と更新
N≤f(中央)→右端=中央と更新
これを(右端-左端)=1となるまで続けます。

(右端-左端)=1となったらf(右端)がN≤f(a)となるもののうちで最小の値となります。

b=0,1,2,...10^6まで二分探索で一番小さい値を確認し、答えを更新していきます。
※a,bは最大10^6まででいいのですがギリギリだとなにかうっかりしていた時にWAとなるのが怖いので、実装では10^6より少し大きめにしています)

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

**【提出】**

```python:
# pypyで提出

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

# 関数にする
def f(a,b):
    return a**3+a**2*b+a*b**2+b**3

# 答え
ans=10**20

# b=0,1,2,...10^6
# (10^6より少し大きめにしています)
for b in range(10**6+100):

    # 左端
    l=-1
    # 右端
    r=10**6+100

    # 1<(右端-左端)の間
    while 1<r-l:
        # 中央
        c=(r+l)//2
        # 計算結果がN未満なら
        if f(c,b)<N:
            # 左端=中央と更新
            l=c
        # 計算結果がN以上なら
        else:
            # 右端=中央と更新
            r=c

    # f(r,b)がそこまでの答えより小さければ答えを更新
    ans=min(ans,f(r,b))

# 答えの出力
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対象)**

<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