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で再実装したので、最小カット最大フローのいい練習になった。