kmjp's blog

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

AtCoder ABC #010 : Python練習編

ABC#010は不参加のため練習のみ。最近の中では簡単な方?
http://abc010.contest.atcoder.jp/assignments

A - ハンドルネーム

入力に"pp"を加えた文字列を返せ。

import sys
print raw_input().strip() + "pp"

B - 花占い

N個の花の花びらの数A[i]が与えられる。
各花の花びらの数が偶数または3で割って2余る数のどちらでも無いように、花びらの数を減らしたい。
減らす最小数を答えよ。

花びらの枚数の初期状態ごとに減らすべき枚数が決まるので、各花についてその数の和を取ればよい。

import sys

ok=[0,0,1,0,1,2,3,0,1,0]

N=input()
K=map(int,raw_input().strip().split(" "))
R=0
for i in K:
	R += ok[i]

print R

C - 浮気調査

2つの座標(tx0,ty0)と(tx1,ty1)、時間T、速度V及びN個の中継地点(X[i],Y[i])が与えられる。
(tx0,ty0)から(tx1,ty1)に速度Vで移動する際、いずれかの中継地点を経由して時間T内に間に合う可能性はあるか答えよ。

各座標を総当たりし、(tx0,ty0)から(X[i],Y[i])と、(tx1,ty)から(X[i],Y[i])1の距離の和がT*V以下のものがあるか調べればよい。

import sys
import math

tx0,ty0,tx1,ty1,T,V=map(int,raw_input().strip().split(" "))
N=input()

for i in range(0,N):
	x,y=map(int,raw_input().strip().split(" "))
	if math.sqrt((x-tx0)*(x-tx0)+(y-ty0)*(y-ty0)) + math.sqrt((x-tx1)*(x-tx1)+(y-ty1)*(y-ty1)) <= T*V:
		print "YES"
		sys.exit(0)
print "NO"

D - 浮気予防

N人の人がおり、互いの友達関係が無向グラフで与えられる。
0番の人が指定されたG人(番号はP[i])と連絡を取れないようにしたい。

連絡が取れる条件は、0番が友達関係を介してP[i]と友達であり、かつP[i]のパスワードが変更されていないことである。
連絡を取れないようにするため、コスト1で友達関係を1つ解消するか、1人のパスワードを変更することができる。
G人と連絡を取らせないようにする最小コストを求めよ。

人間関係のグラフに加え、G人P[i]から終点に向けて無向辺を張ったグラフを考える。
各辺の容量を1として考えたとき、G人と連絡が取れない状態とは0番から終点にフローが作れないことである。

このうち幾つかの辺を除いてフローを0にするわけだが、これは最小カットの数と一致する。
さらに最小カットは最大フローと一致するので、結果的にこのグラフの最大フローを求めればよい。

import sys

def dfs(cur):
	global vis
	global EE
	vis[cur] = 1
	if cur==100:
		return 1
	for i in range(101):
		if vis[i]==0 and EE[cur][i]>0 and dfs(i) > 0:
			EE[cur][i] -= 1
			EE[i][cur] += 1
			return 1
	return 0

N,G,E=map(int,raw_input().strip().split(" "))
EE = [[0 for x in range(101)] for y in range(101)]
vis = [0] * 101

if G==0:
	print 0
	sys.exit(0)
	
for i in map(int,raw_input().strip().split(" ")):
	EE[i][100] = 1

for i in range(0,E):
	x,y=map(int,raw_input().strip().split(" "))
	EE[x][y] = EE[y][x] = 1

flow=0
while 1:
	for i in range(0,101):
		vis[i] = 0
	if dfs(0) == 0:
		break
	flow += 1

print flow

まとめ

最大フローをPythonで再実装したので、最小カット最大フローのいい練習になった。