AtCoder ABC #041 : Python練習編

本番は不参加でした。
http://abc041.contest.atcoder.jp/assignments

A - 添字

愚直に出力する。

S=raw_input()
N=input()
print S[N-1]

B - 直方体

多倍長整数が使える言語だと何も考えなくていいね。

X,Y,Z=map(int,raw_input().strip().split(" "))
print X*Y*Z%1000000007

C - 背の順

(身長,元のindex)のpairを身長降順でソートするとよい。

N=input()
A=map(int,raw_input().strip().split(" "))
B = []
for i in range(N):
	B.append((A[i],i+1))

B.sort()
B.reverse()
for b in B:
	print b[1]

D - 徒競走

N匹の番号付きの兎を順に並べたい。
その時、x番の兎はy番の兎より前である、という情報がいくつか与えられる。
全ての情報に矛盾しない並べ方は何通りか。

bitDPで、bitmaskに相当する兎群が並び順の末尾に来るような並べ方dp[bitmask]を考える。
bitmaskに含まれる兎iがbitmaskに含まれる他の全兎の手前に来て問題ないなら、dp[bitmask] += dp[bitmask ^ (1<

N,M=map(int,raw_input().strip().split(" "))
mat=[0]*N
for i in range(M):
	a,b=map(int,raw_input().strip().split(" "))
	mat[a-1] |= 1<<(b-1)

dp=[0]*(1<<N)
dp[0]=1
for mask in range(1,1<<N):
	for i in range(N):
		if (mask & (1<<i)):
			if (mat[i] & mask)==0:
				dp[mask] += dp[mask ^ (1<<i)]

print dp[(1<<N)-1]

まとめ

いつもより簡単目？