More than 1 year has passed since last update.

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

Last updated at 2022-08-09Posted at 2022-04-04

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

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

A - Four Points

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

まずは図を描いてみましょう。

この図の場合だと
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)と書くことで空白区切りで出力できます。

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

【提出】

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

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

内側の水色の三角形と外側の大きな三角形は相似です。
三平方の定理から外側の大きな三角形の斜辺の長さは√(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の意味)

【提出】

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

どの商品にクーポンを使うべきか、まず例を考えてみましょう。
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を大きい順に並び替えて、余ったクーポンを使っていきます。

【提出】

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

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で提出します。

【提出】

# 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