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

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

こんにちは, Shinoryoです.

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

1A - Vanishing Pitch
2B - Remove It
3C - Digital Graffiti
4D - Circle Lattice Points
5E以降
6参考にしたサイト等

A - Vanishing Pitch

条件は, $D < V T$ または $V S < D$ となります.

	# 入力
	V, T, S, D = [int(x) for x in input().split()]

	# 出力
	if D < V * T or V * S < D:
	print("Yes")
	else:
	print("No")

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

B - Remove It

配列 $A^{'}$ を作成して, それを空白でつなげた文字列を用意し, 出力します.

	# 入力
	N, X = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]

	# 配列A'を用意
	Aprime = []
	for i in range(N):
	if A[i] != X:
	Aprime.append(A[i])

	# 出力(A'が空白の場合を考慮)
	if Aprime == []:
	print()
	else:
	Aprimestr = ""
	for i in range(len(Aprime)-1):
	Aprimestr += str(Aprime[i]) + " "
	Aprimestr += str(Aprime[-1])
	print(Aprimestr)

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

あるいは, 文字列メソッドjoin()を使うと, 文字列のリストを一つの文字列に連結することができます. 「"間に挿入する文字列".join([連結したい文字列のリスト])」の形です. 今の場合, 「間に挿入する文字列」は半角空白, 連結したい文字列のリストは $A^{'}$ の各要素を文字列型にしたものになります.

	# 入力
	N, X = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]

	# 配列A'を用意
	Aprime = []
	for i in range(N):
	if A[i] != X:
	Aprime.append(A[i])

	# 出力
	print(" ".join([str(i) for i in Aprime]))

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

C - Digital Graffiti

マス $S_{i j}$ に対応して, 図のように格子点を定めます. 端の点に関しては考えなくてよいので, 格子点は全部で $(H - 1) (W - 1)$ 個あります.

格子点 $(x, y)$ が多角形の頂点であるのは, 以下の条件のどちらかを満たす場合です.

その点の周囲 $4$ マス( $S_{x, y}$ , $S_{x + 1, y}$ , $S_{x, y + 1}$ , $S_{x + 1, y + 1}$ )のうち $1$ マスが黒に塗られている.
その点の周囲 $4$ マス( $S_{x, y}$ , $S_{x + 1, y}$ , $S_{x, y + 1}$ , $S_{x + 1, y + 1}$ )のうち $3$ マスが黒に塗られている.

$2$ マスだけが黒の場合は多角形の周の一部に対応しますし, $4$ マスなら多角形の内部の点, $0$ マスなら関係ない点になります.

以下がその例です. 図に入っている範囲では, $(0, 0)$ , $(1, 0)$ , $(1, 1)$ が多角形の頂点になります.

	# 与えられた格子点x,yと.#の文字列Sにおいて、その周囲の4マスのうち何個が#かを調査する関数
	def sharp_count(x, y, S_func):
	count = 0
	for k in range(x, x + 2):
	for l in range(y, y + 2) :
	if S_func[k][l] == "#" :
	count += 1
	return count

	# 入力
	H, W = [int(i) for i in input().split()]
	S = [input() for _ in range(H)]

	# 格子点のうち頂点になる数を格納
	cnt = 0

	# 頂点になる数を格納
	# 端の格子点は考慮しない
	# (W - 1)×(H - 1)個調べる
	for i in range(H - 1):
	for j in range(W - 1):
	if sharp_count(i, j, S) == 1 or sharp_count(i, j, S) == 3:
	cnt += 1

	# 出力
	print(cnt)

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

D - Circle Lattice Points

入力が高々小数点第4位までなので, 入力値に予め $10^{4}$ をかけておけば, 精度に関して問題なく計算を行うことができます.

$const = 10^{4}$ 単位で切り上げる関数と切り下げる関数をあらかじめ用意しておくと, 記述が楽になります. $X - R$ ( $10^{4}$ 単位で切り上げ)から $X + R$ ( $10^{4}$ 単位で切り下げ)までの間の $x$ 座標に対して,

\begin{array}{r} (1) & y_{\min} = Y - \sqrt{R^{2} - {(x - X)}^{2}} \end{array}

( $10^{4}$ 単位で切り上げ)から,

\begin{array}{r} (2) & y_{\max} = Y + \sqrt{R^{2} - {(x - X)}^{2}} \end{array}

( $10^{4}$ 単位で切り下げ)までの $y$ 座標が, 条件に適合します(三平方の定理より). それを数え上げればよいです.

sampleは全て通ったのですが, 提出するとWAとなってしまいました(6個から10個くらい). 今の時点ではこれを改善する方法を理解できていません.

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 191」
Editorial - AtCoder Beginner Contest 191
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonで文字列を連結・結合（+演算子, joinなど）」
Pythonで文字列を連結・結合（+演算子, joinなど） | note.nkmk.me
Pythonでの文字列操作において, 文字列を連結・結合する方法として, 複数の文字列を連結・結合: +演算子, +=演算子数値と文字列を連結・結合: +演算子, +=演算子, str(), format() 文字列のリスト（配列）を一つの文字列に連結・結合: join() 数値のリスト（配列）を一つの文字列に連結・結合: join(), str() を説明する. ...
なっちゃん様による「【ちょっとづつAtCode】ABC191　C – Digital Graffiti」
【ちょっとづつAtCode】ABC191　C – Digital Graffiti
引用（引用）問題文H 行 W 列のマス目があります. このマス目の, 上から i 番目, 左から j 番目のマスを, マス(i,,j)と呼ぶことにします. 各マスは黒または白に塗られています. Si,jが # ならばマス (i,,j)は黒に塗られており

AtCoder Beginner Contest 191をPythonで解く

A - Vanishing Pitch

B - Remove It

C - Digital Graffiti

D - Circle Lattice Points

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