東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回は東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - First Player
2B - Subscribers
3C - Virus
4D - A Piece of Cake
5E以降
6参考にしたサイト等

A - First Player

Aの最小値とそのインデックス(A_min_index)を取得し, A_min_index以降の要素を出力した後, A_min_indexより前の要素を出力すればよいです.

	# 入力
	N = int(input())
	S = []
	A = []
	for _ in range(N):
	S_i, A_i = input().split()
	S.append(S_i)
	A.append(int(A_i))

	# Aの最小値とそのインデックスを取得
	A_min = min(A)
	A_min_index = A.index(A_min)

	# 出力
	# A_min_index以降の要素を出力
	for i in range(A_min_index, N):
	print(S[i])

	# A_min_indexより前の要素を出力
	for i in range(A_min_index):
	print(S[i])

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

B - Subscribers

$N$ を文字列まま入力を受け付けて, 4文字目以降をすべて $0$ に置き換えればよいです.

	# 入力
	N = list(input())

	# 文字列のまま切り捨ての操作
	for i in range(len(N) - 3):
	N[- (i + 1)] = "0"

	# 出力
	print("".join(N))

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

C - Virus

下の図のように, 人の間の距離が $D$ 以内の人同士をくっつけていくことを考えます.

このようにくっついた人同士の集合というのを考えることができます.

もし $1$ の人が感染したら, 最終的には $1$ の人が含まれる集合に属する人は感染しますが, それ以外の人には感染しないことになります.

このような操作は例えば, Union Findを用いて実装することができます. 最初は1つひとつバラバラな要素(人)が用意されます. そして, 「2つのまとまり(人)をつなげる」という操作を繰り返し, 最終的にある要素がどの集合に属しているかを管理していくアルゴリズムです.

「2つのまとまり(人)をつなげる」という操作に時間計算量が $O (N^{2})$ かかります. Python3.8だとTLEですが, PyPy3だとACです.

以下の例では, nkmk様による「PythonでのUnion-Find（素集合データ構造）の実装と使い方」(https://note.nkmk.me/python-union-find/)に掲載されているUnion Findのコードを使用しています.

	from itertools import combinations

	# Union Find
	# 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

	# 入力
	N, D = list(map(int, input().split()))
	position = [list(map(int, input().split())) for _ in range(N)]

	# Union Find生成
	infection_connection = UnionFind(N)

	# 全ての2人組の組み合わせでループし、その間の距離D以下なら、その2つをUnionFind.union()でくっつける
	for i, j in combinations(range(N), 2):
	if (position[i][0] - position[j][0]) * (position[i][0] - position[j][0]) + (position[i][1] - position[j][1]) * (position[i][1] - position[j][1]) <= D * D:
	infection_connection.union(i, j)

	# index 0の人が属する集合の、Union Find上のrootを取得
	root = infection_connection.find(0)
	# Union Find上のrootが一致している人は、同じ集合に属していて感染していることになる
	for i in range(N):
	if infection_connection.find(i) == root:
	print("Yes")
	else:
	print("No")

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

Union Findは, 以下のAtCoder Beginner Contestでも登場しています.

D - A Piece of Cake

左から $X$ 列目, 下から $Y$ 行目にあるピースのIDを $(X, Y)$ と定めます( $X, Y$ の取りうる数には $0$ を含みます).

ある苺の座標を $(p, q)$ , ケーキを通る $y$ 軸に並行な異なる直線の座標を $(a_{1}, a_{2}, \dots, a_{A}, W)$ , ケーキを通る $x$ 軸に並行な異なる直線の座標を $(b_{1}, b_{2}, \dots, b_{B}, H)$ とします(便宜上, $W$ , $H$ もくっつけておきます). すると, その苺が乗っているピースのIDの $X$ の方は, $(a_{1}, a_{2}, \dots, a_{A}, W)$ の中に $p$ を挿入する位置のインデックスとして得ることができます. 同様に, その苺が乗っているピースのIDの $Y$ の方は, $(b_{1}, b_{2}, \dots, b_{B}, H)$ の中に $q$ を挿入する位置のインデックスとして得ることができます.

その位置の情報をもとに, (ピースのID,そこに乗っている苺の数)のタプルを, 苺の数の多い順に出力することができます. $m$ に関しては, 以下の2パターンが考えられます.

苺の乗っているピースが $(A + 1) \times (B + 1)$ (ピースの総数)よりも少ない場合
$\Rightarrow$ $m = 0$ となります.
苺の乗っているピースが $(A + 1) \times (B + 1)$ (ピースの総数)と等しい場合
$\Rightarrow$ $m$ としては先ほどのタプルのリストの最も後ろ側を参照します.

$M$ に関しては, 先ほどのタプルのリストの最も前側を参照します.

二分探索にはbisectモジュールを, (ピースのID,そこに乗っている苺の数)のタプルを苺の数の多い順に出力するのにはCollectionsモジュールを使用することができます.

	from bisect import bisect_left
	from collections import Counter

	# 入力
	W, H = map(int, input().split())
	N = int(input())
	strawberries = [list(map(int, input().split())) for _ in range(N)]
	A = int(input())
	a_list = list(map(int, input().split()))
	a_list.append(W)
	B = int(input())
	b_list = list(map(int, input().split()))
	b_list.append(H)

	# 左からX列目、下からY行目にあるピースのIDを(X,Y)と定める
	# 苺が乗っているピースのIDを二分探索で調査
	strawberries_location = [bisect_left(a_list, strawberries[i][0]) + bisect_left(b_list, strawberries[i][1]) * (10**6) for i in range(N)]
	# (ピースのID,そこに乗っている苺の数)のタプルを、苺の数の多い順に出力
	strawberries_count = Counter(strawberries_location).most_common()

	# mを求める
	if len(strawberries_count) < (A + 1) * (B + 1):
	m = 0
	else:
	m = strawberries_count[-1][1]
	# Mを求める
	M = strawberries_count[0][1]
	# 出力
	print(m, M)

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

E以降

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

参考にしたサイト等

「解説 - 東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）」
Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 304)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「PythonでのUnion-Find（素集合データ構造）の実装と使い方」
PythonでのUnion-Find（素集合データ構造）の実装と使い方 | note.nkmk.me
PythonでのUnion Findデータ構造（素集合データ構造）の実装とその使い方を説明する. まずはじめに最終形のクラスとその使い方のサンプルコードを示し, 後半で素朴な実装からいくつかの工夫を加えて最終形に至るまでを説明する. Union Find（素集合データ構造）の概要 PythonでのUnion Findの実装例サンプルコードのクラス...
Wakasugi Tatsuroh様による「Pythonで二分探索を行うライブラリ「bisect」」
Pythonで二分探索を行うライブラリ「bisect」 - Qiita
趣味で競プロをやるようになり, Atcoderの問題を何問か解いているのだが, やっている内に覚えないといけないこともいくつかあるわけで. その内の一つに二分探索というアルゴリズムを使うという場面を多く見てきたため, 自分が今よく利用して...
e様による「【Python】リストの要素の数え上げ, collections.Counterの使い方」
【Python】リストの要素の数え上げ, collections.Counterの使い方 - Qiita
はじめに今回はPythonのcollections.Counter()についてまとめます. AtCoderのPython3.4.3と3.8で動作確認済みです. collections.Counterについて collec...

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）をPythonで解く

A - First Player

B - Subscribers

C - Virus

D - A Piece of Cake

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