🐸

[競プロ] TLEの謎と剰余で答える意味

2024/04/17に公開

Ruby

AtCoder

競プロ

tech

該当の問題

この問題は何をやっても 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 の方が便利

とのこと。

何が便利なのかはよくわからないが、どちらを使っているかで問題の時代性がわかる。