kmjp's blog

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

AtCoder ABC #021 : Python練習編

ARC

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が与えられる。
1 \le A_1 \le A_2 \le ... \le A_K \le Nとなる整数列A[i]の組み合わせは何通りあるか。

1～Nまでの数字から重複ありでK個取り出し、A[i]に昇順で当てはめる、と考えると単なる重複組み合わせとなり {}_N H_Kを求めればよくなる。
別の考え方としては、1からNまで(N-1)回数値がインクリメントする過程で、K回A[i]となる値を採用すると考えても {}_{N+K-1} C_K = {}_N H_Kで同じである。
この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の凡ミスがもったいない。