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

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

こんにちは, Shinoryoです.

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

1A - ReLU
2B - Billiards
3C - Travel
4D - Water Heater
5E以降
6参考にしたもの

A - ReLU

if文で条件分岐をすれば問題ないと思います.

	x = int(input())
	if x >= 0:
	print(x)
	else:
	print(0)

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

B - Billiards

2点 $(S_{x}, S_{y})$ , $(G_{x}, - G_{y})$ を通る直線と $x$ 軸の交点を求めることになります. 2点 $(S_{x}, S_{y})$ , $(G_{x}, - G_{y})$ を通る直線の式は

\begin{aligned} (1) & (G_{x} - S_{x}) (y - S_{y}) & = (- G_{y} - S_{y}) (x - S_{x}) \end{aligned}

です. これに $y = 0$ を代入すればよく, 計算すると

\begin{aligned} (2) & x & = \frac{S_{y} (G_{x} - S_{x}) + S_{x} (G_{y} + S_{y})}{G_{y} + S_{y}} \end{aligned}

となります. これを出力します.

	sx, sy, gx, gy = [int(x) for x in input().split()]
	print((sy(gx-sx)+sx(gy+sy))/(gy+sy))

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

C - Travel

Pythonで順番を並び替えたもののリストを作成するには, itertools.permutations(リスト)を利用します.

下で「index[(i+1)%n]」としている理由は, $i = n - 1$ のときにindex[0](つまり都市 $1$ のデータ)を参照できるようにするためです.

	import itertools

	n, k = [int(x) for x in input().split()]
	data = [[int(x) for x in input().split()] for _ in range(n)]

	nums = list(range(1,n))
	ans = 0
	for index in itertools.permutations(nums):
	index = [0]+list(index)
	time = 0
	for i in range(n):
	time += data[index[i]][index[(i+1)%n]]
	if time==k:
	ans += 1
	print(ans)

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

D - Water Heater

各時刻で使われているお湯の量を直接求めようとすると $O (N)$ かかるため, 時刻の最大値 $2 \times 10^{5}$ を $T$ として時間計算量 $O (N T)$ となり, TLE. そのようなコードを参考までに以下に示しておきます.

	alltime = 2(10*5) + 1
	table = [0 for _ in range(alltime)]

	n, w = [int(x) for x in input().split()]
	for i in range(n):
	s, t, p = [int(x) for x in input().split()]
	for j in range(s, t):
	table[j] += p

	table = sorted(table, reverse=True)

	if table[0] > w:
	print("No")
	else:
	print("Yes")

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

そこで, いもす法と呼ばれる方法を用います(いもす法に関しては, 下の参考にしたものを参照). 各時刻で使われているお湯の量を直接求めるのではなく, 開始時刻と終了時刻でのお湯の使用量の増減を記録し, 後にそのデータを基にシミュレーションします. 開始時刻と終了時刻の記録に $O (N)$ , シミュレーションに $O (T)$ なので, 計算量は $O (N + T)$ となります.

	alltime = 2(10*5)+1
	table = [0 for _ in range(alltime)]

	n, w = [int(x) for x in input().split()]
	for i in range(n):
	s, t, p = [int(x) for x in input().split()]
	table[s] += p
	table[t] -= p

	for i in range(1,alltime):
	table[i] += table[i-1]

	table = sorted(table, reverse=True)

	if table[0] > w:
	print("No")
	else:
	print("Yes")

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

E以降

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

参考にしたもの

「解説 - AtCoder Beginner Contest 183」
Editorial - AtCoder Beginner Contest 183
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
junkls様による「itertoolsによる順列, 組み合わせ, 直積のお勉強」
itertoolsによる順列, 組み合わせ, 直積のお勉強 - Qiita
itertoolsを使うと順列や組み合わせをスッキリ書くことができます. >>> import itertools (a, b, c, d, e)の並べ方を考えてみます. >>> seq =...
nkmk様による「Pythonでリストの最大値・最小値から順にn個の要素を取得」
Pythonでリストの最大値・最小値から順にn個の要素を取得 | note.nkmk.me
Pythonでリスト（配列）の最大値・最小値から順にn個の要素を取得したい場合, n=1であれば, 組み込み関数max(), min(), n>1であれば, リストをソート（並び替え）する方法と標準ライブラリのheapqモジュールを使う方法がある. 最大値・最小値を取得: max(), min() 最大値・最小値から順にn個の要素を取得: ソート最大値・...
Kentaro Imajo様による「いもす法」
いもす法

AtCoder Beginner Contest 183をPythonで解く

A - ReLU

B - Billiards

C - Travel

D - Water Heater

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