AtCoder Beginner Contest 246 A~C 3完記事

アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.

A - Four Points

問題文　概要

長方形の$3$点が与えられる.残りの$1$点はなにか.

制約と入力

制約

$-100 \leq x_i,y_i \leq 100$
$(x_1,y_1),(x_2,y_2),(x_3,y_3)$のすべてを頂点に持つ長方形がただ一つ存在し,その各辺は$x$軸または$y$軸に平行であり,面積は$0$ではない
入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。
$Ax_1 \ \ y_1$
$Ax_2 \ \ y_2$
$Ax_3 \ \ y_3$

考察

$x_1,x_2,x_3$の排他的論理和を求めると,対にならないただ一つが決まる.
同様に,$y_1,y_2,y_3$の排他的論理和を求める.
排他的論理和は$x_1 \oplus x_1=0$になることに注意したい.
これが答えになる.

サンプルコード

a.py

x1,y1=map(int,input().split())
x2,y2=map(int,input().split())
x3,y3=map(int,input().split())
print(x1^x2^x3,y1^y2^y3)

B - Get Closer

問題文　概要

座標平面上の原点から$A,B$に線分を引く.原点からの距離が$1$となる座標はなにか.

制約と入力

制約

$0 \leq A,B \leq 1000$
$(A,B) \neq (0,0)$
入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。
$A \ \ B$

考察

ベクトルの正規化をすればよい.
大きさで割れば答えが求まる.

サンプルコード

b.py

import math
A,B=map(int,input().split())
norm=math.sqrt(A**2+B**2)
print(A/norm,B/norm)

C - Coupon

問題文　概要

クーポンを使ってできるだけ安く買い占めたい.
商品は$N$個あり,$1$枚当たり$X$円やすくなる.
商品に$A=A_1,A_2,\dots,A_i,\dots,A_N$と識別番号を割り当てる.
$K$枚のクーポン券があり,$a$円の商品に$k$枚のクーポンを使った値段は$\max(a-kX,0)$円である.

制約と入力

制約

$1 \leq N \leq 2\times 10^5$
$0 \leq K,X \leq 10^9$
$1\leq A_i \leq 10^9$
入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。
$N \ K \ X$
$A_1 \ A_2 \ \dots \ \ A_N $

考察

安く買うを言い換えると割引額を大きくするとなる.
クーポン$1$枚当たり$X$円まで割引がある.
$0 \leq i \leq N $の各$A_i$が$X$円未満になるまでクーポンの枚数分割引を行う.
この時、途中でクーポン券がなくなった場合は割引を終了する.
$A_N$まで割引を続け,クーポン券が余っている時は,$A$の大きいものからクーポンの枚数分割引を行える.
クーポンは過剰となってもよい.

サンプルコード

c.py

N,K,X=map(int,input().split())
A=list(map(int,input().split()))
for i in range(N):
    if A[i]>X:
        cnt=A[i]//X
        if cnt>K:
            cnt=K
        A[i]-=cnt*X
        K-=cnt
A.sort()
A.reverse()
for i in range(min(len(A),K)):
    A[i]=0
print(sum(A))