🪓

(多分)(日本語では)初！ Rubyでimos法！

2021/02/24に公開

Ruby

Rubyで競プロやってるけど何か質問ある？

センスが平成の見出しはおいといて、競プロの模範解答はとかくRubyが少ない。
7割がc++,1/4がPython,残りがその他といった感じ。
それでも深さ優先探索問題や動的計画法問題はまだなんとかなりましたが、imos法(いもす法とも)で累積和問題を解く記事が全く見つかりません。
というわけで、英語もc++もPythonも読めない私が日本Ruby界imos法のパイオニアになります。

imos法とは

いもす氏が開発した手法で、累積和アルゴリズムの発展型です。

いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです
出入り口でのカウントのみをするという発想で入店時に +1 を，出店時に -1 を記録しておき，答えを求める直前に全体をシミュレートします

いもす法では、基本となる配列に「+1+1」や「−1−1」といった前のデータとの差分を入れておき、その配列の累積和をとることで同様の結果を得ることが出来ます。

いもす法では入口で加算、出口で減算をします(記録)。そして、記録の段階が終わったら前から順に足していきます(シミュレート)。

飛行機の高度で例えると「いついつの高度が何メートルか」を直接記録するのではなく、「いついつに何メートル上昇して、いついつに何メートル降下したか」だけを記録しておいて、最後にまとめて計算する感じでしょうか？
「そんなんで本当に計算量減るんかいな」という疑問にRubyで答えてみましょう。

例題

ABC183D - Water Heater

給湯器が1つあり、毎分Wリットルのお湯を供給することができます。N人の人がいます。i番目の人は時刻SiからTiまでの間 (時刻Tiちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分Piリットル使おうと計画しています。お湯はすぐ冷めてしまうので、溜めておくことはできません。すべての人に計画通りにお湯を供給することはできますか？

愚直法

入力例1を日本語に直すと「給湯器の供給量は毎分10L。人は4人いて、それぞれ1分から3分まで5L、2分から4分まで4L、3分から10分まで6L、2分から4分まで1L」となります。
愚直法で解くなら「配列インスタンスを用意して、1,2番目に5を代入、2,3番目に4を足し、3,4,5,6,7,8,9番目に6を足し、2,3番目に1を足した所で3番目の数値が11になり10を超えたのでNo」となるでしょうか。
7分も湯を出しっぱなしにしている3人目が代入・足し算を7回も増やしています。これが20万分とかになると足し算20万回になります。そんな奴が10億人いたら足し算200兆回、TLE間違いなしですね。

imos法

これがimos法では「配列インスタンスを用意して、1番目に5,3番目に-5を代入、2番目に4,4番目に-4を足し、3番目に6,10番目に-6を足し、2番目に1,4番目に-1を足す。最後に0番目から順に足していき、3番目の数値が11になり10を超えたのでNo」になります。
湯が7分出しっぱなしだろうが20万分出しっぱなしだろうが、書き込むのは始めと終わりの二回で済みます。10億人いても足し算20億回でOKです。
もちろん湯を20万分使ったからには配列の長さも20万、最後に20万回足し算する必要があります。しかしそれでも20億20万回。200兆とは比べ物にならないでしょう。

実際にやってみた

# frozen_string_literal: true

PEOPLE_COUNT, HOT_WARTER_SUPPLY = gets.to_s.split.map(&:to_i) # 配列から多重代入

# faucetは蛇口
faucet_schedule = []
people_i = 1
# rubyのループはwhileが一番早い
while people_i <= PEOPLE_COUNT
  # 蛇口開くタイミングがスタート、止めるタイミングがゴール、出す量の差分がボリュームディファレンス
  # begin,endを使わないのは入力支援が吸われるため
  when_start, when_goal, consume_volume_difference = gets.to_s.split.map(&:to_i)
  # 使う要素だけnilを0に置き換える
  faucet_schedule[when_start] ||= 0
  faucet_schedule[when_goal] ||= 0
  # 湯の出し始めと出し終わりだけを配列に記録する。何万分出していようが計算は一人2回
  faucet_schedule[when_start] += consume_volume_difference
  faucet_schedule[when_goal] -= consume_volume_difference
  # ここのインクリメントをよく忘れる
  people_i += 1
end

# これで蛇口をどれくらい緩めたり締めたりしたかがfaucet_scheduleに
# [nil, 5, 5, 1, -5, nil, nil, nil, nil, nil, -6]の形で記録された
# 最後にこれを前から見ていき、補給量を超えていないか確認
now_consuming_volume = 0
minute_i = 0
# 一時的に「供給は可能」と仮定しておき、一回でもNGだった場合は終了
buffer_can_supply = true
# 毎回sizeメソッドが走る時間がもったいないので、定数に書き込んでしまう
LAST_FAUCET_CONTROL_TIME = faucet_schedule.size - 1
while minute_i <= LAST_FAUCET_CONTROL_TIME
  # 現在消費量に差分を足していく。nilの場合は0
  now_consuming_volume += faucet_schedule[minute_i] || 0
  # 消費量が供給量以下に抑えられているか判定する。
  buffer_can_supply &&= (now_consuming_volume <= HOT_WARTER_SUPPLY)
  # ループ抜けはやらなくても間に合うと思うが、一応やっておく
  break unless buffer_can_supply

  minute_i += 1
end

if buffer_can_supply
  # pよりputsの方が早い
  puts "Yes"
else
  puts "No"
end

前半のループで入力を読んで差分配列を作成し、後半のループで0分目から順に消費量を計算しながら供給量を超えていないかチェックしています。

この記事で解説しなかった事

開発者様の記事にある通り、imos法は二次元や三次元にも適用できるそうです。
長方形を重ねるような問題が凄く嫌いなので、誰かRubyと日本語でサンプルコード書いて下さい。(他力本願)

Rubyで競プロやってるけど何か質問ある？

imos法とは

例題

愚直法

imos法

実際にやってみた

この記事で解説しなかった事

Discussion