CODE FESTIVAL 2014 予選B : Python練習編

CODE FESTIVALに参加。
完答したものの、色々無駄の多い実装で時間を食ってしまった。
http://code-festival-2014-qualb.contest.atcoder.jp/assignments

A - あるピアニスト

２つの数値が与えられるので大きな方を返せ。
pythonでmaxを使えばよい。

import sys

a,b=map(int,raw_input().strip().split())
print max(a,b)

B - 歩く人

プレイヤーはi日目にA[i]歩歩く。計K歩に達するのは何日目か。
KからA[i]を引いていって0を切る日を答える。

import sys
 
N,K=map(int,raw_input().strip().split())
for i in range(0,N):
	K -= input()
	if K<=0:
		print (i+1)
		break

C - 錬金術士

S1,S2,S3は偶数であるL文字からなる。
S1とS2からL/2文字ずつ選び、それらを並び替えてS3を構築できるか答えよ。

本番は最大フローで通した。グラフの頂点数は少ないので、Pythonで最大フローを流しても間に合う。

またより効率的な方法は、A-Zの各文字に対しS1,S2,S3中の登場回数を求めたうえで、S1から最小～最大で何文字取ればS3が作れるか範囲を求め、それがL/2を含むか判定すればよい。

ある文字をS1から取る文字数は、最小値はmax(0,S3-S2)、最大値はmin(S1,S3)文字である。

import sys

S = []
S.append(raw_input().strip())
S.append(raw_input().strip())
S.append(raw_input().strip())

C = [[0 for j in range(26)] for i in range(3)]
L = len(S[0])

for i in range(0,3):
	for j in range(0,L):
		C[i][ord(S[i][j])-ord("A")] += 1

mi = ma = 0
for i in range(0,26):
	if C[0][i]+C[1][i] < C[2][i]:
		mi = ma = 0
		break
	mi += max(0, C[2][i]-C[1][i])
	ma += min(C[0][i], C[2][i])

if mi <= L/2 and L/2 <= ma:
	print "YES"
else:
	print "NO"

D - 登山家

N個の山が一列に並んでおり、高さはH[i]である。
各山の山頂には山小屋がある。
各山小屋は、前後の山のうち高さが自分の山以下の範囲の山小屋を見ることができる。
各山小屋から見える他の山小屋の数を答えよ。

自分は本番はSegTreeを二分探索で繰り返したが、Pythonだと間に合わない。
スタックを使ったO(N)解法でギリギリ間に合う。

山小屋を配列の先頭および後方から順に２回処理する。
スタック中には、まだ山小屋が見えなくなる高さの山が出ていない山の番号を積んでいく。
このスタック中の山は、高さが降順になる。
新たな山を処理するとき、スタック内の山の高さと順次比較して、スタック内の山の方が低い場合、そのスタック内の山の見える限界は今処理している山となるので、山小屋の数を加算してpopする。
スタックの中身を処理し終わったら、新しい山を追加していく。

import sys

N = input()
H = [0]*N
R = [0]*N
stack = []

for i in range(0,N):
	H[i]=input()

for i in range(0,N):
	while len(stack) > 0 and H[stack[-1]] < H[i]:
		R[stack[-1]] += i-stack[-1]-1
		stack.pop()
	stack.append(i)

for i in stack:
	R[i] += N-i-1

stack = []
for i in range(0,N)[::-1]:
	while len(stack) > 0 and H[stack[-1]] < H[i]:
		R[stack[-1]] += stack[-1]-i-1
		stack.pop()
	stack.append(i)

for i in stack:
	R[i] += i

for i in range(0,N):
	print R[i]

まとめ

A,Bは数秒差で1位を逃した。
C,Dは無駄に難しい解法を使い、時間をロスしてしまい残念。