どうかくE22とjit
実装: github.com
とりあえずナイーブに解いたやつ。鍋谷さんは「Rubyでは解けないくらいの計算量にしたつもりだった」と言っていたが案外解けている。
$ ruby -v ruby 2.6.0preview1 (2018-02-24 trunk 62554) [x86_64-darwin17]
MacBook Retina, 12inch, 2017 1.4GHz Core i7 メモリ16GB
$ time ruby test.rb ok 1 ok 2 ok 3 ok 4 ok 5 ok 6 ok 7 ok 8 ok 9 ok 10 ok 11 ok 12 ok 13 ok 14 ok 15 ok 16 ok 17 ok 18 ok 19 ok 20 ok 21 ok 22 ok 23 ok 24 ok 25 ok 26 ok 27 ok 28 ok 29 ok 30 ok 31 ok 32 ok 33 ok 34 ok 35 ok 36 ok 37 NG: 0 ruby test.rb 829.58s user 107.90s system 91% cpu 17:05.94 total
jit 版
$ time ruby --jit test.rb ok 1 ok 2 ok 3 ok 4 ok 5 ok 6 ok 7 ok 8 ok 9 ok 10 ok 11 ok 12 ok 13 ok 14 ok 15 ok 16 ok 17 ok 18 ok 19 ok 20 ok 21 ok 22 ok 23 ok 24 ok 25 ok 26 ok 27 ok 28 ok 29 ok 30 ok 31 ok 32 ok 33 ok 34 ok 35 ok 36 ok 37 NG: 0 ruby --jit test.rb 752.21s user 114.54s system 95% cpu 15:06.41 total
約10%の高速化、な気がする (あまりベンチマークに詳しくない)
別解法を考えた。枝刈りバンバンしていくことでなんとかならないか、というやつ。
そもそも実装がよくわからんけどミスっているのと「xが大きいときにはやくならないですね」という指摘を受けてばたんきゅ〜
n進数なのに木構造を使わなかったのはちょっとダメな気がした。
