最終更新: 2020-06-05T20:36+0900
# @param {Integer[]} rating
# @return {Integer}
def num_teams(rating)
n = rating.size
l,r = [:each, :reverse_each].map{|m|
a,b = [],[nil]*n
rating.send(m).with_index{|p,pi|
i = a.bsearch_index{|_| p<_ }||a.size
b[pi] = [i,a.size-i] # [# of lower, # of upper] leftside/rightside of p.
a.insert(i,p)
}
next b
}
r.reverse!
return n.times.sum{|pi|
(ll,lu),(rl,ru) = l[pi],r[pi]
ll*ru + lu*rl
}
end
最初はこのとき(20190907p01)の解答で使用したデータ構造のどれかが応用できないかとこねこねしていたが、どうにも適合しなかった。そこで改めてこの問題について考えることになったのだけど、たぶんそれはイチから考えるというのとはちょっと違ったと思う。
AtCoder の問題に対して、貪欲法で解ける、DP で解けるというようなことがよく言われるけど、これって実は実際の解法について具体的なことは語っていない。貪欲法とか DP とかいうのは解法の型のようなものでしかない。
二次関数の解について、実数の範囲では場合分けが必要ですよ、ということを教えているようなもので、解の求め方は教えてくれていない。
<脱線>だけど型だけでなく個別具体的なアルゴリズムまで教えてくれないと解けないのです。嘘です。「「"(現在の頂点, 所持している銀貨の枚数) を状態としてdijkstra 法を適用すると、(略) 解くことができます。"」とだけ書かれても、～を状態とするってどういうことですか？」 ここまで教えてもらってもまだ解らないのです。</脱線>
話を戻すと、20190907p01において問題を解くためにインデックスデータを用意した、そのインデックス自体は流用できなかったけど、解答の型は同じだったということ。問題も似てるし。
どういうサイトなんだろう。フォーラムがあるのは結構だけど、Submission を晒す方法がわからない。Count Number of Teams - Submission Detail (32 ms) - LeetCode.pdf 。Facebook でシェアとか、閲覧にログインが必要とか、ボタンがあってもまったくもって無意味なので。
余談：ll(rl) と lu(ru) はどちらか片方だけを記憶すれば十分。pi と n を使った引き算で求められる。でもちょっとだけ遅くなった。Count Number of Teams - Submission Detail (36 ms) - LeetCode.pdf
さっきより遅くなりましたよ……。Count Number of Teams - Submission Detail (52 ms) - LeetCode.pdf。最初が 32 ms で、今度が 52 ms。NlogN と N^2 の違いか。
# @param {Integer[]} rating
# @return {Integer}
def num_teams(rating)
n = rating.size
return [rating,rating.reverse].sum{|r|
up2,up3 = [0]*n,0
(0..n-2).each{|i|
ri = r[i]
(i+1..n-1).each{|j|
next unless ri < r[j]
up2[j] += 1
up3 += up2[i]
}
}
next up3
}
end
ヒントだと思っていたものはフォーラムの書き込みのひとつだった。Python で DP ってやつ。公式のヒントはコレ！ 「BruteForce, check all possibilities.
」 男前だね。
# @param {Integer[]} rating
# @return {Integer}
def num_teams(rating)
n1 = rating.size-1
rs = [] # rating[] sorted
rating.each_with_index{|r,i|
j = rs.bsearch_index{|_,| r<_ }||i
rs.insert(j,[r,i,j])
}
t = 0
rs.each_with_index{|(r,ln,ll),nl|
# nl = # of lower ratings than the r.
# ln/rn = # of ratings on the left/right of the r.
# ll/rl = # of lower ratings on the left/right of the r.
# lu/ru = # of upper ratings on the left/right of the r.
rn = n1-ln
lu = ln-ll
rl = nl-ll
ru = rn-rl
t += lu*rl
t += ll*ru
}
return t
end
最初の版も対称形が美しいと思うのだけど、だからこそズルをする余地があるような気がした。
今度のは捨てていたソート済みのレイティング配列を活用することで二分探索の回数を半分に減らしたもの。ループが２つあるけどどちらのループ変数も単なる添字以上の意味を持ってるのがいい感じ。
しかしメモリ使用量が数十 KiB 減っただけで実行時間は 32 ms のまま変わらず。Ruby で定数倍の改善はちまちました四則演算で相殺されてしまうのか、それとも単に N が小さすぎてスクリプト実行のオーバーヘッドが見えているだけなのか。「Constraints: 1 <= rating.size <= 200
」 32 ms はRuntime Distribution のグラフから左にはみだしてるもんね。
Count Number of Teams - Submission Detail (32 ms, less mem) - LeetCode.pdf
これ以上できることがあるとしたら、愚直な Σ 計算をまとめて計算するようなことか。Σk = n*(n+1)/2 みたいに。
O(NlogN) かと思っていたが配列への挿入が O(N) だから O(N^2) になりそう。やってることが挿入ソートと同じだからそうなんだろう。二分探索のためのランダムアクセスと線形よりましな時間での挿入が両立しない。
平衡二分木があれば O(NlogN) が達成できるんだろうか。実は名前しか知らないんだけど。木なら対数時間で適切な位置に挿入できそうだし、平衡を維持するためには左右配下のノード数を知っていなければいけないはずで、そうすると木をたどるついでに左の枝をカウントしていけば木の中での順序が知れる。たぶん。
名前だけを頼りに insert と each と rebalance メソッドだけ持つ木を作ってみたけど、それを利用して元のスクリプトと同じ答えが出るのは確かめたけど、平衡を保つのが難しいということがわかった。
これまで持っていた雑なイメージでは根っことその左右の子供の間でローテーションするだけでバランスが取れるような気がしていたのだけど、全然そんなことはなかった。芋づる式に全域に渡って枝を付け替えなければいけない雰囲気。
しかも Ruby の組み込み配列を使うのよりくっそ遅い。何十倍も遅い。実装がダメで平衡が保てていないのを差し引いても時間がかかりすぎ。N を大きくしても勝ち目がない。