[競プロ] TLEの謎と剰余で答える意味
該当の問題
この問題は何をやっても TLE になる。最終的には AC で通している方のコードを写経するかのごとく、ほぼ同じにしても TLE になるのでもうわけがわからなかった。
あと、この問題では答えを 10**9 + 7 で割った余りで答えよと書いてあったので最後に剰余にしておいた。剰余で答える問題はこれまでもそうしてきた。
TLE の原因
大きな値を扱っているからだった。
Ruby の場合は内部でがんばって大きな値を扱えるようにしてくれている。ただ、それは利便性と計算時間のトレードオフの関係でもあった。だから、大きな値を扱うと計算時間が増えてしまうのだった。
require "active_support/core_ext/benchmark"
def _ = "%.1f ms" % Benchmark.ms { 1000000.times { yield } }
a = 2**10 # => 1024
b = 2**100 # => 1267650600228229401496703205376
c = 2**1000 # => 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
_ { a + a } # => "43.5 ms"
_ { b + b } # => "94.8 ms"
_ { c + c } # => "205.5 ms"
したがって競プロの攻略に限っていえば、Ruby であってもオーバーフローを気に掛けないといけなかった。
こちらの記事がわかりやすい。
TLE の対策
演算するたびに 10**9 + 7 で丸める。こちらの記事によると、
足し算と掛け算のとき毎回やれ、とのこと。
最後に一回やるだけではいけなかったのか。たしかに最後の一回でよいなら問題文にも「最後に〜」と書いてあるのが自然だろう。それを明言しないのは、大袈裟に言えばただの不親切ではなく自分のような初心者をミスリーディングさせるためだったのである。
具体的な対策1. あちこちで丸める
足し算や掛け算をしている箇所を地道に丸めていく。ただ、sum は内部で足し算を行なうので足し算に置き換える必要がある。
たとえば、
av.sum
だと、
av.reduce(0, :+)
にする程度ではなく、
acc = 0
av.each do |value|
acc += value
end
まで展開した上で、さらに
acc = 0
av.each do |value|
acc = (acc + value).modulo(MOD)
end
とする。
なんというか、ここまで Ruby の長所を殺さないといけないなら競プロをやる意味がなくなる。
具体的な対策2. モンキーパッチ
足し算と掛け算を内部で丸める。ただ sum が少しやっかいで、
-
Integer#+を呼んでいない - Array と Enumerable の sum は異なる
ため、二カ所の sum を、Integer#+ を使う方法に置き換える必要がある。
MOD = 10**9 + 7 # => 1000000007
Integer.prepend Module.new {
def +(other) = super.modulo(MOD)
def *(other) = super.modulo(MOD)
}
[Array, Enumerable].each do |klass|
klass.class_eval do
def sum(init = 0, &block)
if block
collect(&block).reduce(init, :+)
else
reduce(init, :+)
end
end
end
end
このようにしておけば、
v = 2**100 # => 1267650600228229401496703205376
v + v # => 952742563
v * 2 # => 952742563
[v, v].sum # => 952742563
2.times.sum { v } # => 952742563
自動的に丸めることができる。
ただし負の値は正になる点に注意する。
-1 + 0 # => 1000000006
1000000007 と 998244353 は何が違う？
なぜ 998244353 なのか？ によると、
- 1000000007 はもう古い
- 998244353 の方が主流
- 998244353 の方が便利
とのこと。
何が便利なのかはよくわからないが、どちらを使っているかで問題の時代性がわかる。
Discussion