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

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

こんにちは, Shinoryoです.

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

1A - Very Very Primitive Game
2B - Magic 3
3C - Bowls and Dishes
4D - Staircase Sequences
5E以降
6参考にしたサイト等
7脚注

A - Very Very Primitive Game

愚直に条件を確認します. 基本的にはアメの個数が多い人の勝ちで, アメの個数が同じ場合にはどちらが先手かによって変わります.

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

	# 愚直に条件に合うかどうかを確認
	if a > b:
	print("Takahashi")
	elif a < b:
	print("Aoki")
	else:
	if c == 0:
	print("Aoki")
	else:
	print("Takahashi")

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

B - Magic 3

各魔法に対して, ダメージを与えられる条件を満たしているかを順に確かめていきます.

	# 1行目の入力
	n, s, d = [int(x) for x in input().split()]

	# 各魔法に関して, ダメージを与えられるかどうかを確かめる
	for i in range(n):
	# 魔法データの入力
	x, y = [int(x) for x in input().split()]
	# ダメージが通るか判定
	# 通ったらYesを出力し終了
	# 通らなかったらループ続行
	if x < s and y > d:
	print("Yes")
	exit()

	# 全魔法でダメージを与えられないときNoを出力
	print("No")

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

C - Bowls and Dishes

$1 \leq K \leq 16$ であり, ボールが置かれる場合の数(重複あり)は $2 \leq 2^{K} \leq 65536$ であるので, ボールが置かれる場合を全探索しても問題ないでしょう.

各ボールの置き方に対して, そのボールの置き方で各条件を満たすことができるかを確認し, 結果条件を満たすことができた個数を数えます. その最大値を出力すればよいです.

	import itertools

	# 入力
	n, m = [int(x) for x in input().split()]
	abmatrix = [[int(x) for x in input().split()] for _ in range(m)]
	k = int(input())
	cdmatrix = [[int(x) for x in input().split()] for _ in range(k)]

	# 答えを入力
	ans = 0

	# ボールの置き方全てを全探索
	for balls in itertools.product(*cdmatrix):
	# 満たすことができる条件数を計算
	cnt = sum(a in balls and b in balls for a, b in abmatrix)
	# ansよりcntが大きければ, ansを更新
	if ans < cnt:
	ans = cnt

	# 答えを出力
	print(ans)

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

D - Staircase Sequences

初項 $A$ , 末項 $B$ ( $A \leq B$ ), 公差 $1$ の等差数列の和は,

\begin{aligned} (1) & N & = \frac{(A + B) (B - A + 1)}{2} \end{aligned}

です. よって, この問題は,

\begin{aligned} (2) & (A + B) (B - A + 1) & = 2 N \end{aligned}

の整数解 $A$ , $B$ を求める問題になります.

$A + B$ , $B - A + 1$ はともに自然数になります^*1ので, どちらも $2 N$ の正の約数になります. $2 N$ を正の約数 $x$ , $y$ に分解できたとして,

\begin{array}{r} (3) & {\begin{aligned} A + B = x \\ B - A + 1 = y \end{aligned} \end{array}

を $A$ , $B$ について解くと,

\begin{array}{r} (4) & {\begin{aligned} A = \frac{x - y + 1}{2} \\ B = \frac{x + y - 1}{2} \end{aligned} \end{array}

となります. もし, $x$ と $y$ の偶奇が同じなら, $A$ , $B$ は整数になりません. したがって, $x$ と $y$ の偶奇は異なる必要があります. よって, この問題は, $2 N$ を偶奇の異なる2つの自然数 $x$ , $y$ に分解する問題になります.

また, $2 N$ は $2$ を必ず素因数に含みますが, その $2$ という素因数は $x$ と $y$ のどちらか一方にしか含まれることができません. 仮に,

$M$ は $N$ を $2$ で割り切れなくなるまで割った数であるとし,
$M$ の約数を $d_{1} = 1$ , $d_{2}$ , $d_{3}$ , $d_{4} = M$ であるとし^*2,
$x$ に $2$ という素因数が含まれるとする

と, $y$ として当てはまるのは $d_{1}$ , $d_{2}$ , $d_{3}$ , $d_{4}$ のみです^*3. $x$ と $y$ が入れ替わった場合も考えると, 求める値は $M$ の約数の $2$ 倍になります.

	# 入力
	n = int(input())

	# nから因数2を消去する
	# 消去した回数を知る必要はない
	while(n % 2 == 0):
	n //= 2

	# nの約数の個数を調べる
	# その2倍が答えである
	sqn = int(n**(0.5))
	print((sum(n % i == 0 for i in range(1, sqn + 1)) * 2 - (sqn * sqn == n)) * 2)

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 190」
Editorial - AtCoder Beginner Contest 190
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様の「Pythonで複数のリストの直積（デカルト積）を生成するitertools.product」
Pythonで複数のリストの直積（デカルト積）を生成するitertools.product | note.nkmk.me
Pythonで複数のリストの直積（デカルト積）を生成するにはitertools.product()を使う. 10.1. itertools.product() — 効率的なループ実行のためのイテレータ生成関数 — Python 3.6.5 ドキュメントここでは以下の内容について説明する. 直積（デカルト積）とは itertools.product()の基本的な使い方同じリストを繰り返し...

脚注

*1 : $A$ と $B$ がどちらも自然数である場合, これは明らかです. また, $A$ と $B$ がどちらも自然数ではないとすると, 等差数列の和が自然数にならないのであり得ません. $B$ だけが自然数だとすると, 以下のようになります.

$| A | < | B |$ の場合：等差数列の和は自然数になり, $A + B$ , $B - A + 1$ はともに自然数になります.
$| A | \geq | B |$ の場合：等差数列の和が自然数にならないのであり得ません.

したがって, $A + B$ , $B - A + 1$ はともに自然数になります.

*2 : もちろん何個だとしても問題ないです.

*3 : $x$ には各 $y$ に対して適切な値が当てはまります.

AtCoder Beginner Contest 190をPythonで解く

A - Very Very Primitive Game

B - Magic 3

C - Bowls and Dishes

D - Staircase Sequences

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