AtCoder ABC #013 : Python練習編

ABC#013に参加。
無駄にしょうもない2WAしてしまい微妙な順位。
http://abc013.contest.atcoder.jp/assignments

A - A

与えられた文字が何番目のアルファベットか答えよ。
文字コードで計算するだけ。

import sys

a=raw_input()
print (ord(a[0])-ord('A')+1)

B - 錠

0-9の10個の数字からなる回転式の錠がある。
今の数字aと錠を開く数字bがあるとき、数を増加もしくは減少方向に何回回せばよいか答えよ。

a<=bならmin(b-a,10+a-b)、b

import sys

a=input()
b=input()
print min(abs(a-b),10-abs(a-b))

C - 節制

現在の満腹度はHであり、ここからN日間を満腹度が0にならないようにすごしたい。
各日以下のいずれかの食事をとることができる。

• A円払って満腹度をB追加する食事をとる。
• C円払って満腹度をD追加する食事をとる。
• 何も食事をとらず満腹度をE減少する。

最少何円を払えば満腹度を0にせず済むか。

満腹度の最大値は無限なので、食事を何日か取るなら先に食事をとる日を持ってくるのが良い。
１つ目の食事をx日間、２つ目の食事をy日間とるなら、食事をとらない日が(N-x-y)日になるので、H + x*B + y*D - (N-x-y)*E > 0の範囲でx*A+y*Cを最小化する問題となる。

１つ目の式を変形するとy>((N-x)*E-H-x*B)/(D+E)となるので、xを総当たりしながらyの最小値を求め、x*A+y*Cの最小値を求めればよい。

import sys

N,H=map(int,raw_input().strip().split())
A,B,C,D,E=map(int,raw_input().strip().split())

ret = 1<<60
for TA in range(0,N+1):
	LD = N-TA
	hang = H+TA*B
	
	if hang > LD*E:
		TB=0
	else:
		TB=max(0,(LD*E-hang)/(D+E)+1)
	
	ret = min(ret, TA*A+TB*C)

print ret

D - 阿弥陀

N本の縦線に、M本の横線を加えたあみだくじが与えられる。
同じあみだくじをD個縦に連結すると、あみだくじを各縦線で始めた人は最終的に何番目の縦線で終わるか答えよ。

まず１回分のあみだくじ後の位置はM回位置のスワップを行うことでわかる。
後はそれをダブリングしていけばよい。
計算量はO(M+N*log(D))かな。

なお、Dの最大値が約2^30だからと言って30*Nの配列を作って処理するとPythonではTLEした。
今回は2*Nの配列を使って解決。

import sys

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

A = [[0 for i in range(N)] for j in range(2)]
B = [[0 for i in range(N)] for j in range(2)]
Rev = [0 for i in range(N)]

for i in range(0,N):
	A[0][i]=B[0][i]=i

for i in R:
	A[0][i-1],A[0][i]=A[0][i],A[0][i-1]

for i in range(0,30):
	cur=i%2
	tar=cur^1
	for x in range(0,N):
		A[tar][x]=A[cur][A[cur][x]]
		if (D & (1<<i))>0:
			B[tar][x]=A[cur][B[cur][x]]
		else:
			B[tar][x]=B[cur][x]

for x in range(0,N):
	Rev[B[0][x]]=x
	
for x in range(0,N):
	print Rev[x]+1

まとめ

やっぱりPythonで巨大配列のアクセスは遅いのかなぁ…。