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

2014-06-04

SRM 619

| 01:30

Div1 Easy (250) SplitStoneGame

問題

  • 複数の山それぞれに何個かの石がある
  • 二人で交互にプレイする
  • 一つの山を選ぶ
  • 残りの山から2つの山を選び、それぞれに1個以上の石を分配する
  • この操作ができなくなったほうが負け
  • 最適戦略下でどちらが勝つかを判定する

方針

結果

o-- 151.83pt 451st/681 rating 1528 -> 1504 (-24)

判定ゲー意外と時間かかった。


http://togetter.com/li/663337

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

2014-05-25

SRM 618

| 01:56

Div1 Easy (250) Family

問題

  • 簡易版の家系図がある
  • 配列parent1とparent2があり、親のindexが入っている
  • 親は片方が男で片方が女である
  • 可能な組み合わせかどうかを求める

方針

  • ひとつの組み合わせを決めたら、あとは再帰的に決めていって矛盾があるかどうかを見ればよさそう
  • なんとか提出
  • Passed System Test
  • union findに突っ込んで矛盾があるかどうかを見ればよかった
  • AとBがCの親で、AとDがEの親みたいなとき、BとDは同じ性別みたいにしてグルーピングして、矛盾があればNG
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_618/Family.cpp

結果

o-- +1 99.96 + 50 = 149.96pt 320th/532 rating 1544 -> 1528 (-16)

久々のunion find回。


http://togetter.com/li/659154

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

2014-04-13

SRM 606

| 23:55

Div1 Easy (250) EllysNumberGuessing

問題

  • 数当てゲーム
  • 1~1,000,000,000までの数を思い浮かべる
  • 予想値と、絶対値の差のペアが配列で与えられる
  • 数が一意ならその値、不定なら-1、嘘なら-2

方針

  • 情報が正しい場合、guesses[i]-answers[i]かguesses[i]+answers[i]の2択
  • answersを加味した数が1~1,000,000,000に収まらない場合は無視する
  • guessesとanswersの範囲により、情報が正しい場合には、プラスかマイナスのどちらかに必ず答えが含まれている
  • 一つの数だけN個を満たすとき、それが答え
  • 二つの数がN個を満たすとき、不定
  • それ以外の場合は嘘
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_606/EllysNumberGuessing.cpp

結果

o-- +2 153.58 + 100 = 253.58pt 135th/509 rating 1294 -> 1405 (+111)

最初に場合わけしたりすると意外とバグらせやすい問題。写経がんばった。


http://togetter.com/li/622772

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

2014-04-03

SRM 603

| 23:49

Div1 Easy (250) MaxMinTreeGame

問題

  • 頂点と辺からなる木が与えられる
  • それぞれの頂点には点数がある
  • 2人のプレーヤーが交互に辺を一つ選び除去する
  • 分離された一方を残し、もう一方を消す
  • 残りが頂点一つになったとき、その頂点の点数がスコアとなる
  • 先手が点数を最大化、後手が点数を最小化しようとするとき、先手の点数の最大値を求める

方針

結果

x-- 0pt 442nd/608 rating 1301 -> 1247 (-54)

思考力不足


http://togetter.com/li/612995

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