Hatena::Grouptopcoder

hotpepsiの練習帳

2012-03-18

SRM 537 Div1

21:50

Easy (275) KingXNewCurrency

問題

  • アヒルの国の通貨は価値Aと価値Bの二種類ある。
  • 王がAとBに飽きたので通貨を価値Xと価値Yに変更することにした。
  • 変更後もAB貨幣システムでの価格が使えるYは何通りあるかを求める。

方針

Medium (500) KingXMagicSpells

問題

  • アヒル王国の王宮に部屋がN室ある。
  • それぞれの部屋にはducks[i]匹のアヒルがある。
  • 国王は一日一回、魔法の呪文を唱えることができる。
  • 呪文はSpell 1とSpell 2の二種類で、唱える確率は1/2ずつである。
  • Spell 1の効果は、各部屋のアヒルの数がXORされる。
  • Spell 2の効果は、各部屋のアヒルが一斉に部屋spellTwo[i]に移動する。
  • K日後のゼロ番目の部屋のアヒルの数の期待値を求めよ。

方針

結果

xo- 134.77*0 + 289.96 + 0 = 289.96 218th rating 1404 -> 1516

easyは40分かかって提出。mediumがぎりぎり解けそうだったので見直せなかった。凡ミス。10分くらいかけて方針を書き出したりしてもよかった。

mediumは残り30分でいけそうだったので書いた。medium解けるチャンスはほとんどないので、解けそうな回で通ったのは嬉しい。問題としては唯一div2hardで解いたことがあるSRM518に近い感じだった。

三月だけでレートが+320と、ラッキーが重なっていきなり黄色に。今年の目標(GCJ R1突破、一瞬黄色になる)の片方を早くも達成してしまった。とはいえまだeasyを落とすレベルなのでeasyメインで取り組む。

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