キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はキャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Discount
2B - Play Snuke
3C - Unexpressed
4D - Poker
5E以降
6参考にしたサイト等

A - Discount

$(A - B) / A$ の $100$ 倍を計算します.

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

	# 出力
	print((A - B) * 100 / A)

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

B - Play Snuke

高橋くんがスヌケマシンを買うことができる条件は, $X_{i} > A_{i}$ となります. そのような店 $i$ における販売価格 $P_{i}$ の最小値を求めればよいです. $P_{i}$ の最大値は $10^{9}$ なので, 答えの初期値を $10^{9} + 1$ にしてそれが更新されなかった場合は $- 1$ にするようにしています.

	# 入力
	N = int(input())
	A = []
	P = []
	X = []
	for _ in range(N):
	tempA, tempP, tempX = [int(x) for x in input().split()]
	A.append(tempA)
	P.append(tempP)
	X.append(tempX)

	# 答えを格納する変数
	ans = 10**9 + 1

	# 買えるかどうか調査
	for i in range(N):
	if X[i] - A[i] > 0:
	ans = min(ans, P[i])

	# 買えなかったら？
	if ans == 10**9 + 1:
	ans = -1

	# 出力
	print(ans)

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

C - Unexpressed

$N$ までの自然数のうち, $2$ 以上の整数 $a$ , $b$ を用いて $a^{b}$ と表すことができないものの数を求める問題です. $a^{b}$ と表すことができるものの数を求める方が楽そうだということは容易に想像できるでしょう.

全ての $2 \leq a \leq N$ に関して探索するコードがこちらです. 各 $a$ に対して $b$ を $2$ から順に調べていき, $a^{b} \leq N$ になるまで続けます. それを, $2 \leq a \leq N$ に関してループします. $N \leq 10^{10}$ なので当然TLEです.

	# 入力
	N = int(input())

	# 空集合を用意
	set_ruijo_kanou = set()

	# 累乗で表現できる数を追加していく
	for i in range(2,N+1):
	if i in set_ruijo_kanou:
	continue
	j = i**2
	while j < N + 1:
	set_ruijo_kanou.add(j)
	j *= i

	# 答えを出力
	print(N - len(set_ruijo_kanou))

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

そこで, $a$ の範囲は実際には $2 \leq a \leq \sqrt{N}$ に絞れることを利用します. 実際, $b \geq 2$ なので, $a > \sqrt{N}$ に対しては必ず $a^{b} > N$ となってしまいます.

$\sqrt{N} \leq 10^{5}$ なので, これだけでかなり時間計算量を減らすことができますね. 時間内に思いつきたかった.

	# 入力
	N = int(input())

	# Nの正の平方根を用意
	sqN = int(N**0.5)

	# 空集合を用意
	set_ruijo_kanou = set()

	# 累乗で表現できる数を追加していく
	for i in range(2,sqN+1):
	if i in set_ruijo_kanou:
	continue
	j = i**2
	while j < N + 1:
	set_ruijo_kanou.add(j)
	j *= i

	# 答えを出力
	print(N - len(set_ruijo_kanou))

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

D - Poker

残っているカードを調べて全探索すればええやんけ！ってやると当然TLEです. 配列card_remainに, $1$ から $9$ までのカードがそれぞれ何枚残っているかを格納し, それを配列card_remain_cardに実際のカードを模して表現(card_remainが[1,1,2,1,1,2,1,1,2]なら, card_remain_cardには[1,2,3,3,4,5,6,6,7,8,9,9]が入ります)し, card_remain_cardから $2$ つを選ぶ場合をitertools.permutationsで書きだします.

	import itertools

	# 入力
	K = int(input())
	S = input()
	T = input()

	# 9個のKの配列を用意
	card_remain = [K]*9

	# 高橋くんのカードを格納する配列
	takahashi_card = [0]*9
	# 青木くんのカードを格納する配列
	aoki_card = [0]*9
	# それぞれ格納
	for i in range(4):
	takahashi_card[int(S[i]) - 1] += 1
	aoki_card[int(T[i]) - 1] += 1

	# 高橋くんと青木くんの持っているカードをcard_remainから減らす
	for i in range(9):
	card_remain[i] -= takahashi_card[i] + aoki_card[i]

	# 残っているカードを表した配列
	card_remain_card = []
	for i in range(9):
	for _ in range(card_remain[i]):
	card_remain_card.append(i + 1)

	# 高橋くんが勝つ場合の数を格納
	ans = 0
	# 全場合の数を格納
	alll = 0

	# 残っているカードを全探索
	for i, j in itertools.permutations(card_remain_card, 2):
	# 高橋くんと青木くんのカードに追加
	takahashi_card[i - 1] += 1
	aoki_card[j - 1] += 1
	# 高橋くんと青木くんの点数を初期化
	takahashi_score = 0
	aoki_score = 0
	# 高橋くんと青木くんの点数を計算
	for k in range(9):
	takahashi_score += (k + 1) * (10**takahashi_card[k])
	aoki_score += (k + 1) * (10**aoki_card[k])
	# 高橋くんが勝ったらansに+1
	if takahashi_score > aoki_score:
	ans += 1
	# 全場合の数に+1
	alll += 1
	# 高橋くんと青木くんのカードを戻す
	takahashi_card[i - 1] -= 1
	aoki_card[j - 1] -= 1

	print(ans / alll)

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

そこで, 頭を使って考えることにします.

まず, 残っているカードは $(9 K - 8)$ 枚になるはずです. これを高橋くんと青木くんに配る場合の数は, $(9 K - 8) (9 K - 9)$ となります.

残っている $i$ のカードを $C_{i}$ ( $1 \leq i \leq 9$ )とします. 高橋くんに $x$ のカード, 青木くんに $y$ のカードを配る場合の数は当然 $\begin{array}{r} (1) & {\begin{aligned} C_{x} C_{y} (x \neq y), \\ C_{x} (C_{x} - 1) (x = y) \end{aligned} \end{array}$ となります. このことを利用すれば, 残ったカードから $2$ つを選ぶ場合をitertools.permutationsで書きだすなんてことをしなくてもよいですね.

	# 入力
	K = int(input())
	S = input()
	T = input()

	# 残っているカードを格納する配列(1が何個、2が何個、……)
	card_remain = [K]*9

	# 高橋くんのカードを格納する配列(1が何個、2が何個、……)
	takahashi_card = [0]*9
	# 青木くんのカードを格納する配列(1が何個、2が何個、……)
	aoki_card = [0]*9
	# それぞれ格納
	for i in range(4):
	takahashi_card[int(S[i]) - 1] += 1
	aoki_card[int(T[i]) - 1] += 1

	# 高橋くんと青木くんの持っているカードをcard_remainから減らす
	for i in range(9):
	card_remain[i] -= takahashi_card[i] + aoki_card[i]

	# 高橋くんが勝つ場合の数を格納
	ans = 0
	# 全場合の数を格納
	alll = (9K - 8) (9*K - 9)

	# 高橋くんに配るカードに関してループ
	for i in range(9):
	# 青木くんに配るカードに関してループ
	for j in range(9):
	# 高橋くんと青木くんのカードに追加
	takahashi_card[i] += 1
	aoki_card[j] += 1
	# 高橋くんと青木くんの点数を初期化
	takahashi_score = 0
	aoki_score = 0
	# 高橋くんと青木くんの点数を計算
	for k in range(9):
	takahashi_score += (k + 1) * (10**takahashi_card[k])
	aoki_score += (k + 1) * (10**aoki_card[k])
	# 高橋くんが勝ったらansにその場合の数を加える
	if takahashi_score > aoki_score:
	if i == j:
	ans += card_remain[i] * (card_remain[i] - 1)
	else:
	ans += card_remain[i] * card_remain[j]
	# 高橋くんと青木くんのカードを戻す
	takahashi_card[i] -= 1
	aoki_card[j] -= 1

	# 出力
	print(ans / alll)

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

E以降

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

参考にしたサイト等

「解説 - キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)」
Editorial - Caddi Programming Contest 2021(AtCoder Beginner Contest 193)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)をPythonで解く

A - Discount

B - Play Snuke

C - Unexpressed

D - Poker

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