SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

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

1A - Star
2B - uNrEaDaBlE sTrInG
3C - Kaprekar Number
4D - Base n
5E以降
6参考にしたサイト等

A - Star

求めるのは, $X$ を $100$ で割った余りを $100$ から引いた値です.

	# 出力
	print(100 - (int(input()) % 100))

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

B - uNrEaDaBlE sTrInG

文字列 $S$ から奇数番目を取り出した文字列と偶数番目を取り出した文字列を用意します.

文字列の中の文字が大文字か小文字かを判定するには, .islower()や.isupper()を使用します.

.islower()は, 以下の2つの条件がどちらも満たされる場合, Trueを返します. そうでなければFalseを返します.

文字列中に大文字と小文字の区別のある文字が1文字以上存在する.
その大文字と小文字の区別のある文字の全てが小文字である.

.isupper()は, 以下の2つの条件がどちらも満たされる場合, Trueを返します. そうでなければFalseを返します.

文字列中に大文字と小文字の区別のある文字が1文字以上存在する.
その大文字と小文字の区別のある文字の全てが大文字である.

偶数番目を取り出した文字列に関する判定には注意が必要です. 文字列 $S$ が1文字の場合, 偶数番目を取り出した文字列としては, おそらく何もない空白の文字列が用意されるはずです. そうすると, .isupper()としてはFalseが返ってきてしまうので, 偶数番目を取り出した文字列が空白である可能性を考慮しなければなりません.

	# 入力
	S = input()

	# Sの長さを格納
	Slength = len(S)

	# 奇数番目だけ、偶数番目だけを用意
	Seven = ""
	Sodd = ""
	for i in range(0, Slength, 2):
	Seven += S[i]
	for i in range(1, Slength, 2):
	Sodd += S[i]

	# 判定
	if Seven.islower() and (Sodd.isupper() or not(Sodd)):
	print("Yes")
	else:
	print("No")

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

C - Kaprekar Number

意外にも, 問題文にあることをそのまま実行すれば通ります. 「各桁の数字を大きい順に並び替えて」「各桁の数字を小さい順に並び替えて」には, 整数型を文字列型にして, その各文字を整数型にしてソートすればよいです.

	# 整数列Sintlist_funcを入力されて、10進法におけるSintlist_funcの値を出力する関数
	def Nshinhou(Sintlist_func):
	output = 0
	for i in Sintlist_func:
	output = output * 10 + i
	return output

	# 整数iを入力されてg_1(i)を出力する関数
	def g_1(i):
	i_descending = sorted([int(x) for x in str(i)], reverse=True)
	return Nshinhou(i_descending)

	# 整数iを入力されてg_2(i)を出力する関数
	def g_2(i):
	i_ascending = sorted([int(x) for x in str(i)])
	return Nshinhou(i_ascending)

	# 整数iを入力されてf(i)を出力する関数
	def f(i):
	return g_1(i) - g_2(i)

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

	# 操作
	for _ in range(K):
	N = f(N)

	# 出力
	print(N)

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

D - Base n

$N$ 進法における $X$ の値を出力する関数を用意するのは, 「C - Kaprekar Number」と同じなのでそこまで難しくはないでしょう.

$N$ 進数の $N$ が大きいほど2桁目以降の表す値が大きくなっていくので, $N$ を大きくすればするほど $X$ の値は大きくなる(狭義単調増加)ということになります. よって, 二分探索(binary search)を用いることができます.

ここで用いる二分探索の概要

二分探索とは, ソート済みのリストに対する検索を行うにあたって有用なアルゴリズムです.

ある $low$ とある $high$ の値を用意します.
$low$ と $high$ の真ん中の値として $mid = (low + high) / 2$ をとります.
$mid$ 進法における $X$ の値を確認します.
- $mid$ 進法における $X$ の値が $M$ 以下である(つまり, 条件を満たす)ならば, $low = mid$ とします(次は, より大きい値を確認します).
- $mid$ 進法における $X$ の値が $M$ より大きい(つまり, 条件を満たさない)ならば, $high = mid$ とします(次は, より小さい値を確認します).
$low$ と $high$ の差が $1$ になるまで上の作業を続けます.

このようにして得られた $low$ と $high$ について, $low$ 以下では条件を満たし, $high$ 以上では条件を満たさないということになるので, 求める値は $low - d$ (ただし, $d$ は $X$ に含まれる最も大きい数字)となります.

lowとhighの初期値

二分探索を行うにあたって, $low$ と $high$ の初期値を検討する必要があります.

$low$ ： $d$ を採用します. もし $(d + 1)$ 以上の全ての $N$ に対して, $N$ 進法における $X$ の値が $M$ より大きい(つまり, 条件を満たさない)場合は $low = d$ となり, 出力される値は $d - d = 0$ となります.
$high$ ： $M + 1$ を採用します. 後述するように, $X$ が2桁以上の場合(つまり, $X = 10$ 以上)に対して二分探索を適用します. すると, $M$ 進法における $X$ の値は必ず $M$ 以上になります. よって, $(M + 1)$ 進法における $X$ の値は必ず $M$ より大きくなります.

細かい場合の補足

そもそもが $low + 1 >= high$ の場合： $(d + 1)$ 以上の全ての $N$ に対して, $N$ 進法における $X$ の値が $M$ より大きくなります. 下のコード例では「while low + 1 < high」として, $low + 1 >= high$ の場合には二分探索を行わず $low = d$ となるようになっています.
$X$ が1文字の場合：二分探索は使えないので, 最初に場合分けしておく必要があります.

	# 整数列Xintlist_funcと底N_funcを入力されて、N_func進法におけるXintlist_funcの値を出力する関数
	def Nshinhou(Xintlist_func, N_func):
	output = 0
	for i in Xintlist_func:
	output = output * N_func + i
	return output

	# 入力
	Xintlist = [int(x) for x in input()]
	M = int(input())

	# Xに含まれる最も大きい数字dを求めておく
	d = max(Xintlist)

	# Xの文字数が1文字のとき、(d+1以上の)全ての位取り記数法の場合で同じ値が得られる
	# 2文字以上の場合とは決定的に違うので、場合分けをしておく
	if len(Xintlist) == 1:
	if Xintlist[0] <= M:
	print(1)
	else:
	print(0)
	else:
	# 位取り記数法の底が増えていくと、その位取り記数法におけるXの値も増えていく(狭義単調増加)
	# よって、二分探索を用いる

	# 二分探索の初期値を与える
	# lowはd
	low = d
	# highはM+1
	high = M + 1

	# 二分探索を実施
	# lowとhighの差が1になるまで続ける
	while low + 1 < high:
	# lowとhighの平均をとる(小数点以下切り捨て)
	mid = (low + high) // 2
	# mid進法におけるXintlistの値を取得
	value = Nshinhou(Xintlist, mid)
	# 条件を満たしていれば、lowはmid以上の値であることが分かる
	if value <= M:
	low = mid
	# そうでなければ、highはmid以下の値であることが分かる
	else:
	high = mid

	# 二分探索の結果得られたlowとhighが境界
	# 出力するべきはlow - d
	print(low - d)

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 187」
Editorial - AtCoder Beginner Contest 192
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
TATSUO IKURA様による「文字列の中の文字が大文字か小文字かを判定する(islower, isupper, istitle)」 >
文字列の中の文字が大文字か小文字かを判定する(islower, isupper, istitle)
文字列で用意されているメソッドの中で, 文字列の中に含まれる文字が大文字か小文字かを判定するのに使用できるメソッドの使い方について解説します.
渡部拓也様による「アルゴリズムを勉強するなら二分探索から始めよう！『なっとく！アルゴリズム』より」
アルゴリズムを勉強するなら二分探索から始めよう！『なっとく！アルゴリズム』より
　新しいサービスやプロダクトを開発するなら, アルゴリズムの理解はもはや欠かせなくなってきました. まだ理解が浅い, 勉強したいと思っている, そんな方には翔泳社が1月31日に刊行した『なっとく！アルゴリズム』をおすすめします. 今回は本書の読み方と, アルゴリズムの例として二分探索について紹介します.

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)をPythonで解く

A - Star

B - uNrEaDaBlE sTrInG

C - Kaprekar Number

D - Base n

ここで用いる二分探索の概要

lowとhighの初期値

細かい場合の補足

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