CODE FESTIVAL 2015 予選A : Python練習編

CODE FESTIVAL予選に参加。
普段と違うPCのため操作ミスでタイムロス。
これがなければ１位も狙えたか…？
http://code-festival-2015-quala.contest.atcoder.jp/assignments

A - CODE FESTIVAL 2015

末尾が2014である文字列が与えられる。末尾を2015に変換して出力せよ。
最後の１文字を変えるだけ。

s=raw_input()
print s[0:(len(s)-1)]+"5"

B - とても長い数列

N要素の数列A[1..N]がある。
空の数列S=[]から初めて、S := S + [A[i]] + Sのように数列を連結していく作業をi=1～Nで順に行う。
全要素の総和を求めよ。

Sの総和についてもsum(S) := sum(S) + A[i] + sum(S)の関係があるので、順次sum(S)を計算していくだけ。

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

for i in range(N):
	C = C*2 + A[i]
print C

C - 8月31日

N個の宿題がある。
それぞれ自力で解くとA[i]分、他人の解答を写すとB[i]分かかる。
すべての宿題をT分以内に完了するには、最少何個の宿題を写せばよいか。

１個も写さない場合、sum(A)分かかる。
そこから１問写すとかかる時間が(A[i]-B[i])分減る。
そのため(A[i]-B[i])が大きい順に写す対象としてよい。

よって(A[i]-B[i])を先に降順にソートしておき、sum(A)から合計がT分以下になるまで、(A[i]-B[i])を引いていき、引いた回数を出力すると解。

N,T=map(int,raw_input().strip().split(" "))
L=[]
sum = -T
for i in range(N):
	A,B=map(int,raw_input().strip().split(" "))
	sum += A
	L.append(B-A)

ret = 0
L.sort()
for d in L:
	if sum > 0:
		ret += 1
		sum += d

if sum > 0:
	print -1
else:
	print ret

D - 壊れた電車

N両の連結した車両をM人で検査する。
初期状態でM人はX[i]両目の車両にいる。
各人検査にかかる時間は0で、隣の車両に移動するのに1の時間がかかる。
全車両を検索するのにかかる最小時間を求めよ。

実は既出。時間を二分探索し、各人先頭から詰めながら順番に時間内に検査できる範囲を求めていく。
初期位置から前も後ろも検査する場合、先に前に行って折り返す場合と後ろに行って折り返す場合で検査できる車両の多い方を選ぶ必要があるので注意。
Codeforces #200 Div1. C. Read Time - kmjp's blog

なお、以下の解は80点の部分点しか取れない。C++で同様に実装すると100点取れる。

import sys

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

if N==M:
	print 0
	sys.exit()

X=[]
for i in range(M):
	X.append(input())

def dodo(v):
	right = 0
	for x in X:
		if right >= x-1:
			right = x+v
		else:
			if x-v > right+1:
				return False
			right = max(x+(v-(x-right-1))/2,x+(v-(x-right-1)*2))
	
	return right >= N


ret = 0
for i in range(30,-1,-1):
	if not dodo(ret + (1<<i)):
		ret += 1<<i

print ret+1

まとめ

DはPythonで満点取れるのかなぁ。
120位以内に入るのに満点必須な状況だと、普通に実装してLLだとTLEって結構厳しい条件だな。