hotpepsiの練習帳

SRM 537 Div1

21:50

Easy (275) KingXNewCurrency

問題

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

方針

• P=A*n+B*mが表せることが必要
• GCDとLCMかな...と思い込んでだいぶ時間を浪費
• いろいろ書き直す
• A=X*i+Y+j、B=X*i+Y*jと表せればよさそう
• 全部満たす場合(-1)の判定条件を書き間違ったまま提出
• 書き直し
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_537/KingXNewCurrency.cpp

Medium (500) KingXMagicSpells

問題

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

方針

• doubleに突っ込んでみる
• 小数点のXOR...? 意味がわからない
• 1ターン毎に考えると、移動かXORしかない
• ビット毎に独立して考えてよい
• 桁毎にdoubleで持ってターン毎にシミュレーションしてみる
• サンプルと合ったので提出
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_537/KingXMagicSpells.cpp

結果

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メインで取り組む。