ABC#021に参加。
AでFirst Accept取れたのは良いが、Cでしょうもないミスをして順位を落とした。
http://abc021.contest.atcoder.jp/
A - 足し算
整数Nが与えられる。
Nを複数の2の累乗数の和で表せ。
1をN個使えばよい。
N=input() print N for i in range(0,N): print 1
B - 嘘つきの高橋くん
高橋君は町Aから町Bに移動する過程で町P[i]を順に経由した。
移動経路が最短か判定せよ。
A,B,P[i]で重複する町があるか判定すればよい。
import sys N = input() A,B = map(int,raw_input().strip().split(" ")) K = input() P = map(int,raw_input().strip().split(" ")) num = [0]*105 num[A] += 1 num[B] += 1 for i in P: num[i]+=1 for i in range(0,105): if num[i] > 1: print "NO" sys.exit() print "YES"
C - 正直者の高橋くん
N個の町と、町同士を結ぶ双方向の道路M本がある。
町Aから町Bに至る最短経路の通り方は何通りあるか。
町と道路を無向グラフとみなし、Warshall-Floydで頂点間の距離D(x,y)を求める。
Aから初めて頂点xに至る経路の数をP[x]とする。
D(A,x)=rとなるxに対し、D(A,y)=r+1かつD(x,y)=1なら、xからyに移動するのはyに至る最短経路(のうちの一つ)なので、P[y]+=P[x]を処理していく。
最終的にP[B]が解。
N=input() A,B=map(int,raw_input().strip().split(" ")) A -= 1 B -= 1 mat=[[101 for i in range(101)] for j in range(101)] for i in range(N+1): mat[i][i]=0 M=input() for i in range(M): x,y=map(int,raw_input().strip().split(" ")) mat[x-1][y-1] = mat[y-1][x-1] = 1 for i in range(N): for x in range(N): for y in range(N): mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y]) mo = 1000000007 num=[0] * 101 num[A] = 1 for i in range(0,N): for cur in range(0,N): if mat[A][cur] != i: continue for tar in range(0,N): if mat[A][tar]==i+1 and mat[cur][tar]==1: num[tar] += num[cur] num[tar] %= mo print num[B]
D - 多重ループ
N,Kが与えられる。
となる整数列A[i]の組み合わせは何通りあるか。
1~Nまでの数字から重複ありでK個取り出し、A[i]に昇順で当てはめる、と考えると単なる重複組み合わせとなりを求めればよくなる。
別の考え方としては、1からNまで(N-1)回数値がインクリメントする過程で、K回A[i]となる値を採用すると考えてもで同じである。
このCombinationの値は逆元を用いて計算できる。
mo = 1000000007 def comb(n,k): if k < 0 or k > n: return 0 fact = [0]*(n+1) factr = [0]*(n+1) inv = [0]*(n+1) fact[0]=factr[0]=inv[1]=1 for i in range(2,n+1): inv[i] = inv[mo % i] * (mo - mo/i) % mo for i in range(1,n+1): fact[i] = fact[i-1] * i % mo factr[i] = factr[i-1] * inv[i] % mo return fact[n] * factr[k] * factr[n-k] % mo def hcomb(n,k): if n==0 and k==0: return 1 return comb(n+k-1,k) N=input() K=input() print hcomb(N,K)
まとめ
Cの凡ミスがもったいない。