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

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

こんにちは, Shinoryoです.

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

1A - Lexicographic Order
2B - AtCoder Quiz
3C - Inverse of Permutation
4D - Cutting Woods
5E以降
6参考にしたサイト等
7脚注

A - Lexicographic Order

Pythonにおいて辞書順は, 通常の大小関係<と>で表されます.

	# 入力
	A, B = input().split()

	# 出力
	if A < B:
	print("Yes")
	else:
	print("No")

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

B - AtCoder Quiz

方法はさまざまあるかと思いますが, 以下では「コンテスト一覧となる集合から差し引いた残りを出力する」という方法で記述しています.

	# コンテスト一覧
	S_all = {"ABC", "ARC", "AGC", "AHC"}

	# S_allから減らしていく
	for _ in range(3):
	S_all.discard(input())

	# 出力
	print(S_all.pop())

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

C - Inverse of Permutation

例えば, $[p [i], i]$ を $i = 1, 2, \dots, N$ まで並べたリストを用意して昇順にソートすると, 各要素の2番目の要素を取り出したものは順列 $Q$ に相当します(図1参照).

図1　

[p [i], i]

を並べたリストをソートした概念図.

時間計算量は $O (N \log N)$ に(たぶん)なりますが, これでもACすることができます.

	# 入力
	# pはインデックス番号(1から始まる)をつけておく
	N = int(input())
	p = []
	p_index = 1
	for x in input().split():
	p.append([int(x), p_index])
	p_index += 1

	# ソートする
	q = sorted(p)

	# 出力
	print(" ".join(str(q[i][1]) for i in range(N)))

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

あるいは, $q [p [i]] = i$ であることに気づいてしまえば, より高速に処理することが可能です(「 $Q$ の $p [i]$ 番目の要素が $i$ である」そのままです). 時間計算量は $O (N)$ に(たぶん)なります.

	# 入力
	# Pはインデックス番号にするために-1する
	N = int(input())
	P = [int(x) - 1 for x in input().split()]

	# 順列Qを作成する(適当に0で初期化しておく)
	Q = [0 for _ in range(N)]
	# Q[P[i]] = iである
	for i in range(N):
	Q[P[i]] = i

	# 出力
	# もとの(インデックスではない)数字に戻すために+1する
	print(" ".join(str(q + 1) for q in Q))

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

D - Cutting Woods

UnionFindを利用した解法は, おそらく以下のようになるかと思います. UnionFindは, 「AtCoder Beginner Contest 214をPythonで解く」でも取り扱っています.

クエリが全部なされた後でも切断されていない部分を切断するような, 新たなクエリを加える. これにより, 全てのクエリが実行された後には全ての部分が切断されている状態になる.
$L$ で初期化されたUnionFindを用意する.
クエリを逆に実行していく. $c = 1$ なら切断の逆の結合を行い, $c = 2$ なら出力するべき値を何らかのリスト等に格納しておく.
出力するべき値が格納されたリストから, 定められた順番で出力を行う.

Pythonでは, これだとTLEになってしまいます.

	from collections import defaultdict, deque

	# UnionFindのクラス
	# https://note.nkmk.me/python-union-find/
	class UnionFind():
	def __init__(self, n):
	self.n = n
	self.parents = [-1] * n

	def find(self, x):
	if self.parents[x] < 0:
	return x
	else:
	self.parents[x] = self.find(self.parents[x])
	return self.parents[x]

	def union(self, x, y):
	x = self.find(x)
	y = self.find(y)

	if x == y:
	return

	if self.parents[x] > self.parents[y]:
	x, y = y, x

	self.parents[x] += self.parents[y]
	self.parents[y] = x

	def size(self, x):
	return -self.parents[self.find(x)]

	def same(self, x, y):
	return self.find(x) == self.find(y)

	def members(self, x):
	root = self.find(x)
	return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
	return [i for i, x in enumerate(self.parents) if x < 0]

	def group_count(self):
	return len(self.roots())

	def all_group_members(self):
	group_members = defaultdict(list)
	for member in range(self.n):
	group_members[self.find(member)].append(member)
	return group_members

	def __str__(self):
	return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

	# 入力
	L, Q = [int(x) for x in input().split()]
	c = []
	x = []
	non_cutted_set = set(range(1, L))
	for i in range(Q):
	c_temp, x_temp = [int(x) for x in input().split()]
	c.append(c_temp)
	x.append(x_temp)
	if c_temp == 1:
	non_cutted_set.discard(x_temp)

	# 切断していない部分を切断する
	for non_cutted in non_cutted_set:
	c.append(1)
	x.append(non_cutted)
	Q += 1

	# UnionFindをLで初期化
	uf = UnionFind(L)

	# 出力するものを格納するリスト
	output = deque()

	# クエリを逆に実行していく
	for i in range(Q - 1, -1, -1):
	if c[i] == 1:
	# 接合の反対=結合
	uf.union(x[i] - 1, x[i])
	else:
	# x[i]が所属しているグループのサイズを見る
	output.appendleft(uf.size(x[i]))

	# 出力
	while(output):
	print(output.popleft())

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

そこで, 発想を変えてみます. 「切断位置リスト」として, 今までに切断された位置が格納されたリストを用意します. 便宜上, $0$ と $L$ も初期値として格納しておきます. あるクエリ $c = 2, x = x_{1}$ が与えられたときに,

「切断位置リスト」に含まれる要素のうち $x_{1}$ より大きい要素のうち最小の要素( $= x_{2}$ )
「切断位置リスト」に含まれる要素のうち $x_{1}$ より小さい要素のうち最大の要素( $= x_{3}$ )

を高速に取得できれば, 出力すべき値は $x_{2} - x_{3}$ となります.

そのような $x_{2}$ , $x_{3}$ を高速に取得できる方法の1つに, bisectモジュールがあります. リストの順序関係(基本的には, 数値の大小関係)を保ったまま, リストへの挿入を行うことができます. 挿入だけでなく, 「挿入可能な位置」を調査することができ, これによって $c = 2$ のクエリに関する操作を行うことができます.

これだけでも残念ながらPythonだとTLEになってしまうのですが, arrayモジュールを利用することによって, 挿入をやや高速に行うことができて^*1ACすることができます.

	from array import array
	import bisect

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

	# 切断した箇所を格納していくリスト
	# 上下限は0, L
	cutted = array("i", [0, L])

	# 全クエリに対してループ
	for i in range(Q):
	c_temp, x_temp = [int(i) for i in input().split()]
	if c_temp == 1:
	# cuttedにx[i]を、順序を維持したまま挿入する
	bisect.insort(cutted, x_temp)
	else:
	# cuttedにx_tempを挿入するとしたらどこか？
	# 挿入可能な位置の前後の差をとれば、x_tempが含まれる木材の長さが分かる
	i = bisect.bisect(cutted, x_temp)
	print(cutted[i] - cutted[i - 1])

	# bisect.bisectやbisect.insortに(明示的であるためには)つけるべきleftやrightは、
	# 今回の場合重複がないのでどちらでもよく、省略している

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 217」
Editorial - AtCoder Beginner Contest 217
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で文字列同士を比較して判定する方法について説明する. 完全一致（等価）: ==, != 部分一致: in, not in 前方一致・後方一致（先頭・末尾）: startswith(), endswith() 文字列の大小関係（順番）: <, <=, >, >= 大文字小文字を区別せずに比較正規表現パターンにマッチ: re.search(), re.fullmatch() 文字列を検索し...
bisect — Array bisection algorithm — Python 3.9.7 documentation
bisect — Array bisection algorithm — Python 3.9.7 documentation
ta7uw様による「Python標準ライブラリ：順序維持のbisect」
Python標準ライブラリ：順序維持のbisect - Qiita
はじめにソートされたリストに対してソート順序を保ったまま値を挿入したいと思う場面は少なくないはずです. そういった場面に出くわしたときにappendしてsortしているとパフォーマンスはよくないです. Pythonのlistのソ...
array — Efficient arrays of numeric values — Python 3.9.7 documentation
array — Efficient arrays of numeric values — Python 3.9.7 documentation

脚注

*1 : 気になったので, リストに対してinsertをしたときの処理時間を計測してみました.

	from array import array
	import time

	N = 10**5

	# 通常のリストの場合の処理時間計測
	t1 = time.time()
	test_list1 = []
	for _ in range(N):
	test_list1.insert(0, 1)
	t2 = time.time()
	print("通常のリストの場合：" + str(t2 - t1) + "秒")

	# arrayの場合の処理時間計測
	t3 = time.time()
	test_list2 = array("i", [])
	for _ in range(N):
	test_list2.insert(0, 1)
	t4 = time.time()
	print("arrayモジュールの場合：" + str(t4 - t3) + "秒")

view raw ABC217-d-check.py hosted with ❤ by GitHub

通常のリストの場合：3.3825604915618896秒
arrayモジュールの場合：0.6667544841766357秒

こうしてみると, (少なくとも $N$ が十分に大きい場合には)確かにarrayモジュールの方がinsertに関しては高速に処理が出来そうですね.

AtCoder Beginner Contest 217をPythonで解く

A - Lexicographic Order

B - AtCoder Quiz

C - Inverse of Permutation

D - Cutting Woods

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