AtCoder Beginner Contest 197（Sponsored by Panasonic）をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

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

1A - Rotate
2B - Visibility
3C - ORXOR
4D - Opposite
5E以降
6参考にしたサイト等

A - Rotate

入力する文字列を $S$ として, 求めるのは $S$ の $2$ 文字目以降の後ろに $S$ の $1$ 文字目をくっつけた, $S [1 :] + S [0]$ になります.

	# 入力
	S = input()

	# 出力
	print(S[1:]+S[0])

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

B - Visibility

マス目 $(X, Y)$ から上下左右4方向に順に進めていき(答えに $1$ を足していく), 障害物#か端に突き当たったらそこで探索するのをやめればよいです. マス $(X, Y)$ 自身を含むので答えの初期値には $1$ を加えておくこと, $X$ と $Y$ が数学の通常の座標の感覚とは違うことに注意して実装します.

図 B問題における探索のイメージ. 星のマスはマス目

(X, Y)

を表す. 上下左右4方向に順に進めていき, 障害物#か端に突き当たったらそこで探索するのをやめる.

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

	# X, Yをindexに合わせて-1
	X -= 1
	Y -= 1

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

	# 上方向
	for x in range(X-1, -1, -1):
	if S[x][Y] == "#":
	break
	else:
	ans += 1

	# 下方向
	for x in range(X+1, H, 1):
	if S[x][Y] == "#":
	break
	else:
	ans += 1

	# 左方向
	for y in range(Y-1, -1, -1):
	if S[X][y] == "#":
	break
	else:
	ans += 1

	# 右方向
	for y in range(Y+1, W, 1):
	if S[X][y] == "#":
	break
	else:
	ans += 1

	# 出力
	print(ans)

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

C - ORXOR

区分けの仕方は, それぞれの数の間にあると仮定する $(N - 1)$ 個の仕切りそれぞれに, 仕切りを置くか置かないかの $2$ 通りになるので, $2^{N - 1}$ 通りになります. それぞれの区分けの仕方は, 整数 $0 \leq i \leq 2^{N - 1} - 1$ を2進数にした表現によって表すことができます. このような全探索方法をbit全探索といいます.

下のコードでは, $i$ を2進法で表したとき右から $j$ 番目が $1$ ならば, $A [j - 1]$ と $A [j]$ の間に仕切りがあると考えています. 右から $j$ 番目が $1$ かどうかを確かめるには, $i$ を2進法で表した数を右に $j - 1$ だけシフト(>>演算子)し, それと $1$ との論理積(&演算子)をとることによって確かめます.

図右から

j

番目が

1

かどうかを確かめるイメージ. 左では, そのまま

1

との論理積をとることによって, 一番右が

1

であることを確かめている. 一方右では, 右へ

1

シフトしたあとで

1

との論理積をとることによって, 右から

2

番目が

0

であることを確かめている.

Pythonでは論理和(OR)(|演算子)と排他的論理和(XOR)(^演算子)があるので, それを用いることで計算をすることができます.

なお, 下のコードはPyPy3でACとなります. Python3だとTLEでした.

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

	# 答えを格納する変数
	# A < 2^30なので、2^30よりは小さい
	ans = 1 << 30

	# ループ
	# 2^(N-1)回分(区間に分ける場合の数)
	for i in range(1 << (N-1)):

	# ored: 分けた区間内の数のビット単位ORを格納する変数
	# xored: 得られた全ての値のビット単位XORを格納する変数
	ored = A[0]
	xored = 0

	# A[1]からA[N-1]までのA[j]に関する処理
	for j in range(1, N):
	# 区間の分け方iの右から(j-1)番目が1(つまり、仕切りを入れる)かのチェック
	if (i >> (j - 1)) & 1:
	# 仕切りが入っている場合の処理
	xored ^= ored # XOR演算
	ored = A[j]
	else:
	# 仕切りが入っていない場合の処理
	ored \|= A[j] # OR演算

	# 最後のXOR演算
	xored ^= ored # XOR演算
	# ansを更新
	ans = min(ans, xored)

	# 出力
	print(ans)

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

D - Opposite

任意の正多角形に対してある円が存在し, その正多角形はその円に内接するようにできます.

$p_{0}$ と $p_{N / 2}$ の2点を結ぶ線分の中点をとることによって, 円の中心(あるいは「正多角形の中心」) $q$ を得ることができます. そして, $p_{0}$ の座標と $q$ の座標, そして正多角形が正 $N$ 角形であることが分かれば, $q$ を中心に $2 π / N rad$ だけ反時計回りに $p_{0}$ を回転させた点が $p_{1}$ であるということが分かります.

図 D問題を表した図.

p_{0}

と

p_{N / 2}

の2点を結ぶ線分の中点をとることによって, 点

q

の座標が分かる. そして,

p_{1}

は,

q

を中心に

2 π / N rad

だけ反時計回りに

p_{0}

を回転させた点である.

座標の回転は行列(あるいは, 複素数平面など)を用いて考えます. $(x_{0}, y_{0})$ を中心に角度 $α$ だけ反時計回りに $(x, y)$ を回転させることを考えれば, その結果得られる $(x_{1}, y_{1})$ は

\begin{aligned} (1) & (\begin{array}{c} x_{1} - x_{0} \\ y_{1} - y_{0} \end{array}) & = (\begin{array}{c} \cos α & - \sin α \\ \sin α & \cos α \end{array}) (\begin{array}{c} x - x_{0} \\ y - y_{0} \end{array}) \end{aligned}

となることに注意してください. Pythonにおいて, $\cos$ や $\sin$ はmath.cos(), math.sin()で計算できます(引数は $rad$ ). 円周率 $π$ はmath.piで扱えます.

	import math

	# 点x、点x_0、角度(rad)を受け取って、
	# 点x_0を中心にその角度だけ反時計回りに点xを回転させた座標(x_1, y_1)を返す関数
	def rotate(x, x_0, angle):
	x_1 = math.cos(angle)(x[0] - x_0[0]) - math.sin(angle)(x[1] - x_0[1]) + x_0[0]
	y_1 = math.sin(angle)(x[0] - x_0[0]) + math.cos(angle)(x[1] - x_0[1]) + x_0[1]
	return [x_1, y_1]

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

	# 正多角形の中心qを求める
	q = [(p_N2[0] + p_0[0])/2, (p_N2[1] + p_0[1])/2]

	# 求める点は、qを中心にp_0を(2*Pi/N)だけ反時計回りに回転させた点
	p_1 = rotate(p_0, q, 2*math.pi/N)

	# 出力
	print(p_1[0], p_1[1])

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 197（Sponsored by Panasonic）」
Editorial - AtCoder Beginner Contest 197（Sponsored by Panasonic）
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonのビット演算子（論理積, 論理和, 排他的論理和, 反転, シフト）」
Pythonのビット演算子（論理積, 論理和, 排他的論理和, 反転, シフト） | note.nkmk.me
Pythonには&, |, ^, ~, <<, >>のビット演算子が用意されており, 2進数で表した整数型intの値の各ビットに対して, それぞれ論理積, 論理和, 排他的論理和, ビット反転, 左ビットシフト, 右ビットシフトを行う. ここでは, 論理積（AND）: &演算子論理和（OR）: |演算子排他的論理和（XOR）: ^演算子について説明してから, ...
nkmk様による「Pythonで三角関数を計算（sin, cos, tan, arcsin, arccos, arctan）」
Pythonで三角関数を計算（sin, cos, tan, arcsin, arccos, arctan） | note.nkmk.me
Pythonの数学関数の標準モジュールmathを使うと, 三角関数（sin, cos, tan）および逆三角関数（arcsin, arccos, arctan）の計算ができる. 9.2. math — 数学関数三角関数 — Python 3.6.4 ドキュメントここでは, 以下の内容についてサンプルコードとともに説明する. 円周率（パイ）: math.pi 角度変換（ラジアン, 度）: m...

AtCoder Beginner Contest 197（Sponsored by Panasonic）をPythonで解く

A - Rotate

B - Visibility

C - ORXOR

D - Opposite

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