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

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

こんにちは, Shinoryoです.

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

1A - Don't be late
2B - Substring
3C - Sum of product of pairs
4D - Friends
5E以降
6参考にしたサイト等
7脚注

A - Don't be late

たどり着けるかどうかを計算します. 一応整数の範囲でやれるように

\begin{aligned} (1) & D & \leq T \times S \end{aligned}

の条件式を用いています.

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

	if D <= T*S :
	print("Yes")
	else:
	print("No")

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

B - Substring

文字列 $T$ を文字列 $S$ に重ねる全パターンを調査して, その最小値をとります. 文字列の長さはlen()で分かります.

	S = input()
	T = input()

	# 答えを仮置きしている
	# この後minで最小値をとっていくので, 仮置きは最大の1000文字
	ans = len(T)

	# 調査するパターンを全探索(i文字目からを重ねてみる)
	for i in range(len(S) - len(T)+1):
	diff = 0
	# 文字が異なるかどうかを確認(j文字目の文字が異なるかどうかを確認)
	for j in range(len(T)):
	if S[i + j] != T[j]:
	diff += 1
	ans = min(ans, diff)

	print(ans)

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

C - Sum of product of pairs

問題文にあることを律儀に実行する(すなわち, $1 \leq i < j \leq N$ を満たす $i$ , $j$ に対して,

\begin{array}{r} (2) & \sum_{i, j} A_{i} A_{j} \end{array}

を計算しようとする)と, 計算量が膨大になり, TLEになります. 参考までにそのコードを示しておきます.

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

	Asum = [sum(A[i+1:]) for i in range(N-1)]

	ans = 0

	for i in range(N-1):
	ans += (A[i] * Asum[i])
	ans %= ((10**9) + 7)

	print(ans)

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

解決策はいくつか考えられますが, 累積和によるものを示しておきます. $1 \leq i \leq N$ ( $i = N$ のときは対応する $j$ が存在しないので, 実質的には $N - 1$ )の各 $i$ に対して, $A_{i}$ に掛け算するのは $A_{i + 1}$ , $A_{i + 2}$ , ……, $A_{N}$ です. ゆえに, あらかじめ $A_{i + 1}$ , $A_{i + 2}$ , ……, $A_{N}$ の和を求めておけば, 計算量を減らすことができます.

実際には, $A_{1}$ , $A_{2}$ , ……, $A_{N}$ の和を求めておいて, $i = 1$ に対する計算が終わった後にその累積和から $A_{1}$ を減らして $i = 2$ に対する計算に利用する, というようにします.

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

	# A[0]に掛け算するA[1], A[2], …, A[N-1]の和Asumを求める
	Asum = sum(A[1:])

	# 答えを入力する変数
	ans = 0

	# A[0], ……, A[N-2]に対して調査
	for i in range(N-1):
	# A[i]×(A[i+1], A[i+2], …, A[N-1])を計算
	ans += (A[i] * Asum)
	# 剰余を計算
	ans %= ((10**9) + 7)
	# AsumからA[i+1]を引いて, 次の計算に利用
	Asum -= A[i+1]

	# 答えを出力
	print(ans)

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

あるいは,

\begin{aligned} (3) & \sum_{i < j} A_{i} A_{j} & = \frac{{(\sum_{i} A_{i})}^{2} - \sum_{i} A_{i}^{2}}{2} \end{aligned}

であるため, これを計算する方法もあります.

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

	print(((sum(A)2 - sum([x2 for x in A]))//2) % (10**9 + 7))

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

D - Friends

友達関係を辿って辿り着ける人は友達であるということから, $N$ 人の人は最終的には友達同士で結成されたいくつかの「友達集合」に分けられます. もちろん, 友達が存在しないために $1$ 人の「友達集合」に含まれる可能性もあります.

ここで, もし同じ「友達集合」に所属する人同士を同じグループに配置してしまうと, その人達は友達同士になってしまうため, 条件を満たすことが出来ません. よって, 最も人数の多い「友達集合」の人数を $K$ とすると, 必要なグループ数は最低でも $K$ になります. 他の各「友達集合」についても, $1$ 人ずつ順番にグループを割り振っていけばよいので, 求める数は $K$ になります.

$K$ を求める方法として, ここでは幅優先探索(breadth first search; BFS)と呼ばれる方法を用います.

幅優先探索はグラフ理論等で用いられるアルゴリズムです. ある根ノードで始まり隣接した全てのノードを探索し, そのそれぞれに対して同様のことを繰り返すことによって探索対象ノードを網羅します.

下の図は, 鹿児島県から出発して, 陸続きの都道府県を探索する幅優先探索を表しています. 鹿児島県に隣接していて陸続きなのは, 熊本県と宮崎県です. その熊本県と宮崎県に対しても同様のことを繰り返していきます^*1.

いくつか注意点を述べておきます.

友達が誰かを調べるべき人を格納したリスト(上の例でいうと, この後熊本県と宮崎県に関してどの都道府県に隣接しているかを調べるので, 「熊本県」と「宮崎県」を格納するリストが欲しい)に関しては, collectionsモジュールのdeque型を使用します^*2.
これまでの探索でどの友達集合に所属しているかが判明している人に関しては, 新たに幅優先探索を行っても既知の友達集合を調べることになってしまいます. そのままではでは時間計算量が大きくなってしまうので, リストvisitedを用いてどの友達集合に所属しているかが判明している人のリストを管理します.

	# collectionsモジュールのdeque型を使用
	from collections import deque

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

	# 友達情報リストの作成
	# AとBが友達なら, A行目のリストにBを加える
	# リストのインデックスは0から始まるため, N+1行の2次元配列
	# (0行目の存在は無視する)
	g = [[] for _ in range(N+1)]
	for i in range(M):
	A, B = [int(x) for x in input().split()]
	g[A].append(B)
	g[B].append(A)

	# どの友達集合に所属しているかが判明している人のリスト
	visited = [False]*(N+1)
	ans = 1

	# 各人に対してループ
	for i in range(1,N+1):
	# どの友達グループに所属しているかが判明している場合は調べなくてよい
	if visited[i]:
	continue

	visited[i] = True
	# deque型の変数を作成(まずはiの友達を調べるため, iを格納)
	queue = deque([i])

	# iが所属する友達集合の人数を格納する変数を作成
	# iとiは友達なので, 初期値は1
	friends_number = 1

	# 幅優先探索の実行
	# queueの各要素について友達を調べる
	while queue:
	k = queue.popleft()
	for j in g[k]:
	# iの新しい友達jに関して,
	# ・friends_numberに1を足し,
	# ・visited[j]をTrueにし,
	# ・queueにjを追加する
	if visited[j]:
	continue
	friends_number += 1
	visited[j] = True
	queue.append(j)

	ans = max(ans,friends_number)

	print(ans)

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

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 177」
Editorial - AtCoder Beginner Contest 177
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
TATSUO IKURA様の「文字列の長さ(文字数)を取得する」
文字列の長さ(文字数)を取得する
組み込み関数の len 関数を使って文字列の長さ(文字数)を取得する方法について解説します.
takayg様の「Pythonでアルゴリズム（幅優先探索, bfs）」
Pythonでアルゴリズム（幅優先探索, bfs） - Qiita
はじめに　pythonを使った幅優先探索の実装について解説していきます. （僕がいつも実装するやつを載せるだけです. ）　幅優先探索ではよく距離についての問題が出てくるので, 今回はある1頂点から各頂点までの距離を返す関数を実装し...
nkmk様の「Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う」
Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う | note.nkmk.me
Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと, データをキューやスタック, デック（両端キュー）として効率的に扱うことができる. collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント標準のリストをキューやスタック, デック（両端キュー）として使うことも可能だが, リストでは先頭...

脚注

*1 : 宮崎県から大分県に点線で矢印が引いてあるのは, 探索に関する熊本県と宮崎県の順番次第では, 大分県へは熊本県からではなく宮崎県から矢印が引かれる可能性があることを示しています.

*2 : deque型には, 先頭・末尾の要素を追加・削除するappend(), appendleft(), pop(), popleft()にかかる時間計算量が大きく減少するというメリットがあります. 一方で, deque型の中央部分へのアクセスには時間計算量が大きくなってしまうというデメリットがあるので, 要素の追加・削除以外も何らかの操作を行う場合には, deque型を使わない方が良いかもしれません.

AtCoder Beginner Contest 177をPythonで解く

A - Don't be late

B - Substring

C - Sum of product of pairs

D - Friends

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