kmjp's blog

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

AtCoder ABC #031 : Python練習編

解法自体に戸惑うことはなかったが、無駄に変数名ミス等繰り返してタイムロス。
http://abc031.contest.atcoder.jp/assignments

A - ゲーム

攻撃力Aと守備力Dが与えられる。
どちらか片方だけを1加算できるとき、攻撃力と守備力の積を最大化せよ。

攻撃力に加算するケースと守備力に加算するケース両方試して大きい方を答えればよい。
もしくは元々小さい方に加算すればよい。

A,B=map(int,raw_input().strip().split(" "))
print max((A+1)*B,A*(B+1))

B - 運動管理

週の運動時間をL分以上H分以下にしたい。
過去N週の運動時間をそれぞれA[i]分とする。
各週条件を満たすには後何分追加で運動すればよかったか(もしくは何分運動しても条件を満たせないか)答えよ。

すでにA[i]>Hならその週は条件を満たせない。L≦A[i]≦Rなら運動不要。A[i]<Lなら(L-A[i])分だけ運動する。

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

for i in range(N):
	A = input()
	
	if A>H:
		print -1
	elif A>=L:
		print 0
	else:
		print L-A

C - 数列ゲーム

N要素の数列Sがある。
Sに対し、先手と後手は異なる1要素を1回ずつ選択する。
Sのうち、両者の選択した要素及びそれらで囲まれた要素からなる数列をTとする。
Tの奇数番目の要素は先手、偶数番目の要素は後手のポイントとして加算される。
後手は自分の得点が最大となる要素のうち、最も左の要素を取りに行くことが分かっている。
先手は最大何ポイント得られるか。

先手のとる手を総当たりしよう。
先手の手を決めたら、後手の手を総当たりすればそのうち後手が取る手(すなわち後手のポイントが最大となる要素)がわかる。
同時にその時の先手のポイントもわかる。
よって各先手の手に対する先手のポイントの最大値を求めればよい。

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

ma = -5000
for x in range(N):
	maxa = maxb = -5000
	
	for y in range(N):
		if x == y:
			continue
		V = [0,0]
		i = 0
		for z in range(N):
			if (x-z)*(y-z) <= 0:
				V[i] += A[z]
				i ^= 1
		
		if V[1] > maxb:
			maxa,maxb = V
	
	ma = max(ma,maxa)

print ma

D - 語呂合わせ

1~Kの数字と、N個の語呂合わせのデータがある。
1~Kの数字はある1~3文字のアルファベットからなる単語にごろ合わせできることが分かっている。
各語呂合わせのデータでは、1~Kの数字複数桁からなる元となる整数と、各数字を語呂合わせした単語連結した文字列が与えられる。
個々の数字に対応する語呂合わせの単語を求めよ。

各数字は1~3文字に対応することが分かっているので、各数字が何文字のアルファベットに対応するか、3^K通り総当たりすればよい。
各数字が対応するアルファベット数を決めたら、各語呂合わせのデータを見て、長さが合うか、また各数字に対応する単語が一意になるかチェックすればよい。

K,N=map(int,raw_input().strip().split(" "))
D = []

for i in range(N):
	v,w=raw_input().strip().split(" ")
	S=[]
	for c in v:
		S.append(ord(c)-ord('1'))
	D.append((S,w))

fact = [1]
for i in range(10):
	fact.append(fact[-1]*3)

for mask in range(fact[K]):
	lenp = []
	R = [""]*K
	
	for i in range(K):
		lenp.append(mask/fact[i]%3+1)
	ok = 1
	
	for v,w in D:
		tlen = 0
		for r in v:
			tlen += lenp[r]
		
		if tlen != len(w):
			ok = 0
			break
		
		pos = 0
		for r in v:
			s = w[pos:pos+lenp[r]]
			
			if R[r] == "":
				R[r] = s
			elif R[r] != s:
				ok = 0
				break
			pos += lenp[r]
	
	if ok:
		for r in R:
			print r
		break

まとめ

ABがFA取れたのは良かったけど、CDのミスが多かった。

広告を非表示にする