AtCoder ABC #022 : Python練習編

ABC022は開始時刻に間に合わず不参加。
http://abc022.contest.atcoder.jp/assignments

A - Best Body

N日間の体重遷移の情報として、初日の体重Wと、2日目以降における前日との体重差分A[i]が与えられる。
適正体重であるS～Tの間に入る日を求めよ。

W+=A[i]で体重を更新し、S～Tに収まるか判定すればよい。
Python はS ≦ W ≦ Tという表記ができて良いね。

N,S,T=map(int,raw_input().strip().split(" "))
ret=0
W=0
for i in range(N):
	W+=input()
	if S<= W <=T:
		ret += 1

print ret

B - Bumble Bee

ハチがN個の花を順に訪れる。
i番目に訪れる花の種類はA[i]である。
その際、以前に同じ花を訪れていた場合、i番目の花に受粉する。
全体で受粉する花の数を求めよ。

setなり、花の種類ごとのカウンタなりで、各花が訪問済みか管理すればよい。

N=input()
ret=0
hist=[0]*101000

for i in range(N):
	x=input()
	if hist[x] > 0:
		ret += 1
	hist[x] = 1

print ret

C - Blue Bird

N頂点M距離付無向辺の無向グラフが与えられる。
1番の頂点から始まり、他の頂点を1個以上通り、同じ辺を2回以上通らないようにして元の頂点に戻る経路のうち、最短経路の距離を求めよ。

自分は以下の3通りで通した。上2つはPythonではTLEするので注意。

1番とx番の辺を取り除いた状態で1番からx番への最短経路を求め、元の1番とx番の辺を追加すれば条件を満たす移動経路が求められる。そこでx番を総当たりして最小値を求めればよい。
- (N-1)回Dijkstraを行うので、O(N^3*logN)かかる。
2番～N番の頂点でWarshall-Floyed法で全点間最短経路を求める。次に2番～N番の頂点から2個x,yを総当たりし、1→x→y→1とたどる経路の最小値を求めればよい。
- 後半の総当たりパートはO(N^2)だが、WF法パートでO(N^3)かかる。
Editorialの最後にあった最短経路木を用いる方法。
- まずDijkstra法を用いて最短経路を求める。その際、1番に隣接するどの頂点を経由したかによって頂点をグループ分けする。
- 最短経路に含まれない辺を用いると異なるグループを結べるのであれば、条件を示す経路を作れる。
- よって最短経路に含まれない辺を総当たりし、経路長の最小値を求めればよい。
- DijkstraパートでO(N^2*logN)、辺の総当たりパートでO(N^2)なので、こちらはPythonで間に合う。

import sys
import math
import Queue

N,M=map(int,raw_input().strip().split(" "))
mat=[[1<<60 for i in range(301)] for j in range(301)]
group=[0]*301

for i in range(M):
	x,y,l=map(int,raw_input().strip().split(" "))
	mat[x-1][y-1]=mat[y-1][x-1]=l

dist = [1<<60] * N
dist[0]=0

Q = Queue.PriorityQueue()
Q.put((0,0))
while Q.qsize() > 0:
	ent = Q.get()
	co  = ent[0]
	cur = ent[1]
	if dist[cur] != co:
		continue
	
	for i in range(N):
		if mat[cur][i]>=0 and co + mat[cur][i] < dist[i]:
			if cur==0:
				group[i]=i
			else:
				group[i]=group[cur]
			dist[i] = co + mat[cur][i]
			Q.put((dist[i],i))

mi=1<<60
for x in range(1,N):
	if group[x] != x:
		mi = min(mi, dist[x]+mat[0][x])
	for y in range(x+1,N):
		if group[x] != group[y]:
			mi = min(mi, dist[x] + mat[x][y] + dist[y])

if mi >= 1<<60:
	mi = -1
print mi

D - Big Bang

2次元上でN個の頂点群の座標A[i]が与えられる。
これらを同じ距離・同じ向きに平行移動し、同じ角度原点を中心に回転移動し、原点を中心にP倍拡大したところ、各頂点の座標はB[i]となった。
Pを求めよ。

Pさえ求められればいいので、図形全体に対しPだけ差が出るようなパラメータに注目し、移動前後のパラメータの変化を求める。
自分は以下の2通りでやった。前者はC++だと通るが、Pythonだと通らない。

A,Bの凸包を求め、辺の総長や最短辺長の比を求める。この比はPである。
- 凸包パートでO(N*logN)かかる。
A,Bそれぞれ重心が原点に来るよう平行移動し、原点から全頂点への距離の総和を求める。この比もPである。
- こちらはO(N)なのでPythonでも間に合う。

import math

def dsum(P):
	tx=ty=0
	
	for x,y in P:
		tx += 1.0*x
		ty += 1.0*y
	tx /= len(P)
	ty /= len(P)
	
	tl = 0
	for x,y in P:
		x -= tx
		y -= ty
		tl += (x*x+y*y) ** 0.5
	
	return tl

N=input()
TL=[]

for i in range(2):
	P = []
	for j in range(N):
		P.append(map(int,raw_input().strip().split(" ")))
	TL.append(dsum(P))

print TL[1]/TL[0]

まとめ

CもDもPythonだと大変だと思ったけど、良く考えたらDは簡単だったな。
無駄に凸包ライブラリをPythonに移植しちゃったよ。

kmjp's blog

競技プログラミング参加記です

AtCoder ABC #022 : Python練習編

A - Best Body

B - Bumble Bee

C - Blue Bird

D - Big Bang

まとめ