AtCoder ABC246

A問題

長方形の3点の座標が与えられる。残りの一点の座標を求めるも問題

• 排他的論理和の以下の性質を使用する。
  • a ^ a = 0
  • a ^ 0 = a
  • a ^ (b ^ c) = (a ^ b) ^ c

#それぞれの座標を(x1, x1), (x2, y2), (x3, y3)とする。

x_ans = x1 ^ x2 ^ x3
y_ans = y1 ^ y2 ^ y3
print(x_ans, y_ans)

なおif式でも普通に回答可能

x_ans = 0
y_ans = 0

if (x1 == x2):
    x_ans = x3
elif (x2 == x3):
    x_ans = x1
else:
    x_ans = x2

if (y1 == y2):
    y_ans = y3
elif (y2 == y3):
    y_ans = y1
else:
    y_ans = y2

print(x_ans, y_ans)

B問題

原点から点(A, B)方向に向かって長さが1になる点の座標を求める問題

• 原点と点(A, B)の線分の長さをdとすると、求める点の座標は(A/d, B/d)となる。

# A, B
import math
d = math.sqrt(A*A + B*B)

x = A / d
y = B / d

print(x, y)

C問題

• N個の商品の値段Anが分かっている。
• X円分のクーポンをK毎持っていて、一つの商品に対して、0枚以上のクーポンを使用することができる。
• クーポンを使用すると値段aの商品に対して、max{a-kx, 0}で購入できる。
• 一番安く購入できるとすると、何円になる？

max{a-kx, 0}なので例えば10円のクーポンが1枚あり、9円の商品、8円の商品がある場合9円の商品にクーポンを使用したほうが支払総額は8円で済む。

方針は以下

• 各商品の値段とクーポンの値段(X)の商を求める。
  • 割り切れた分はクーポンが残っているのならば使う。(1)
• 各値段の値段とクーポンの値段(X)の余りを求める。
  • (1)でクーポンが残っている場合、余りが小さい商品にクーポンを使用する。

# N, K, X    N: 商品の数、K: クーポンの数、X: クーポンの値段
# A  A: 各商品の値段リスト

sum_A = 0 # クーポンを使用しない場合の値段の合計
used = 0 # 余りなしに使用したクーポンの数
rem_list = # // 余りを格納する

for i in A:
    sum_A += i
    div = i
    temp_used = used
    rem = i % X
    if (rem != 0):
        rem_list.append(rem) 
    if div == 0:
        continue

    # クーポンの残り枚数を考慮する。
    if temp_used + div > K:
        used = K # クーポン数が足りないのですべて使用したとする。
        continue
    used += div

# 余りの昇順
rem_list.sort(reverse=True)

if (used == K):
    # 使用できるクーポンがもうない場合
    print(sum_A - K * X)
else:
    # 使用できるクーポンがある場合
    # 余りが少ない商品に適用する。
    remainK = K - used # 残りクーポン枚数
    sub = sum(rem_list[:remainK])
    print(sum_A - used * X - sub)

なるべく単一ループで済むように実装してたら結構実装に時間がかかった。

感想

約一年ぶりにAtCoderやってみた。
C問題までは何とか解けた。
ただ特にアルゴリズムとを使わなくてもできる問題だったから運が良かったのかも。。
アルゴリズムしっかり勉強していくぞ✌️
(D以上も解説できるように頑張ります。。)