Hatena::Grouptopcoder

ir5は引退した

 | 

2011-06-03

SRM 508

23:20

とりあえず色は戻ったけど…


DivLevelProblemNameStatus
1250DivideAndShiftPassedSystemTest
1500YetAnotherORProblemPassedSystemTest
11000みてないUnopened

250

  • 問題文の意味がよく分からないのでサンプルを見る → 素数で割ったりシフトしたりするらしい
  • 最初に全部シフトしてから素数で割るっていう風にしても多分問題ないはず.
  • for (N回ループ) { res=min(res, 左(右)シフトの回数+割り算の回数) } みたいなコードを書く.まぁサンプルは通る.
    • でかいケースで試す.TLE.うお…
    • 冷静に考えて1,000,000×割り算はやばげらしい
    • 答えとか20より大きくなることないんだしシフトの回数30回とかに制限してればいいや… 提出. 210.53pts
  • いやまて落ち着け,右シフトするときに巡回するようにできてないぞこれ… → 再提出orz.169.75pts

500

  • 慌てて500を開く
  • OR? よく分からないけど,繰り上がりの無い足し算をしたいらしい.
  • よく分からない… R[i]の値を上の桁から見ていくとか? (正解)
    • R[i]=000110100 などとして,↓みたいに分けられる.
R[i] = 000110100
       00011????   ← これはR[i]にびったりくっついてる感じがする(のであとの?についてまだ制約がある)
       00010????   ← これはR[i]から独立であるのであとの?については自由に決められる
  • うーん,もしかして↓みたいに分類すると上手くいくんでは? (不正解)
R[i] = 000110100
       0000?????
       00010????
       0001100??
       000110100
  • しかしパターン数がいかんせん多すぎる,60^10*もっと くらいかかる… いや,解析が甘い?
  • うーん,分からない… 時間だけが無駄に過ぎていく

  • 今のはどうもWrongAttemptっぽいので落ち着いて初心に帰ろう.
  • 上から見るんではなくて,下からみるとかはどうだろう? いや,どう考えてもだめ…

  • 最初の考えにおいて,各ビットが「まだぴったりくっついている」か「独立になった」かを場合分けしてDPすればいいんでないの?
    • ぴったりくっついているについて2通りあって,独立になったで1通りだから3^10*60状態くらい?
    • 違う,2^10*60通りでいい.
  • 書く.

  • 書いた.サンプル合う.
    • 最近サンプルの弱い問題ばかりだったので疑心暗鬼になりながら軽くテストする.TLEにはならない.答えはよくわからない.
    • 提出. 238.53pts.低い…

1000

  • 提出してる人多いけど残り時間的にどう考えても不可能なので250の撃墜ケース作る.

Challenge Phase

  • 怪しい人はそれなりにいる
  • よく分からない… みんな事前に素因数分解とかごついことしていて安易に撃墜できない.
  • 黄色い人で明らかに怪しい人がいて,容易に撃墜ケースが分からない人がいたので,手元に写経してChallengeすることにする
    • 書き上げた!! あとはCounterExampleを探すだけ…
    • なかなか見つからない… あ,落とされたorz

System Test

通る

oox 408.23pts 140th place

2196→2208


色は戻ったけどお慈悲っぽい…

よくわかりませんがみんな500提出するの速すぎると思います.

 |