AtCoder Beginner Contest 246をPythonで解く-Shinoryo's Weblog

Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 246を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Four Points
- 1.1解法パターンA
- 1.2解法パターンB(こちらの方が標準的っぽい)
2B - Get Closer
3C - Coupon
4D - 2-variable Function
5E以降
6参考にしたサイト等

A - Four Points

解法パターンA

$x$ 座標のリスト, $y$ 座標のリストを用意し, それぞれのリストで登場回数が $1$ 回の座標の組み合わせが求める座標になります. リストにおける登場回数を調べるには, collectionsのCounterを用いるとよいです.

	import collections

	# 入力
	x_zahyou = []
	y_zahyou = []
	for _ in range(3):
	x_zahyou_temp, y_zahyou_temp = [int(x) for x in input().split()]
	x_zahyou.append(x_zahyou_temp)
	y_zahyou.append(y_zahyou_temp)

	# x座標の出てくる回数をカウントし、
	# 最も少ないものの座標値を取得
	x_count = collections.Counter(x_zahyou)
	x_ans = x_count.most_common()[-1][0]

	# y座標の出てくる回数をカウントし、
	# 最も少ないものの座標値を取得
	y_count = collections.Counter(y_zahyou)
	y_ans = y_count.most_common()[-1][0]

	# 出力
	print(x_ans, y_ans)

view raw atcoder-abc-246-a.py hosted with ❤ by GitHub

解法パターンB(こちらの方が標準的っぽい)

上記の「登場回数が $1$ 回の座標の組み合わせ」というのを, 別の方法で求めます. 入力する $x$ 座標を $x_{1}, x_{2}, x_{3}$ , 求めるべき $x$ 座標を $x_{ans}$ とします.

$x_{1} = x_{2}$ ならば, $x_{ans} = x_{3}$
$x_{1} = x_{3}$ ならば, $x_{ans} = x_{2}$
$x_{2} = x_{3}$ ならば, $x_{ans} = x_{1}$

以上のようにして, $x_{ans}$ を求めることができます. 問題文にある「制約」から, この3つのどれか1つにかならず当てはまります.

$y$ 座標についても同様になります.

	# 入力
	x_zahyou = []
	y_zahyou = []
	for _ in range(3):
	x_zahyou_temp, y_zahyou_temp = [int(x) for x in input().split()]
	x_zahyou.append(x_zahyou_temp)
	y_zahyou.append(y_zahyou_temp)

	# x座標を求める
	if x_zahyou[0] == x_zahyou[1]:
	x_ans = x_zahyou[2]
	elif x_zahyou[0] == x_zahyou[2]:
	x_ans = x_zahyou[1]
	else:
	x_ans = x_zahyou[0]

	# y座標を求める
	if y_zahyou[0] == y_zahyou[1]:
	y_ans = y_zahyou[2]
	elif y_zahyou[0] == y_zahyou[2]:
	y_ans = y_zahyou[1]
	else:
	y_ans = y_zahyou[0]

	# 出力
	print(x_ans, y_ans)

view raw atcoder-abc-246-a-2.py hosted with ❤ by GitHub

B - Get Closer

求めるのは,

\begin{array}{r} (1) & (\frac{A}{\sqrt{A^{2} + B^{2}}}, \frac{B}{\sqrt{A^{2} + B^{2}}}) \end{array}

になります.

	# 入力
	A, B = [int(x) for x in input().split()]

	# 出力
	print(A / (((A2) + (B2))(1/2)), B / (((A2) + (B2))(1/2)))

view raw atcoder-abc-246-b.py hosted with ❤ by GitHub

C - Coupon

クーポンによる値下げには, 以下の2つのタイプがあります. クーポン使用前の値段を $a$ 円とします.

タイプ1： $a \geq X$ のときは, $a$ から $X$ 円ぴったりが引かれる.
タイプ2： $a < X$ のときは, $a$ から $a$ 円のみが引かれる.

全商品を買うための合計費用を最小化するためには, より効率的にクーポンを使用していく, つまりタイプ1の値下げをできる限り行った後に, タイプ2の値下げを行えばよいわけです.

タイプ1の値下げに関して考えます. $i$ 番目の商品に関して $A_{i}$ から $X$ をできる限り引くことを考えるわけですが, 可能な回数は

\begin{array}{r} (2) & ⌊ \frac{A_{i}}{X} ⌋ \end{array}

となります(ただし, $⌊ x ⌋$ はGauss記号であり, $x$ を超えない最大の整数). クーポンは $K$ 枚しかありませんので, タイプ1の値下げに使えるクーポンの枚数は

\begin{array}{r} (3) & min {\sum_{i = 1}^{N} ⌊ \frac{A_{i}}{X} ⌋, K} \end{array}

となります.

タイプ2の値下げに関して考えます. タイプ1のような値下げを全て仕切ってなお, クーポンが余っている場合を考えますので, $A_{i}$ は全て $X$ で割った余りに変換してしまいます. その上で, $A_{i}$ を大きい順にソートして, クーポンがある限り順番にタイプ2の値下げを行っていきます.

以上により, 全商品を買うための最小合計費用を求めることができます.

	# 入力
	N, K, X = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	# 最後の出力のため
	A_original = [a for a in A]

	# 使うクーポン数を格納
	use_coupon = 0
	# 減額できる値段を格納
	discount = 0

	# A_1から順番に0円を下回らない範囲でクーポンを適用する
	for i in range(N):
	if A[i] >= X:
	use_coupon += (A[i] // X)

	# 使うクーポンはKより小さくなければならない
	use_coupon = min(use_coupon, K)
	# 残りクーポン数を計算
	K -= use_coupon
	# ここまでで減額できる額を計算
	discount = use_coupon * X

	# ここまでクーポンを使った後の端数の処理
	# 大きいのから順に引いていきたいので、端数を計算した後でソートする
	for i in range(N):
	A[i] %= X
	A.sort(reverse=True)
	# クーポンがある限り、大きい端数から消していく
	for i in range(N):
	if A[i] > 0 and K > 0:
	K -= 1
	discount += A[i]

	# 出力
	print(sum(A_original) - discount)

view raw atcoder-abc-246-c.py hosted with ❤ by GitHub

D - 2-variable Function

ある整数 $X$ が条件に当てはまるかを考えるのは非常に難しいので, さまざまな $a, b$ に対して $f (a, b) = a^{3} + a^{2} b + a b^{2} + b^{3}$ の値を格納したリストを用意して, そのリストの中から $N$ 以上の最小の整数を持ってきて $X$ にすることが考えられます. さらに具体的に手法を詰めていくと, 固定された $a$ に対して $f (a, b)$ が $b$ に関して単調増加であることを利用して, 以下のように求められます.

答えの初期値として, $ans$ を無限大で用意する.
$a$ の値を定める( $0$ から $10^{6}$ までループ).
1. $b = 0$ として $f (a, b)$ の値を求める.
2. $f (a, b) < N$ の場合は, $b + = 1$ として上に戻る.
3. $f (a, b) \geq N$ の場合は, $ans = min (ans, f (a, b))$ のように更新して, $b$ に関するループを終了する.
結果として得られる $ans$ が答え.

なお, $N = 10^{18}$ であり, $a = 10^{6}$ , $b = 0$ とすると $f (a, b) = 10^{18}$ であるので, $a$ , $b$ の調べる範囲は $0$ から $10^{6}$ まででいいことが分かることを利用しています. しかし, それらの全範囲を探索しているだけではとても時間が足りません.

そこで, $a$ に関するループはそのままに, 固定された $a$ に対して $f (a, b)$ が $b$ に関して単調増加であることをさらに利用して, 二分探索(binary search)を用いることを考えます.

ある $low$ (適切な $b$ がある範囲の下限)とある $high$ (適切な $b$ がある範囲の上限)の値を用意する.
$low$ と $high$ の真ん中の値として, $mid = (low + high) / 2$ を用意する.
$f (a, mid)$ を求める.
$f (a, mid)$ の値によって, 以下のように分類する.
- $f (a, mid) < N$ の場合は, $b$ としては $mid$ より大きい値を取ることになるので, $low = mid$ とする.
- $f (a, mid) \geq N$ の場合は, $b$ としては $mid$ 以下の値を取ることになるので, $high = mid$ とする.
$low$ と $high$ の差が $1$ になるまで, これを繰り返す.

このようにしていくことで, 最終的に $high$ が, 固定された $a$ に対して適切な $b$ になります. 答えの初期値として, $ans$ を無限大で用意して, 各 $a$ に対してループしていく過程で $f (a, high)$ によって $ans$ を更新していけば, 最終的な $ans$ が求める答えとなります.

	# 入力
	N = int(input())

	# a,bからa^3+a^2b+ab^2+b^3を求める関数
	def func(a, b):
	return (a3) + (a2) * b + a * (b2) + (b3)

	# 答えを格納する変数
	ans = float("inf")

	# X = a^3+a^2b+ab^2+b^3を満たすXに関して、N以上で最小のものを探す
	# 10^18がXの条件を、a = 10^6、b = 0で満たすので、aとして0~10^6を探索する
	for a in range(0, (10**6) + 1):
	# bに関しても0~10^6を探索する
	# bに関してはf(a, b)が単調増加なので、二分探索を行う
	low = -1 # 答えになるhighが0をとりうるように、-1にする
	high = 10**6
	# 二分探索を実施
	# lowとhighの差が1になるまで続ける
	while low + 1 < high:
	# lowとhighの平均をとる(小数点以下切り捨て)
	mid = (low + high) // 2
	# f(a, mid)の値を取得
	value = func(a, mid)
	# value < Nであれば、lowはmid以上の値であることが分かる
	if value < N:
	low = mid
	# value >= Nであれば、highはmid以下の値であることが分かる
	else:
	high = mid
	# 得られたhighが、ansになりうるb
	# (func(a, high) >= Nで、highは限りなく小さい)
	# ansを更新する
	ans = min(ans, func(a, high))

	# 出力
	print(ans)

view raw atcoder-abc-246-d.py hosted with ❤ by GitHub

二分探索については「SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)をPythonで解く」でも取り上げていますので, ぜひご覧ください.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

「解説 - AtCoder Beginner Contest 246」
Editorial - AtCoder Beginner Contest 246
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「PythonのCounterでリストの各要素の出現個数をカウント」
PythonのCounterでリストの各要素の出現個数をカウント | note.nkmk.me
Pythonでリストやタプルの全要素の個数は組み込み関数len(), 各要素の個数（要素ごとの出現回数）はcount()メソッドで取得できる. さらに, Python標準ライブラリcollectionsのCounterクラスを使うと, 出現回数が多い順に要素を取得できたりする. ここでは, 全要素数をカウント: len() 各要素の個数（要素ごとの出現回数）を...

AtCoder Beginner Contest 246をPythonで解く

A - Four Points

解法パターンA

解法パターンB(こちらの方が標準的っぽい)

B - Get Closer

C - Coupon

D - 2-variable Function

E以降

参考にしたサイト等

0 件のコメント:

コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)

Search

About Me

Labels

Blog Archives

Twitter