Hatena::Grouptopcoder

shinichiro_hの日記

 | 

2009-07-23

SRM445

02:01

まず開始前に contestapplet.conf を復元しておく。これが無ければ前回同様2問目間に合わなかったんじゃないかなあ。

2問時間ギリギリで解いて60位。なんか結構むずかしめの問題だったのかなあと思うに大健闘という感じかな。あと challenge しようとしてた子はやはり落ちてた。

275: 最初にうーんこれメッシュに切って…とか思ったら example に .5 がついてるのがあって諦めた。 50C25 は計算できない、できない、できない…とか考えてた。グリーディに近いのから取ってくのは…だめだなあとかなんとか。途中で気付いてたんだけど、解答に小数点があるとしても必ず .5 なので、0.5 でメッシュに切ってきゃ終わりだった。もっと早く気付けてしかるべきだったかなあ。なんか思考がループに陥るのはよくないなあ。

550: LL って書き忘れるな…忘れるな…忘れるな…とか思いながらやっていた。 define 1 1LL とかしたろうか。一番上のケタが 1 か 0 かは簡単に確定して、えーとその下はどうなるのかなぁ…と思って、要は前のケタの最終値に1くっつけたものと前のケタの k-2**(n-1)-1 までで一番大きかったものの最大値を求められればいいんだなぁと思った。一番大きかった方は単に再帰してやれば良くて、前のケタの最終値は同じ関数再帰してたけど、うーんこれは絶対おかしいなぁそうか最大値じゃなくて特定の位置の値だしなあと特定の位置を求める関数を書いた。そっちもまあ、一番上のケタはさっさと確定するので、1 くっつける場合に似たような再帰をしてやれば OK 。あとは k が -1 とかになるとかなしいので、剰余取る感じで。

今見るとこれ k=2**(n-1) の時にバグみたいなものがあるけどたまたまうまくいくようになってるなぁ。ラッキーです。

レートは1713とかになった。増えた。やった!

 |