Hatena::Grouptopcoder

ir5は引退した

 | 

2010-08-04

SRM 478

02:20

りんご先生の回.

DivLevelProblemNameStatus
1250CarrotJumpingPassed System Test
1500KiwiJuicePassed System Test
11000開けただけOpened

250

  • 問題文にうさぎが.これはもしや…
  • ある数xが与えられる.xを4x+3に変えるor 8x+7に変えるという操作を最小回数繰り返して,x≡0(mod M) (Mは10億くらい)となるようにしたい.必要な操作の最小回数を求めよ.操作が10万回以内では不可能なときは-1を返せ.
  • 探索空間すごい広い
  • なにこれ… 全然分からん…
  • 4x+3,8x+7というのでうまいことが出来るのかもしれないけど… うーむ
    • mod4で考えると常に≡3だ. …だからどうした.
  • 5分くらい考えても全然分からくてさすがに焦るので適当に探索してみることに….いいのかどうかは知らない.
  • TLE.ですよねー.
    • あ,訪問した点弾いてなかった.弾くようにする.
    • …なんか0.3secくらい掛かるけど間に合う.ランダムにテスト作っても大丈夫っぽい.
    • ほとんどのケースで-1になるけどそういうもんなのか? で,どのケースでも0.3sec程度しか掛かってない.
    • 何故これでいいのか全然分からない.全然分からないけどとりあえずテストは大丈夫そう. → submit.ここまで15分.

  • 提出後も結構テストをする. 良く分からないけどなんか大丈夫そうなので次へ.

500

  • 水を注ぐ問題.
  • ボトルA,Bのうち,片方が満タンor空なら,AとBに対して操作をしても意味はない.つまり,満タンor空のボトルは操作の対象から取り除ける.
  • 満タンor空になったボトルを除外していくとした場合,操作に順番って関係あるのだろうか… つまり操作を*として,(A*B)*C と A*(B*C) は等価か?
    • 等価っぽい.結局ボトルA,B,Cに入ってる水の総量だけを見ればいいことになる.
  • ということは,ある個数のボトルに対して,どんな操作の順番でやったとしても結果は一緒になる.
  • DPかなぁ
    • S:ボトルの集合として,
    • E[S] := Sを全部混ぜたときの価値の総和
    • D[S] := Sを使って得られる最大の価値
    • とすると,
    • D[φ]=0
    • D[{u}∪S']=max_{S'=T+U} ( E[{u}∪T]+D[U] )
    • とかでできるんでは.
  • 計算量は大丈夫なのかしら.最悪O(2^n*2^n)にならないか…?
  • 部分集合の生成で2^n個いることは滅多にないし,n<=15程度ならそこまでひどいことにはならなさそう. (注:あんまり深く考えてない)
  • やろう.書く.

  • ビット操作が結構面倒くさい(特にSの部分集合を取るところ) 適当にICPCのチームライブラリから取ってくる
  • テスト.
    • 間違い.まぁですよね.
  • E[S]が違うっぽい
    • ceil(a/b)とかで違う値出してた.修正.天井関数は毎回どう書いたらいいか悩んでるような気がする….
  • まだ合わない
  • 部分集合の生成のところが間違ってた.修正.
  • サンプルテスト通った.
    • 自分でも簡単なのを作って試す.大丈夫っぽい.サンプルも強固そうなのがあるし問題なさそう… → submit.ここまで55分くらい.

1000

  • 開けただけ.

  • 暇なので250,500のテストをひたすらしてた.
  • 500提出してる人が部屋内で自分しかいなくて寂しい
  • division summaryを見る.全体で50位.両方通ると結構いいけどどうだろうなぁ….
    • Codeforcesでやったら強いRAVEman氏とかが500でCompiledのままになってたりする.うーむ,なんか怖い.そのほか赤色の人も割と下の方にいたりした.

Intermission

  • 普通に休憩した.

Challenge Phase

  • 他の人250しか提出してないので250を見る.
  • 自分のと全然方針違う… なにこれ.2x+1とか書いてるけどこれ駄目なんじゃないの?
  • 撃墜ケースらしきものを作る.作った.ローカルで確認.あれ,合ってる.なんで?
  • あー,そうか
    • f(x)=2x+1とすると,4x+3=f(f(x)), 8x+7=f(f(f(x))) なので,生成される数はfで高々30万回合成されてできる数にしかならない!
  • そういうことだったのか… 全然分からなかった.(普通に何かの線形変換なのかな程度にしか見えなかった)

  • サンプルも強固だったから間違いは少ないだろうし500提出している人間はいないし何も出来ない
  • 終了

System Test

両方通った.


o o x 462.69 45/694

1732 -> 1887


順位も良かったのでかなりあがりました.

目標だった1800代も突破できたのでこれを頑張って維持していきたいところですが,はてさて.

 |