AtCoder ABC #024 : Python練習編

ABC初1位でした。
FAはAしか取れませんでしたが…。
http://abc024.contest.atcoder.jp/assignments

A - 動物園

入場料が子供1人A円、大人1人B円の動物園がある。
ただし入場者がK人を超えると1人C円割引される。
子供S人、大人T人で入場したときの入場料を求めよ。

正規料金A*S+B*Tに対し、入場者(S+T)がK以上なら(S+T)*C円引けばよい。

A,B,C,K=map(int,raw_input().strip().split(" "))
S,T=map(int,raw_input().strip().split(" "))

F=A*S+B*T
if S+T >= K:
	F -= (S+T)*C
print F

B - 自動ドア

この自動ドアは、閉まっている状態で人が来るとT秒開く。
また、開いている状態で人が来ると、現在時刻からT秒先まで開いている状態が延長される。
人が来る時刻A[i]が与えられるので、ドアが開いている総時間を求めよ。

「次にドアが閉まる時間」「それまでドアが開いている総時間」を更新していく。

• 「次にドアが閉まる時間」は常にA[i]+Tに更新されることになる。
  • ドアが閉まっているときに人が来た場合、「それまでドアが開いている総時間」はT秒増える。
  • ドアが開いているときに人が来た場合、「それまでドアが開いている総時間」はA[i]+T -「次にドアが閉まる時間」分増える。

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

cur = -1
tot = 0
for i in range(N):
	A = input()
	if cur < A:
		tot += T
	else:
		tot += A + T - cur
	
	cur = A + T

print tot

C - 民族大移動

1～N番の町がある。
i番目の日は、L[i]～R[i]番の町内を自由に移動できる。
ここで(S,T)で構成されるK個のクエリが与えられる。
各クエリ、S番の町にいる人がT番の町に到達できる最短の日数を求めよ。

各クエリ、1日ずつ愚直にシミュレーションすればよい。
とにかく目的地に近づくように貪欲に移動していく。
今いる町が移動対象となる日が来たとき、

• S＜Tなら移動してS=min(T,R[i])に更新する
• S＞Tなら移動してS=max(T,L[i])に更新する
• S==Tになったら終了

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

for i in range(D):
	l,r=map(int,raw_input().strip().split(" "))
	L.append(l)
	R.append(r)

for x in range(K):
	S,T=map(int,raw_input().strip().split(" "))
	
	for i in range(D):
		if L[i] <= S <= R[i]:
			if S > T:
				S = max(L[i],T)
			elif S < T:
				S = min(R[i],T)
			
			if S==T:
				print i+1
				break

D - 動的計画法

10^8*10^8の２次元グリッドを考える。
左下のマスから初めて、隣接する上または右マスに移動する、という処理を繰り返す。
各マスには、左下からそのマスに移動する経路の組み合わせ数(mod 10^9+7)を書き込んでいく。

0-indexで下からr行目、左からc列目の位置のマスを(r,c)と表現する。
ここで、ある3マスに注目したところ、(r,c)の値は=A、(r,c+1)の値は=B、(r+1,c)の値は=Cであることがわかった。
A,B,Cの値からr,cを求めよ。

であることは容易に想像がつく。

ここで、より、
からとなる。
の値が分かれば、でr,cの値も求められる。

mo = 1000000007

def rev(v):
	return pow(v,mo-2,mo)

A = input()
B = input()
C = input()

AoB = A * rev(B) % mo
AoC = A * rev(C) % mo

RC1 = rev(AoB + AoC - 1)
R1 = AoC * RC1 % mo
C1 = AoB * RC1 % mo

print "%d %d" % (R1-1,C1-1)

まとめ

順調に解けて良かった。