AtCoder ABC #015 : Python練習編

ABC015はリアルタイム参加できなかったので、別途練習。
http://abc015.contest.atcoder.jp/assignments

A - 高橋くんの研修

2つの文字列が与えられるので、文字列長が長い方を返せ。

そのまま実装するだけ。

A=raw_input().strip()
B=raw_input().strip()

if len(A) < len(B):
	print B
else:
	print A

B - 高橋くんの集計

N個のソフトウェアと、そのバグ数A[i]が与えられる。
バグがあるソフトウェアにおける、バグ数の平均値を小数点以下切り上げで答えよ。

バグ数と対象ソフトウェアの合計をだし、切り上げ除算すればよい。

N=input()
A=map(int,raw_input().strip().split(" "))

x=0
b=0
for i in A:
	x += i
	if i > 0:
		b += 1

print (x+b-1)/b

C - 高橋くんのバグ探し

N個の質問と、それぞれの回答選択肢がK個ずつある。
各問題の各選択肢は解答値T[i][j]を持つ。
各質問で１個ずつ選択肢を選ぶ場合、解答値のxorが0になることはあるか。

DFSか、K^N個全部総当たりすればよい。

import sys
N,K=map(int,raw_input().strip().split(" "))
A=[]

for i in range(0,N):
	A.append(map(int,raw_input().strip().split(" ")))

for i in range(0,K**N):
	v = 0
	for j in range(0,N):
		v ^= A[j][i // int(K**j) % K ]
	
	if v == 0:
		print "Found"
		sys.exit(0)

print "Nothing"

D - 高橋くんの苦悩

N個のスクリーンショットは幅がA[i]、重要度がB[i]である。
スクリーンショットをK個以下かつ幅の合計がW以下となるように選択し、重要度の合計を最大化せよ。

オーソドックスなDP。
スクリーンショットの選択数と、幅の合計値に対して重要度の合計値の最大値を保持しても良いし、スクリーンショットの選択数と、重要度の合計値に対して幅の合計値の最小値を保持しても良い。

C++ならどちらでも間に合うが、幅の合計値が重要度の合計値より若干大きいため、前者だとTLEする。

W=input()
N,K=map(int,raw_input().strip().split(" "))

dp=[[12000000 for i in range(5001)] for j in range(51)]
dp[0][0] = 0

tot=0
for i in range(N):
	A,B=map(int,raw_input().strip().split(" "))
	
	for x in range(i,-1,-1):
		for y in range(tot,-1,-1):
			dp[x+1][y+B] = min(dp[x+1][y+B], dp[x][y]+A)
	tot += B

ma=0
for i in range(0,K+1):
	for j in range(0,5001):
		if dp[i][j]<=W:
			ma = max(ma,j)

print ma

まとめ

D問題、LLにはかなり微妙な制限だな。