SRM537

TopCoder

2ヶ月ぶりくらいに参加してみました。

  • -

275. KingXNewCurrency

問題：A円とB円の組み合わせで払えるすべての金額を、X円とY円の組み合わせで払えるようにしたい。A, B, Xが与えられるとき、Yのとり方は何通り?

  • ふおお…なんだか数学ゲーっぽいぞ…。
  • まずは、A%X==0 && B%X==0 ならYがいらない子なので-1を返す。
  • とりあえず、AB円以上あたりは全部払えてしまいそうな気がする。
    • 適当なケースで、それっぽくなってることを確かめる
  • Yが大きすぎるといらない子になるので、Y≦max(A, B)で考えてよさそう
  • しかし、すべての組み合わせを支払い可能な条件とは一体…。
  • しばし考えた後、全探索すれば良い気がした。
  • AB円以降は払えそうだし、200^2円くらいまで調べて問題なければ良さそう。
  • 1≦Y≦max(A,B)≦200 だし、計算時間も余裕。
  • で、問題オープンから提出まで18分。
  • 某飲み会で「全探索が好きです」と言ってたとは思えない体たらくである。
  • 後に、診断人さんの放送で「A円とB円さえ払えれば十分！」と聞いて衝撃を受けた。

500. KingXMagicSpells

問題：部屋に数字ducks[i]が割り当てられていて、「部屋ごとにspellOne[i]とのxorをとる」「部屋iの数字を部屋spellTwo[i]に移動する」の片方をランダムに選び実行する操作をK回行う。操作後の部屋0の数字の期待値は?

  • 期待値にxorとか、なにこれこわい。
  • 取りうる数字の数が少ないのでは…と思ったけど、少なくとも2^(K/2)はあってやばい。
  • 期待値を持ってたとして、それに上手くxorを考える方法はないのか…。
    • [0,1]なら(1-期待値)にするだけで良さそうなんだけど…。
    • もしかして、ビットごとに考えれば良いんじゃね？
    • xorならビットごとに独立な操作だし、問題なさそうな気がする。
  • 組んでみたらサンプルが通ったので、提出した。
  • ここまで15分。Easyより早いとは…。

Challenge Phase

  • やばそうなケースも思いつかなかったのでまったりしてた。
  • -

結果：AC / AC / -- ，+0, 601.54 pt, 59位
レーティング：2374 -> 2411


250で無駄に考え過ぎたのと、時間あったのにHardに歯が立たなかったのが反省点。
そろそろHardと戦えるようになりたいです(´・ω・｀)