オフラインリアルタイムどう書く P.2 の実装例
これは何？
オフラインリアルタイムどう書く P.2
の、問題
二進数を回す
の実装例。
実装例集積所は下記。
実装
素朴な実装
まずは素朴に。
# "1[3]3" などを 0b100011 などに変換する
def parse(s)
r=0
s.scan(/((?:\[?)\d+(?:)\]?)/) do |m,|
if m[0]=="["
r<<= m[1..-2].to_i
else
v = m.to_i
r <<= v.to_s(2).size
r |= v
end
end
r
end
# n を ro÷b 回転 回す
def rot(b,n,ro)
r=0
lo=0
(1...).each do |edge|
len = edge*b
mask = (2**len-1)
org = (n>>lo) & mask
shift = ro*edge
rotated = ((org<<shift) | org>>(len-shift)) & mask
r |= rotated << lo
lo += len
return r if n<2**lo
end
end
# 解く
def slow(src)
bs, ns = src.split(" ")
b = bs.to_i
n = parse(ns)
h=Hash.new{ |h,k| h[k]=[] }
b.times do |r|
h[rot(b,n,r)].push r
end
mm = h.keys.minmax
# pp h
mm.map{ |m| h[m].sort.join(",") }.join("/")
end
ruby なので、多倍長整数が使える。
素直に二進数にし、b角形なら b通りの回転を全部試す。
回転した結果得られる値をキー、回転量の配列を値にする Hash を作り、全部突っ込む。
minmax → sort → join(",") → join("/") で完成。
手元の MacBook Pro (Apple M1 Pro 非Max with ruby 3.4.5) で、10分ぐらい。
上記を 40〜50分ぐらいで書ければ勝利という目算だった。
速い実装
スパース性
テストデータを見ると、1000万桁の二進数がある。比較演算一回で数十万回のループが回る。
四則演算するたびに数メガバイトのコピーが発生する。
ということで問題文や図の後半をよく見ると、何万ビットあろうともその大半はゼロで、1のビットは多くても 100ぐらいしか無いということがわかる。
いわゆるスパースなビット列。
ということで、通常の2進数ではなく「1のビットがある桁を覚える」という作戦で行くと扱うデータ量が少なくなる。
探索範囲
テストデータを見ると、9万角形とかがある。
素朴な実装では 9万回のループを回していたわけだけど、そんなに調べる必要はない。
最大値となるのは「回転量を増やしても減らしても値が小さくなる」という場所に 1 があるときだけ。
最小値となるのは「回転量を増やしても減らしても値が大きくなる」という場所に 1 があるときだけ。
ということで、最小値になるのは下図左の範囲に 1 があるときだけ。最大値になるのは下図右の範囲に 1 があるときだけ。
いずれにも 1 が無いケースについては調査不要となる。
実装例
前述の 二点を入れると、手元の環境で 1秒以下でテストが終わる。
# 正の整数 n が 2進数で何桁かを計算する
# 例: 0b1 => 1, 0b10 => 2, 0b1111 => 4
def binLength(n)
n.digits(2).size
end
# n を 2進数で表したときに 1 になっている桁の位置を配列で返す
# 例: 0b101011 => [5,3,1,0]
def ones(n)
binLength(n).downto(0).select{ n[_1] !=0 }
end
# "1[80]1" などを [81,0] などに変換する
def parse(s)
s.split(/\D/).each_slice(2).each_with_object([]) do |(n,gs),o|
g = gs ? gs.to_i : 0
b=ones(n.to_i).map{ _1+g }
offset = b.first + 1
o.map!{ _1 + offset }
o.push(*b)
end
end
# b 角形で 番号 n の場所を返す。
# @return [p0,p1,e] p0 はその b角形の番号の最小値、p1 は一つ外側の多角形の最小値。e は1辺の長さ。
def poly_ix(b,n)
p0=0
for e in (1...) do
p1 = p0+ e*b
return [p0,p1,e] if n<p1
p0 = p1
end
end
# nums を r÷b 回転 回す
def rotate(b, nums, r)
nums.map{ |n|
p0, p1, e = poly_ix(b,n)
((n-p0) + r*e) % (p1-p0) + p0
}.sort.reverse
end
# 最大・最小となる回転量の候補
def candidates(b,nums)
c=nums.flat_map do |n|
p0, _, e = poly_ix(b,n)
x = (n-p0)/e
(-1..0).map{ |o| (o-x).modulo(b) }
end
c.uniq.sort
end
def solve(src)
bs, ns = src.split(" ")
b = bs.to_i
nums = parse(ns)
rotateds = candidates(b,nums).map{ |r| [r,rotate(b, nums, r)] }
min, max = rotateds.minmax_by{ _1[1] }
[min,max].map{ |m|
rotateds.select{ _1[1]==m[1] }.map(&:first).sort.join(",")
}.join("/")
end
candidates で行った計算をもう一回 rotate でやるのは無駄だし、そもそも poly_ix でループを回すのはダサイと思うけれど、ビット長を n として、
それと。
せっかくなので、 parse の戦略も素朴な実装とは違う作戦のものにしてみた。
素朴な実装は、正規表現で scan する作戦。
今回の実装は「数字以外」で split して、二個ずつ処理する作戦。ちょっと姑息な感じもするけど、正規表現を書かなくていいので短時間で書けそうだと思う。
split だと、1[2][3]4 というような入力に負けるけど、そういう入力はないことになっている（出題当初、そういうテストケースがあるというミスをしていた。すいません）ので大丈夫。
出題してみて
この問題は
- 素朴な実装なら割とすぐに書けるだろう
- スパースであることを利用すると速くできる
- 調査対象を減らせることに来づければもっと速くできる
という三段階になっているところはよいなと思っているけど、問題文が長く、問題を理解するのに時間がかかるのが良くないなと思った。
総合的には悪くないかなと思っている。
次回はもう少し簡単で短い問題を作りたい。
Discussion