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

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

こんにちは, Shinoryoです.

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

1A - Determinant
2B - Quizzes
3C - Super Ryuma
4D - increment of coins
5E以降
6参考にしたサイト等

A - Determinant

求める値は $a d - b c$ となるので, それを出力します.

	a, b = [int(x) for x in input().split()]
	c, d = [int(x) for x in input().split()]

	print(ad-bc)

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

B - Quizzes

「クイズに正解すると $1$ 点増え, 不正解だと $1$ 点減る」を律儀に行って, 出力します.

	n, x = [int(x) for x in input().split()]
	s = list(input())

	for i in range(n):
	# i番目の文字列が"o"かそうでないかを判定し, 得点に点数を加える
	if s[i] == "o":
	x += 1
	else:
	# 持っている点数が0点のときに不正解となった場合は点数は減らない
	x = max(0, x-1)

	print(x)

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

C - Super Ryuma

「超竜馬」にびびってしまいますが, 中身は意外と単純だったようです.

マス目を移動できる条件を再掲.

A： $a + b = c + d$
B： $a - b = c - d$
C： $| a - c | + | b - d | \leq 3$

移動A・Bを多くても $2$ 回(もちろん $1$ 回の場合もあります)行えば, 全マス目の半分の場所(市松模様にしたときに同じ色の場所)には移動できます. もう半分だけは, 移動A・Bに加えて移動Cが必要になります.

したがって, $0$ 回, $1$ 回, $2$ 回で移動できるかどうかを判定すれば, それ以外を $3$ 回で移動できると判定することでよくなります.

$0$ 回：同じマスかどうかの判定
$1$ 回：上記3つの移動可能条件のどれかに当てはまるかの判定
$2$ 回：
- 移動A・Bの組み合わせは $((a - c) + (b - d)) \mod 2 = 0$
- 移動C・Cの組み合わせは $| a - c | + | b - d | \leq 6$
- 移動A・Cの組み合わせは $| (a - c) + (b - d) | \leq 3$
- 移動B・Cの組み合わせは $| (a - c) - (b - d) | \leq 3$

	r1, c1 = [int(x) for x in input().split()]
	r2, c2 = [int(x) for x in input().split()]
	r = r2 - r1
	c = c2 - c1

	# 0回判定
	if (r,c) == (0,0) :
	print(0)
	# 1回判定(移動A)
	elif r == c :
	print(1)
	# 1回判定(移動B)
	elif r == -c :
	print(1)
	# 1回判定(移動C)
	elif abs(r) + abs(c) <= 3 :
	print(1)
	# 2回判定(移動A・B)
	elif (r + c) % 2 == 0 :
	print(2)
	# 2回判定(移動C・C)
	elif abs(r) + abs(c) <= 6 :
	print(2)
	# 2回判定(移動A・C)
	elif abs(r+c) <= 3 :
	print(2)
	# 2回判定(移動B・C)
	elif abs(r-c) <= 3 :
	print(2)
	# 3回判定(それ以外)
	else :
	print(3)

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

D - increment of coins

再帰関数を使うのだろうなということまでは推察できたのですが…….

金貨が $X$ 枚, 銀貨が $Y$ 枚, 銅貨が $Z$ 枚のときの操作回数の期待値を $f (X, Y, Z)$ とします. $X$ , $Y$ , $Z$ のいずれかが $100$ のときに操作が完了するので, 操作回数の期待値は $f (X, Y, Z) = 0$ となります. それ以外のときは, 各々の硬貨を引く確率を考えれば,

\begin{aligned} f (X, Y, Z) & = \frac{X}{X + Y + Z} (f (X + 1, Y, Z) + 1) \\ + \frac{Y}{X + Y + Z} (f (X, Y + 1, Z) + 1) \\ (1) & + \frac{Z}{X + Y + Z} (f (X, Y, Z + 1) + 1) \end{aligned}

となります. これを再帰関数で実装すればよいです.

実行時間が膨大になるので, 「メソッドのある引数に対する計算結果を保存しておき, 後で同じ引数が与えられた時, 計算結果を再利用する」機能であるlru_cacheを用いました. これは実行時間と引き換えにメモリを消費するということでよいのでしょうか……？

	# lru_cacheの利用
	from functools import lru_cache
	@lru_cache(maxsize=None)

	# 再帰関数の実装
	def numberexpected(g, s, b) :
	if g == 100 or s == 100 or b == 100 :
	return 0
	return (numberexpected(g+1, s, b)+1)g/(g+s+b) + (numberexpected(g, s+1, b)+1)s/(g+s+b) + (numberexpected(g, s, b+1)+1)*b/(g+s+b)

	# 数字の入力
	a, b, c = [int(x) for x in input().split()]

	# 操作回数の期待値の出力
	print(numberexpected(a, b, c))

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

あるいは, 必要な回数を全部格納した配列を作成し求めてしまおう作戦も可能でしょう(こちらの方が一般的？).

	# 数字の入力
	a, b, c = [int(x) for x in input().split()]

	# 必要な回数を全部格納した配列を作成し求めてしまおう作戦
	dp = [[[i for i in range(101)] for j in range(101)] for k in range(101)]
	for i in range(100,-1,-1):
	for j in range(100,-1,-1):
	for k in range(100,-1,-1):
	# 硬貨が全て0枚という入力はありえないが, 配列に存在してしまっているので0を格納(これがないと0除算エラー)
	if i == 0 and j == 0 and k == 0 :
	dp[i][j][k] = 0
	elif i == 100 or j == 100 or k == 100 :
	dp[i][j][k] = 0
	else:
	dp[i][j][k] = dp[i+1][j][k]i/(i+j+k) + dp[i][j+1][k]j/(i+j+k) + dp[i][j][k+1]*k/(i+j+k) + 1

	# 操作回数の期待値の出力
	print(dp[a][b][c])

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 184」
Editorial - AtCoder Beginner Contest 184
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
Kotaro Adachi様による「Python3でLRUキャッシュを用いてプログラムを高速化」
🍺Python3でLRUキャッシュを用いてプログラムを高速化 - Qiita
　卒論でPythonのプログラムを回していたが時間がかかりすぎてうんざりしていた. Python初心者の僕がいろいろ調べていたら高速化のために以下の二つに関するポストが頻繁に見られた. Numba Pythonを速くしたいときにやっ...

AtCoder Beginner Contest 184をPythonで解く

A - Determinant

B - Quizzes

C - Super Ryuma

D - increment of coins

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