hotpepsiの練習帳

SRM 620

着想 | 23:15

Div1 Easy (250) PairGame

問題

• 1以上の二つの整数のペア(x,y)がある
• 次のターンで(x+y,y)か(x,x+y)のどちらかにできる
• (x,y)からはじめて(a,b)と(c,d)のどちらにでも到達できる数のうちx+yの最大値を求める

方針

• (x,y)からはじめて(a,b)までの間の各地点で(c,d)に到達可能か探索
• stack overflowで死ぬ
• 書き直し
• 値(p,q)に到達するには、片方の値はx+yなので、小さいほうを引いたものからしか到達できない
• つまり逆方向の探索だと、値は一意になる
• (a,b)と(c,d)について、a>cかb>dのときは、a,bを一手戻し、そうでなければc,dを一手戻し、一致するまで繰り返す
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_620/PairGame.cpp

結果

GCJに備えて仮眠したら寝過ごした。連続出場記録が87で途切れてしまった。

SRMをベースに生活スケジュールが組まれているということを再認識したのであった。

とはいえ出ていてもたぶん0点だったと思う。

http://togetter.com/li/665676