(8/9に書いたもの)
Epoch@まつやま参加記
7月にEpoch@まつやまを見つけてid:peryaudoと一緒に参加することにした。
で、予選問題がどんなものかと思っていたんだけど全部結構簡単で、最適化しないソースで1時間半くらいで終わった。
1番はvector型をキーとしたマップを作るって思いついてから20分くらいで終わった。
2番はちょっと実装重かったので40分くらいかかった。
3番は分数をdouble型に変換したものと、そのままをstringで管理したものをpairで管理し、
double型の大小関係でソートするというもので、誤差がただ怖かったので、デバッグ含め30分くらいかけて作った。結局誤差は生じなかったみたいだが。
で、id:peryaudo君にも独自の方向でソースを作ってもらって、それを照らし合せてアイデアを積み重ねていった。
結局各問題の解法の方針としては
一番:先ほど書いた方法そのまま。シンプルだしお気に入り。
二番:素数生成アルゴリズムはエラトステネスのふるいを最適化したもの。アルファベットのテーブルなど作り無駄な計算を削った。素数部分についてはきちんとループで生成している。
Submitした後にstring型に一時格納するのはまずかったかな?と思ったがputchar()のコストがよく分からないし、まあいいだろうという結果に落ち着いた。
テストケースだとどのケースもtimeで0.2s~0.3sだった。どんなケースでも律儀に1000万までの素数生成しているので仕方ない。当初書いたソースは1.1sでしたw
三番:簡易分数クラス作って<演算子をオーバーロードする。そしてそれをmapで管理。イメージより相当速かった。これは完全にid:peryaudoのアイデア。
そもそもの計算時間が一瞬なので、微々たる差になるが、それでも明らかにdouble型を使った場合に比べ2倍早かった。あとメモリ使用量も少ない。
予選のコーディングに掛けた時間、2日間でしたがすごく楽しかった。
(ここから10/3)
1番、あとで気づいたけど、mapじゃなくてsetでよかった。
もうひとつ、setのsetつくるよりvectorのsetつくった方が高速だった。むしろvectorのvectorをuniqueして消したらもっと高速だったんじゃないかとか思ったけど再提出はやめた。
とりあえず7月時点でSTLの使い方とか未熟だったけど、それなりに高速・省メモリなコードが書けたんじゃないかって思ってます。