Hatena::Grouptopcoder

hotpepsiの練習帳

2014-06-07

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

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20140607