Codeforces #328 Div2 C. The Big Race

グダグダの出来だと思ったら、なぜか割といい順位に落ち着いた。
http://codeforces.com/contest/592/problem/C

問題

2人でレースを行う。
スタート地点から見て、先手はWの倍数、後手はBの倍数の距離にしか移動できない。
両者ともゴールを通り過ぎない範囲で移動可能な範囲で前に進んでいく。
ゴール地点の距離が1～Tの範囲の整数から等確率で選ばれるとき、両者の到達位置が等しくなる確率を求めよ。

解法

両者が同じ位置で止まるのは、ゴールに最も近い到達位置がLCM(W,B)の倍数の時である。
さらに言えば、距離がLCM(W,B)*P + Q (0≦Q＜min(W,B))で表現できる範囲である。
1～Tのうち、上記式の形で表現できる範囲を求めよう。
T,W,Bが割と大きいので、下記コードは念のためPythonを用いている。

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

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a%b)

if A>B:
	A,B=B,A

G=gcd(A,B)
L=A*B/G

tie = (T/L)*A + min(A-1,(T%L))

g=gcd(tie,T)
print "%d/%d" % (tie/g,T/g)

まとめ

問題の内容はともかく、入力の最大値がDiv2Cクラスではないよなぁ…。