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

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

こんにちは, Shinoryoです.

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

1A - Difference Max
2B - Round Down
3C - Doubled
4D以降
5参考にしたサイト等

A - Difference Max

正解は $b - c$ となります.

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

	# 出力
	print(b-c)

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

B - Round Down

math.floorを使用すると, $X$ の値が大きすぎて誤差が発生してWAとなってしまいます.

	import math

	# 出力
	print(math.floor(float(input())))

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

そこで, 文字列型として処理して小数点を検索し, それより左側だけを取り出して出力するということをすれば, 誤差なく出力できます.

	# 入力
	X = input()

	# 小数点の位置を探す
	index = X.find('.')

	# 出力
	if index == -1:
	print(X)
	else:
	print(X[:index])

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

C - Doubled

$1$ から $N$ までの自然数に対し, その前半と後半が文字列として等しいかどうかを判定するには, $N$ が大きすぎてTLEとなってしまいます.

	# 入力
	N = int(input())

	# 答えを格納する変数
	ans = 0

	# 1からNまでの整数を全探索
	for i in range(1, N + 1):
	stri = str(i)
	leni = len(stri)
	# 桁数が偶数、かつ前後半で文字列が一致
	if leni % 2 == 0 and stri[:leni // 2] == stri[leni // 2:]:
	ans += 1

	# 出力
	print(ans)

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

そこで, $11$ , $22$ , $\dots$ , $99$ , $1010$ , $1111$ , $\dots$ , $9999$ , $100100$ , $\dots$ のように, $i$ を繰り返してできた数を順番に作り出していくことを考えます. その数が $N$ を超えたとき, $i - 1$ が答えとなります. 時間計算量は $O (N)$ になります.

	# 入力
	N = int(input())

	# 11, 22, ... , 99, 1010, 1111, ... , 9999, 100100, ...
	# のように、iを繰り返してできた数を順番に作り出していく
	# Nを超えた時点で終了し、i-1が答えになる
	i = 0
	repeatnum = 0
	while(repeatnum <= N):
	i += 1
	repeatnum = int(str(i)*2)
	print(i-1)

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

あるいは, それを二分探索で求めることもできます. $N < 10^{12}$ ですので, 初期値は $0$ と $10^{6}$ にしておけば十分でしょう. 二分探索については「SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)をPythonで解く」でも記述しています. 時間計算量は $O (\log N)$ になります.

	# 入力
	N = int(input())

	# 二分探索の初期値
	low = 0
	high = 10**6

	# 二分探索を実施
	# lowとhighの差が1になるまで続ける
	while low + 1 < high:
	# lowとhighの平均をとる(小数点以下切り捨て)
	mid = (low + high) // 2
	# midを2回繰り返した値を取得
	value = int(str(mid)*2)
	# valueがN以下であれば、lowはmid以上の値であることが分かる
	if value <= N:
	low = mid
	# そうでなければ、highはmid以下の値であることが分かる
	else:
	high = mid

	# 出力すべきはlow
	print(low)

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

さらに, 以下のように考えることもできます.

$N$ の桁数が $1$ のとき, 答えは明らかに $0$ (後の $N$ の桁数が奇数のときの処理と若干異なるので, 最初に分類しておく).
$N$ の桁数が偶数のとき, $N$ の前半部分を $M$ として取得します.
- $M$ を2回繰り返した数が $N$ より大きい場合, $M$ を2回繰り返した数は含めずに, 答えは $M - 1$ となります.
- $M$ を2回繰り返した数が $N$ 以下の場合, $M$ を2回繰り返した数を含めて, 答えは $M$ となります.
$N$ の桁数が奇数のとき, 桁数の半分(小数点以下切り捨て)だけ $9$ を繰り返した数が答えになります.

時間計算量は $O (1)$ になります.

	# 入力
	N = int(input())

	# Nの桁数を用意
	lenN = len(str(N))

	if (lenN % 2) == 0:
	# Nの桁数が偶数ならば……
	# Nの前半部分を取得
	halfN = int(str(N)[:(lenN // 2)])

	# 「halfNを2回繰り返した数」とNの大小関係で出力が決まる
	if N < int(str(halfN)*2):
	print(halfN - 1)
	else:
	print(halfN)

	elif lenN == 1:
	# Nの桁数が奇数のときの処理で、桁数が1のときだけエラーが出るので別処理
	# 1桁なら明らかに答えは0
	print(0)

	else:
	# 奇数ならば……
	# len(str(N))の半分(小数点以下切り捨て)だけ9を繰り返した数が答え
	# Nが3桁なら9(11, 22, ... , 99)が答え
	# Nが5桁なら99(上記と1000, 1111, ... , 9999)が答え
	print(int(str(int(9))*(lenN // 2)))

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

D以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 196」
Editorial - AtCoder Beginner Contest 196
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder Beginner Contest 196をPythonで解く

A - Difference Max

B - Round Down

C - Doubled

D以降

参考にしたサイト等

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