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

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

こんにちは, Shinoryoです.

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

1A - Heavy Rotation
2B - Trapezoid Sum
3C - Collinearity
4D - Hachi
5E以降
6参考にしたもの

A - Heavy Rotation

偶数なら「White」, 奇数なら「Black」を出力すれば問題ないであろう.

	n = int(input())

	if n%2 == 0:
	print("White")
	else:
	print("Black")

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

B - Trapezoid Sum

$A_{i}$ から $B_{i}$ までの整数の合計は, 等差数列の公式で

\begin{aligned} (1) & S_{i} & = \frac{(B_{i} + A_{i}) (B_{i} - A_{i} + 1)}{2} \end{aligned}

となるから, これを $N$ 個に対して合計すればよい. 2で割ったことによって変数ansがint型ではなくなってしまったので, 最後にint型にして出力している.

	n = int(input())
	ans = 0

	for i in range(n):
	a, b = [int(x) for x in input().split()]
	ans += (b+a)*(b-a+1)/2

	print(int(ans))

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

C - Collinearity

3点 $(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3})$ が1直線上にあるには, 2点 $(x_{1}, y_{1}), (x_{2}, y_{2})$ を結ぶ直線の傾きが, 2点 $(x_{1}, y_{1}), (x_{3}, y_{3})$ を結ぶ直線の傾きに等しければよい. すなわち,

\begin{aligned} (2) & \frac{(y_{2} - y_{1})}{(x_{2} - x_{1})} & = \frac{(y_{3} - y_{1})}{(x_{3} - x_{1})} \end{aligned}

となればよい. $x_{1} = x_{2}$ , $x_{1} = x_{3}$ のときにも利用できるように,

\begin{aligned} (3) & (x_{3} - x_{1}) (y_{2} - y_{1}) & = (x_{2} - x_{1}) (y_{3} - y_{1}) \end{aligned}

とすればよい.

この判定を, $N$ 個の点の組み合わせの数だけ実行すればよい. エラーにならないようにfor文の繰り返す範囲には注意されたい.

	n = int(input())
	data = [[int(item) for item in row] for row in [input().split() for _ in range(n)]]

	ans = 0

	for i in range(n-2):
	for j in range(i+1, n-1):
	for k in range(j+1, n):
	if (data[k][0] - data[i][0])(data[j][1] - data[i][1]) == (data[k][1] - data[i][1])(data[j][0] - data[i][0]):
	ans = 1

	if ans == 1:
	print("Yes")
	else:
	print("No")

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

D - Hachi

8の倍数を判定するには, 「下3桁が8で割り切れればよい」という判定方法を利用する. しかし, 愚直に実行するとTLE.

	s = int(input())
	sbunkai = []
	while s > 0:
	sbunkai.append(s%10)
	s //= 10
	sbunkai.reverse()
	n = len(sbunkai)

	ans = 1

	if n == 1:
	ans *= sbunkai[0]%8
	elif n == 2:
	ans = (sbunkai[0]10 + sbunkai[1])%8
	ans = (sbunkai[1]10 + sbunkai[0])%8
	else:
	for i in range(n):
	for j in list(set(range(n)) - set([i])):
	for k in list(set(range(n)) - set([i]) - set([j])):
	ans = (sbunkai[i]100 + sbunkai[j]*10 + sbunkai[k])%8

	if ans == 0:
	print("Yes")
	else:
	print("No")

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

そこで, リストの要素の数え上げをできるcollections.Counter()を利用する. collections.Counter()を利用することで, リストの中で「aが何個, bが何個, ……」というデータを得ることができる. 入力データの中に0はないため, 入力した数字からどれか3つを用いて112, 120, 128, ……のどれかを構成できるかを調べていけば, 計算量が少なくて済む.

1桁, 2桁の場合は別に処理する. これは単に8で割った余りで判断すればよいであろう.

	from collections import Counter

	s = input()

	if len(s) <= 2:
	if int(s)%8 == 0 or int(s[::-1])%8 == 0:
	print("Yes")
	else:
	print("No")
	exit()

	cnt = Counter(s)
	for i in range(112, 1000, 8):
	if not Counter(str(i)) - cnt:
	print("Yes")
	exit()

	print("No")

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

E以降

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

参考にしたもの

「解説 - AtCoder Beginner Contest 181」
Editorial - AtCoder Beginner Contest 181
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
ell様による「【Python】リストの要素の数え上げ, collections.Counterの使い方」
【Python】リストの要素の数え上げ, collections.Counterの使い方 - Qiita
はじめに今回はPythonのcollections.Counter()についてまとめます. AtCoderのPython3.4.3と3.8で動作確認済みです. collections.Counterについて collec...

AtCoder Beginner Contest 181をPythonで解く

A - Heavy Rotation

B - Trapezoid Sum

C - Collinearity

D - Hachi

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