100問解こう(2/100) SRM402 Div1 Easy RandomSort

与えられた配列を指定された方法でソートするとき、回数の期待値を求める問題。

 

解法は少し考えたのち、幅優先でのシミュレーションを選択。

しかし、しばらく期待値でない謎の値を求めていた上に、System TestでN=8のときuncaught exceptionが出てしまった。

Xcodeのデバッガとにらめっこした結果、queueが爆発したらしい?ことが分かったので解法を変える。

 

別の解を探すべく長考したが結局解けなかったので、Google先生に頼ったらメモ化せよとのこと。

最初に書いたものはメモ化しにくかったため、再帰に書き直してさっくり提出……できず死ぬほどハマる*1

 

もしやと思い調べると、なんとDiv2ではHard(1000)だったらしい。

そりゃ解けるわけないと諦めて参考の解法を真似して終了。

けど、Div2では58人、Div1では334人*2解いているんだから解けるようにならないとなあ。

 

参考

メモ化再帰で、それぞれの状態に対し期待値を求める解法

http://d.hatena.ne.jp/aomori-ringo2/20101227/1293456299

 

余談

流行を意識してgoto fail;を入れたら落ちた*3

 

 

*1:期待値をソート完了後に交換回数*確率で求めようとしていたためうまく再帰に落とせなかったらしい。参考の解法はそれぞれの状態について直接期待値を求めている。

*2:http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm402

*3:ちなみに1週間ぶり2回目で、1回目も不注意によるコーナーケースが原因