Ruby競プロTips(基本・罠・高速化108 2.7x2.7)

計測方法は、(10**6).times{ }のような最小限のコードです。 実際、制限時間が2秒だとして、10の7乗台前後から、想定解法でも厳しくなってくる印象です。 それ以前の1,000,000回(10の6乗)で2秒超えてTLEするなら、自分の書いたアルゴリズムを疑いましょう。 今のC++は10の7乗だと「余裕をもって間に合う」レベルらしいので、C++と比べるとRubyは10倍遅い感じです。 競技プログラミングでは、問題に与えられた要素数も 方針・アルゴリズムを考えるヒントになるので、このあたりの感覚はもっておくとよさそうです。 高速化手法のまとめ・見方 先に高速化のまとめがあった方が親切かと思い、簡単にまとめておきます。 (まとめの方にしか書いてないのもあります……) 本記事は、アルゴリズムの話も少し混じっていますが、アルゴリズムはRubyに限らないので、ほぼ触れてません。 「アルゴリズ

[katsyoshi]

いやーおもしろい

[rlho]

大作すぎる…！

[rin51]

かなり細かい

[mas-higa]

s/Array.new{ _1/Array.new(n){ _1/ 配列の結合に << が出てくるのが分からない。降順ソートは a.sort_by{ -_1 } かな?

[u1tnk]

先生！

[el-condor]

興味深い。後でじっくり読もう

[iga_k]

技の多才さがすごい!

[azumakuniyuki]

わりと前に調べてベンチマークした時にメソッド呼ぶより演算子の方が速いなぁと思ったけどRubocopにいろいろ言われたのを思い出した